CryptoDB
Polynomial Commitments for Galois Rings and Applications to SNARKs over $\mathbb{Z}_{2^k}$
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | Succinct non-interactive arguments of knowledge (SNARKs) allow a weak verifier to delegate computation tasks to a powerful prover in a verifiable way. However, most SNARK constructions require the computation tasks to be represented as arithmetic circuits over finite fields, incurring a significant overhead when applied for delegations of modern computer programs, which typically are of $\mathbb{Z}_{2^{64}}$ or $\mathbb{Z}_{2^{32}}$ arithmetics. The only exception is Rinocchio (JoC 2023), which builds the first SNARK for rings and features constant proof size. Due to $\mathbb{Z}_{2^k}$ being lack of large evaluation sets for polynomial interpolations, Rinocchio resorts to Galois ring extensions of $\mathbb{Z}_{2^k}$. However, Rinocchio is designated-verifier and the concrete efficiency is unclear at the moment. Towards building {\em publicly verifiable} SNARKs for rings $\mathbb{Z}_{2^k}$, we follow the well-established framework of polynomial interactive oracle proofs (IOP)-based SNARKs, and obtain the following results: i) We systematically study the proximity gaps for Reed-Solomon codes over Galois rings. We prove that for Galois rings, the state-of-the-art $(1-\rho)/2$ gap for finite fields given by Ben-Sasson et al. (JACM 2023) still holds. This allows to construct efficient polynomial commitment schemes for Galois rings based on Reed-Solomon codes. ii) We construct efficient polynomial IOPs for rank one constraint systems (R1CS) over $\mathbb{Z}_{2^k}$ via Galois rings. To amortize the overhead of operating on a large Galois ring extension of $\mathbb{Z}_{2^k}$, we make use of the reverse-multiplication friendly embeddings (RMFEs) techniques. iii) Combining the above two ingredients together, we put forward the first {\em publicly verifiable} SNARKs for rings $\mathbb{Z}_{2^k}$ with a transparent setup and plausibly post-quantum security. In addition, we implement and evaluate our constructions. Our evaluations indicate the concrete efficiency is promising, provided that Galois rings operations are optimized well. |
BibTeX
@inproceedings{crypto-2025-35581,
title={Polynomial Commitments for Galois Rings and Applications to SNARKs over $\mathbb{Z}_{2^k}$},
publisher={Springer-Verlag},
author={Yuhao Jia and Songsong Li and Chaoping Xing and Yizhou Yao and Chen Yuan},
year=2025
}