Paper 2019/532

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

Carsten Baum and 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 uses MPC with preprocessing such as recently proposed by Katz, Kolesnikov and Wang (ACM CCS 2018). Our argument system uses only symmetric-key primitives and utilizes a version of the so-called SPDZ-protocol which has efficiency benefits for arithmetic circuits compared to other approaches. 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 and show how our solution compares in terms of argument size to existing work. We moreover 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. To the best of our knowledge, our construction outperforms all known approaches for the SIS problem with post-quantum security either in terms of computation or communication complexity.