Paper 2023/150
More Efficient ZeroKnowledge Protocols over $\mathbb{Z}_{2^k}$ via Galois Rings
Abstract
A recent line of works on zeroknowledge (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 VOLEinthehead 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 proofofconcept 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 reallife programming and the computer architectures such as CPU words), presents nontrivial 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 stateoftheart Moz$\mathbb{Z}_{2^k}$arella. We remove the undesirable dependence of communication complexity on the security parameter, and achieve communication complexity {\em strictly} linear in the circuit size. Furthermore, our protocol has better concrete efficiency. For $40,80$ bits soundness on circuits over $\mathbb{Z}_{2^{32}}$ and $\mathbb{Z}_{2^{64}}$, 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 show that the pseudorandom correlation generator approach can be adapted to efficiently implement VOLE over Galois rings, with analysis of the hardness of underlying LPN assumptions over Galois rings. (4) We adapt the VOLEinthehead technique to make it work for $\mathbb{Z}_{2^k}$, yielding {\em publicly verifiable} noninteractive ZK protocols over $\mathbb{Z}_{2^k}$ which preserve most of the efficiency metrics of the VOLEbased ZK protocols.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in CRYPTO 2024
 Keywords
 Zero Knowledge
 Contact author(s)

linfuchun @ sjtu edu cn
xingcp @ sjtu edu cn
yaoyizhou0620 @ sjtu edu cn  History
 20240723: last of 7 revisions
 20230208: 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 ZeroKnowledge Protocols over $\mathbb{Z}_{2^k}$ via Galois Rings}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/150}, year = {2023}, url = {https://eprint.iacr.org/2023/150} }