Paper 2023/150

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

Fuchun Lin, Shanghai Jiao Tong University
Chaoping Xing, Shanghai Jiao Tong University
Yizhou Yao, Shanghai Jiao Tong University
Abstract

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}$. (1) We propose a competing ZK protocol that has many advantages over the state-of-the-art Moz$\mathbb{Z}_{2^k}$arella. We remove the undesirable dependence of communication complexity on the security parameter, and achieve (strict) linear communication complexity. Furthermore, our protocol has better concrete efficiency. For $40,80$ bits soundness on $32,64$-bit CPUs, we offer $1.15\times$--$2.9\times$ improvements in communication. (2) Inspired by the recently proposed interactive message authentication code technique (Weng et al., CCS'22), we construct a constant round ZK protocol over $\mathbb{Z}_{2^k}$ with sublinear (in the circuit size) communication complexity, which was previously achieved only over fields. (3) We adapt the VOLE-in-the-head technique, and apply it to our first ZK protocol, yielding the first {\em publicly verifiable} non-interactive ZK over $\mathbb{Z}_{2^k}$ with linear communication complexity. Also, we show that the pseudorandom correlation generator approach (incompatible with VOLE-in-the-head) can be adapted to efficiently implement VOLE over Galois rings, with analysis of the hardness of underlying assumptions.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Zero Knowledge
Contact author(s)
linfuchun @ sjtu edu cn
xingcp @ sjtu edu cn
yaoyizhou0620 @ sjtu edu cn
History
2023-10-07: last of 4 revisions
2023-02-08: received
See all versions
Short URL
https://ia.cr/2023/150
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/150,
      author = {Fuchun Lin and Chaoping Xing and Yizhou Yao},
      title = {More Efficient Zero-Knowledge Protocols over $\mathbb{Z}_{2^k}$ via Galois Rings},
      howpublished = {Cryptology ePrint Archive, Paper 2023/150},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/150}},
      url = {https://eprint.iacr.org/2023/150}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.