Welcome to the resource topic for 2023/150
Title:
More Efficient Zero-Knowledge Protocols over \mathbb{Z}_{2^k} via Galois Rings
Authors: Fuchun Lin, Chaoping Xing, Yizhou Yao
Abstract:A recent line of works on zero knowledge (ZK) protocols with a {\em vector oblivious linear function evaluation (VOLE)}-based offline phase provides a new paradigm for scalable ZK protocols with prover memory footprint almost the same as verifying the circuit in the clear. Most of these protocols can be made to have a {\em non-interactive} online phase, yielding a {\em preprocessing NIZK}. In particular, when the preprocessing is realized by a two-round protocol, one obtains a {\em malicious designated verifier-NIZK (MDV-NIZK)}, which is a recent closely scrutinized variant of DV-NIZK that allows the verifier to generate a public key (first message of two-round protocol) for the prover and a secret key to verify proofs. Though many practically efficient protocols for proving circuit satisfiability over any field are implemented, protocols over the ring \mathbb{Z}_{2^k} are significantly lagging behind, with only a proof-of-concept pioneering work called {\em Appenzeller to Brie} and a first proposal called {\em Moz$\mathbb{Z}{2^k}arella}. The ring \mathbb{Z}{2^{32}} or \mathbb{Z}{2^{64}}, though highly important (it captures computation in real-life programming and the computer architectures such as CPU words), presents non-trivial difficulties because, unlike Galois fields \mathbb{F}{2^{k}}, the fraction of units in rings \mathbb{Z}{2^{k}}$ is 1/2. In this work, we first construct protocols over a large Galois ring extension of \mathbb{Z}_{2^{k}} (fraction of units close to 1) and then convert to \mathbb{Z}_{2^k} efficiently using amortization techniques. Our results greatly change the landscape of ZK protocols over \mathbb{Z}_{2^k}.
(1) We propose a competing basic protocol that has many advantages over the state-of-the-art Moz$\mathbb{Z}{2^k}$arella: our efficiency is independent of the security parameter (so overwhelming superiority in high security region); for frequently used 40,80 bits soundness on 32,64-bit CPUs we all offer savings (up to 3\times at best).
(2) Through adapting a recently proposed {\em interactive} authentication code to work over Galois rings, we obtain constant round VOLE-based ZK protocols over \mathbb{Z}_{2^k} with sublinear (in the circuit size) communication complexity, which was previously achieved only over fields.
(3) In order to circumvent the impossibility result of OT-based reusable VOLE, we propose a novel construction of two-round {\em reusable} VOLE over Galois rings using Galois fields counterpart and powerful tools developed for non-interactive secure computation. We also show that the pseudorandom correlation generator (PCG) approach to extending VOLE without increasing rounds can be generalized to Galois rings. Instantiating a non-interactive version of our basic protocol with a two-round reusable VOLE preprocessing, we obtain MDV-NIZK over \mathbb{Z}_{2^k} with unique features. Such protocols are not only never achieved over rings but also new over small fields.
ePrint: https://eprint.iacr.org/2023/150
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 .