Welcome to the resource topic for 2016/681
Title:
Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack
Authors: Ronald Cramer, Ivan Damgard, Chaoping Xing, Chen Yuan
Abstract:We propose a new zero-knowledge protocol for proving knowledge of short preimages under additively homomorphic functions that map integer vectors to an Abelian group. The protocol achieves amortized efficiency in that it only needs to send O(n) auxiliary function values to prove knowledge of n preimages. Furthermore we significantly improve previous bounds on how short a secret we can extract from a dishonest prover, namely our bound is a factor O(k) larger than the size of secret used by the honest prover. In the best previous result, the factor was O(k^{\log k} n). Our main technique is derived from the theory of expanders. Our protocol can be applied to give proofs of knowledge for plaintexts in (Ring-)LWE-based cryptosystems, knowledge of preimages of homomorphic hash functions as well as knowledge of committed values in some integer commitment schemes.
ePrint: https://eprint.iacr.org/2016/681
Talk: https://www.youtube.com/watch?v=ajiWrb3KgQY
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 .