Paper 2015/446

On the Amortized Complexity of Zero-knowledge Protocols

Ronald Cramer, Ivan Damgård, and Marcel Keller

Abstract

We propose a general technique that allows improving the complexity of zero-knowledge protocols for a large class of problems where previously the best known solution was a simple cut-and-choose style protocol, i.e., where the size of a proof for problem instance $x$ and error probability $2^{-n}$ was $O(|x| n)$ bits. By using our technique to prove $n$ instances simultaneously, we can bring down the proof size per instance to $O(|x| + n)$ bits for the same error probability while using no computational assumptions. Examples where our technique applies include proofs for quadratic residuosity, proofs of subgroup membership and knowledge of discrete logarithms in groups of unknown order, interval proofs of the latter, and proofs of plaintext knowledge for various types of homomorphic encryption schemes. We first propose our protocols as $\Sigma$-protocols and extend them later to zero-knowledge proofs of knowledge.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in JOC 2014
Keywords
Sigma-protocolszero-knowledgeproof of knowledgehomomorphic encryptionrandom self-reducible problems
Contact author(s)
m keller @ bristol ac uk
History
2015-05-09: received
Short URL
https://ia.cr/2015/446
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/446,
      author = {Ronald Cramer and Ivan Damgård and Marcel Keller},
      title = {On the Amortized Complexity of Zero-knowledge Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2015/446},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/446}},
      url = {https://eprint.iacr.org/2015/446}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.