Efficiency limitations of Σ-protocols for group homomorphisms revisited
2012 (English)In: Security and Cryptography for Networks, Springer Berlin/Heidelberg, 2012, 461-476 p.Conference paper (Refereed)
We study the problem of constructing efficient proofs of knowledge of preimages of general group homomorphisms. We simplify and extend the recent negative results of Bangerter et al. (TCC 2010) to constant round (from three-message) generic protocols over concrete (instead of generic) groups, i.e., we prove lower bounds on both the soundness error and the knowledge error of such protocols. We also give a precise characterization of what can be extracted from the prover in the direct (common) generalization of the Guillou-Quisquater and Schnorr protocols to the setting of general group homomorphisms. Then we consider some settings in which these bounds can be circumvented. For groups with no subgroups of small order we present: (1) a three-move honest verifier zero-knowledge argument under some set-up assumptions and the standard discrete logarithm assumption, and (2) a Σ-proof of both the order of the group and the preimage. The former may be viewed as an offline/online protocol, where all slow cut-andchoose protocols can be moved to an offline phase.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2012. 461-476 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 7485 LNCS
Discrete logarithms, Efficiency limitations, Lower bounds, Offline, Preimages, Zero knowledge, Cryptography, Algebra
IdentifiersURN: urn:nbn:se:kth:diva-105313DOI: 10.1007/978-3-642-32928-9_26ScopusID: 2-s2.0-84866706029ISBN: 978-364232927-2OAI: oai:DiVA.org:kth-105313DiVA: diva2:570624
8th International Conference on Security and Cryptography for Networks, SCN 2012, 5 September 2012 through 7 September 2012, Amalfi
FunderICT - The Next Generation
QC 201211202012-11-202012-11-202015-04-28Bibliographically approved