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) 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, where k is the statistical security parameter. In the best previous result, the factor was O(klog kn). 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.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-319-56620-7_17
Series Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence
Conference Advances in Cryptology - EUROCRYPT
Citation
Cramer, R.J.F, Damgård, I.B, Xing, C, & Yuan, C. (2017). Amortized complexity of zero-knowledge proofs revisited: Achieving linear soundness slack. In Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence. doi:10.1007/978-3-319-56620-7_17