Cryptology ePrint Archive: Report 2016/681

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

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.

Category / Keywords: cryptographic protocols / zero-knowledge, protocols, proofs of knowledge

Original Publication (in the same form): IACR-EUROCRYPT-2017

Date: received 6 Jul 2016, last revised 14 Feb 2017

Contact author: ivan at cs au dk

Available format(s): PDF | BibTeX Citation

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.

Version: 20170214:115713 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]