Paper 2016/681

Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack

Ronald Cramer, Ivan Damgard, Chaoping Xing, and Chen Yuan


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.

Note: This revision contains a stronger result than the original version, in that the protocol now works with a quadratic number of inputs instances rather than cubic as before.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in EUROCRYPT 2017
zero-knowledgeprotocolsproofs of knowledge
Contact author(s)
ivan @ cs au dk
2017-02-14: last of 2 revisions
2016-07-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ronald Cramer and Ivan Damgard and Chaoping Xing and Chen Yuan},
      title = {Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack},
      howpublished = {Cryptology ePrint Archive, Paper 2016/681},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.