More Efficient Zero-Knowledge Protocols over  \(\mathbb {Z}_{2^k}\) via Galois Rings

A recent line of works on zero-knowledge (ZK) protocols with a vector oblivious linear function evaluation (VOLE)-based offline phase provides a new paradigm for scalable ZK protocols featuring fast proving and small prover memory. Very recently, Baum et al. (Crypto’23) proposed the VOLE-in-the-head technique, allowing such protocols to become publicly verifiable. Many practically efficient protocols for proving circuit satisfiability over any Galois field are implemented, while protocols over rings \(\mathbb {Z}_{2^k}\) are significantly lagging behind, with only a proof-of-concept pioneering work called Appenzeller to Brie (CCS’21) and a first proposal called Moz \(\mathbb {Z}_{2^k}\) arella (Crypto’22). 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, for example, unlike Galois fields \(\mathbb {F}_{2^{k}}\) , the fraction of units in \(\mathbb {Z}_{2^{k}}\) is 1/2. In this work, we first construct ZK protocols over a high degree Galois ring extension of \(\mathbb {Z}_{2^{k}}\) (fraction of units close to 1) and then convert them to \(\mathbb {Z}_{2^k}\) efficiently using amortization techniques. Our results greatly change the landscape of ZK protocols over  \(\mathbb {Z}_{2^k}\) .