Paper 2023/150
More Efficient Zero-Knowledge Protocols over $\mathbb{Z}_{2^k}$ via Galois Rings
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)
- 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
-
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} }