Efficiency Limitations for Σ-Protocols for Group Homomorphisms

E. Bangerter, J. Camenisch, S. Krenn, in:, D. Micciancio (Ed.), Springer, 2010, pp. 553–571.


Conference Paper | Published
Author
; ;
Editor
Series Title
LNCS
Abstract
Efficient zero-knowledge proofs of knowledge for group homomorphisms are essential for numerous systems in applied cryptography. Especially, Σ-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, while 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 Σ-protocols not using common reference strings or the like. We prove our results for a comprehensive class of Σ-protocols in the generic group model, and further strengthen them by investigating certain instantiations in the plain model.
Publishing Year
Date Published
2010-02-08
Volume
5978
Page
553 - 571
Conference
TCC: Theory of Cryptography Conference
IST-REx-ID

Cite this

Bangerter E, Camenisch J, Krenn S. Efficiency Limitations for Σ-Protocols for Group Homomorphisms. In: Micciancio D, ed. Vol 5978. Springer; 2010:553-571. doi:10.1007/978-3-642-11799-2
Bangerter, E., Camenisch, J., & Krenn, S. (2010). Efficiency Limitations for Σ-Protocols for Group Homomorphisms. In D. Micciancio (Ed.) (Vol. 5978, pp. 553–571). Presented at the TCC: Theory of Cryptography Conference, Springer. https://doi.org/10.1007/978-3-642-11799-2
Bangerter, Endre, Jan Camenisch, and Stephan Krenn. “Efficiency Limitations for Σ-Protocols for Group Homomorphisms.” edited by Daniele Micciancio, 5978:553–71. Springer, 2010. https://doi.org/10.1007/978-3-642-11799-2.
E. Bangerter, J. Camenisch, and S. Krenn, “Efficiency Limitations for Σ-Protocols for Group Homomorphisms,” presented at the TCC: Theory of Cryptography Conference, 2010, vol. 5978, pp. 553–571.
Bangerter E, Camenisch J, Krenn S. 2010. Efficiency Limitations for Σ-Protocols for Group Homomorphisms. TCC: Theory of Cryptography Conference, LNCS, vol. 5978. 553–571.
Bangerter, Endre, et al. Efficiency Limitations for Σ-Protocols for Group Homomorphisms. Edited by Daniele Micciancio, vol. 5978, Springer, 2010, pp. 553–71, doi:10.1007/978-3-642-11799-2.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar