On the Amortized Complexity of ZeroKnowledge Prot

Authors: Ronald Cramer Ivan Damgård Marcel Keller

Publish Date: 2013/01/31

Volume: 27, Issue: 2, Pages: 284-316

PDF Link

Abstract

We propose a general technique that allows improving the complexity of zeroknowledge protocols for a large class of problems where previously the best known solution was a simple cutandchoose style protocol ie where the size of a proof for problem instance x and error probability 2−n was Oxn bits By using our technique to prove n instances simultaneously we can bring down the proof size per instance to Ox+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 Σprotocols and extend them later to zeroknowledge proofs of knowledgeI Damgård was supported by the Danish National Research Foundation and The National Science Foundation of China under the grant 61061130540 for the Sino–Danish Center for the Theory of Interactive Computation within which part of this work was performed and also by the CFEM research center supported by the Danish Strategic Research Council within which part of this work was performed

Keywords: