International Association
for Cryptologic Research

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.