2017-04-30
Amortized complexity of zero-knowledge proofs revisited: Achieving linear soundness slack
Publication
Publication
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 | |
|---|---|
| doi.org/10.1007/978-3-319-56620-7_17 | |
| Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence | |
| Advances in Cryptology - EUROCRYPT | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Cramer, R., Damgård, I., Xing, C., & Yuan, C. (2017). Amortized complexity of zero-knowledge proofs revisited: Achieving linear soundness slack. In EUROCRYPT 2017: Advances in Cryptology – EUROCRYPT 2017 (pp. 479–500). doi:10.1007/978-3-319-56620-7_17 |
|
