Paper 2009/595

Efficiency Limitations for $\Sigma$-Protocols for Group Homomorphisms

Endre Bangerter, Jan Camenisch, and Stephan Krenn

Abstract

Efficient zero-knowledge proofs of knowledge for group homomorphisms are essential for numerous systems in applied cryptography. Especially, $\Sigma$-protocols for proving knowledge of discrete logarithms in known and hidden order groups are of prime importance. Yet, while these proofs can be performed very efficiently within groups of known order, for hidden order groups the respective proofs are far less efficient. This paper shows strong evidence that this efficiency gap cannot be bridged. Namely, whilst there are efficient protocols allowing a prover to cheat only with negligibly small probability in the case of known order groups, we provide strong evidence that for hidden order groups this probability is bounded below by $1/2$ for all efficient $\Sigma$-protocols not using common reference strings or the like. We prove our results for a comprehensive class of $\Sigma$-protocols in the generic group model, and further strengthen them by investigating certain instantiations in the plain model.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Extended abstract appears in TCC 2010.
Keywords
Generic Group Model$\Sigma$-ProtocolsProofs of KnowledgeError Bounds
Contact author(s)
stephan krenn @ bfh ch
History
2009-12-04: revised
2009-12-04: received
See all versions
Short URL
https://ia.cr/2009/595
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/595,
      author = {Endre Bangerter and Jan Camenisch and Stephan Krenn},
      title = {Efficiency Limitations for $\Sigma$-Protocols for Group Homomorphisms},
      howpublished = {Cryptology ePrint Archive, Paper 2009/595},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/595}},
      url = {https://eprint.iacr.org/2009/595}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.