Welcome to the resource topic for 2019/532
Title:
Concretely-Efficient Zero-Knowledge Arguments for Arithmetic Circuits and Their Application to Lattice-Based Cryptography
Authors: Carsten Baum, Ariel Nof
Abstract: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.
ePrint: https://eprint.iacr.org/2019/532
Talk: https://www.youtube.com/watch?v=6q_Cc3RNzLE
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 .