Paper 2018/560

Sub-Linear Lattice-Based Zero-Knowledge Arguments for Arithmetic Circuits

Carsten Baum, Jonathan Bootle, Andrea Cerulli, Rafael del Pino, Jens Groth, and Vadim Lyubashevsky


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.

Available format(s)
Publication info
Published by the IACR in CRYPTO 2018
Zero-KnowledgeArithmetic CircuitsSub-linear proofsCommitments
Contact author(s)
carsten baum @ biu ac il
jonathan bootle 14 @ ucl ac uk
andrea cerulli 13 @ ucl ac uk
Rafael Del Pino @ ens fr
j groth @ ucl ac uk
vadim lyubash @ gmail com
2018-06-04: received
Short URL
Creative Commons Attribution


      author = {Carsten Baum and Jonathan Bootle and Andrea Cerulli and Rafael del Pino and Jens Groth and Vadim Lyubashevsky},
      title = {Sub-Linear Lattice-Based Zero-Knowledge Arguments for Arithmetic Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2018/560},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.