Welcome to the resource topic for 2018/560
Title:
Sub-Linear Lattice-Based Zero-Knowledge Arguments for Arithmetic Circuits
Authors: Carsten Baum, Jonathan Bootle, Andrea Cerulli, Rafael del Pino, Jens Groth, Vadim Lyubashevsky
Abstract:We propose the first zero-knowledge argument with sub-linear communication complexity for arithmetic circuit satisfiability over a prime p whose security is based on the hardness of the short integer solution (SIS) problem. For a circuit with N gates, the communication complexity of our protocol is O\left(\sqrt{N\lambda\log^3{N}}\right), where \lambda is the security parameter. A key component of our construction is a surprisingly simple zero-knowledge proof for pre-images of linear relations whose amortized communication complexity depends only logarithmically on the number of relations being proved. This latter protocol is a substantial improvement, both theoretically and in practice, over the previous results in this line of research of Damgård et al. (CRYPTO 2012), Baum et al. (CRYPTO 2016), Cramer et al. (EUROCRYPT 2017) and del Pino and Lyubashevsky (CRYPTO 2017), and we believe it to be of independent interest.
ePrint: https://eprint.iacr.org/2018/560
Talk: https://www.youtube.com/watch?v=Dj073BX-lUg
Slides: https://crypto.iacr.org/2018/slides/28829.pdf
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 .