Paper 2019/532

Concretely-Efficient Zero-Knowledge Arguments for Arithmetic Circuits and Their Application to Lattice-Based Cryptography

Carsten Baum and Ariel Nof


In this work we present a new interactive Zero-Knowledge Argument of knowledge for general arithmetic circuits. Our protocol is based on the ``MPC-in-the-head''-paradigm of Ishai et al. (STOC 2009) and follows the recent ``MPC-in-the-head with Preprocessing'' as proposed by Katz, Kolesnikov and Wang (ACM CCS 2018). However, in contrast to Katz et al. who used the ``cut-and-choose'' approach for pre-processing, we show how to incorporate the well-known ``sacrificing'' paradigm into ``MPC-in-the-head'', which reduces the proof size when working over arithmetic circuits. Our argument system uses only lightweight symmetric-key primitives and utilizes a simplified version of the so-called SPDZ-protocol. Based on specific properties of our protocol we then show how it can be used to construct an efficient Zero-Knowledge Argument of Knowledge for instances of the Short Integer Solution (SIS) problem. We present different protocols that are tailored to specific uses of SIS, while utilizing the advantages of our scheme. In particular, we present a variant of our argument system that allows the parties to sample the circuit ``on the fly'', which may be of independent interest. We furthermore implemented our Zero-Knowledge argument for SIS and show that using our protocols it is possible to run a complete interactive proof, even for general SIS instances which result in a circuit with $>10^6$ gates, in less than 0.5 seconds.

Note: This is the full version of the paper that will appear at PKC 2020.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2020
zero-knowledgelattice cryptographyMPC
Contact author(s)
nofdinar @ gmail com
carsten baum @ outlook com
2020-02-16: revised
2019-05-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carsten Baum and Ariel Nof},
      title = {Concretely-Efficient Zero-Knowledge Arguments for Arithmetic Circuits and Their Application to Lattice-Based Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2019/532},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.