Welcome to the resource topic for 2015/446
Title:
On the Amortized Complexity of Zero-knowledge Protocols
Authors: Ronald Cramer, Ivan Damgård, 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.
ePrint: https://eprint.iacr.org/2015/446
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .