**On the Amortized Complexity of Zero-knowledge Protocols**

*Ronald Cramer and 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.

**Category / Keywords: **cryptographic protocols / Sigma-protocols, zero-knowledge, proof of knowledge, homomorphic encryption, random self-reducible problems

**Original Publication**** (in the same form): **IACR-JOC-2014

**Date: **received 9 May 2015

**Contact author: **m keller at bristol ac uk

**Available format(s): **PDF | BibTeX Citation

**Version: **20150509:152422 (All versions of this report)

**Short URL: **ia.cr/2015/446

[ Cryptology ePrint archive ]