Paper 2019/1251

Lattice-based Zero-knowledge SNARGs for Arithmetic Circuits

Anca Nitulescu


Succinct non-interactive arguments (SNARGs) enable verifying NP computations with substantially lower complexity than that required for classical NP verification. In this work, we construct a zero-knowledge SNARG candidate that relies only on lattice-based assumptions which are claimed to hold even in the presence of quantum computers. Central to this new construction is the notion of linear-targeted malleability introduced by Bitansky et al. (TCC 2013) and the conjecture that variants of Regev encryption satisfy this property. Then, using the efficient characterization of NP languages as Square Arithmetic Programs we build the first quantum-resilient zk-SNARG for arithmetic circuits with a constant-size proof consisting of only 2 lattice-based ciphertexts. Our protocol is designated-verifier, achieves zero-knowledge and has shorter proofs and shorter CRS than the previous such schemes, e.g. Boneh et al. (Eurocrypt 2017).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere.
lattice-basedzero knowledgeSNARGpost-quantum
Contact author(s)
anca nitulescu @ cosmian com
2019-10-28: received
Short URL
Creative Commons Attribution


      author = {Anca Nitulescu},
      title = {Lattice-based Zero-knowledge SNARGs for Arithmetic Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1251},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.