This paper introduces the first multilinear polynomial commitment scheme (PCS) over Galois rings achieving \(\mathcal {O}(\log ^2 n)\) verification cost. It achieves \(\mathcal {O}(n\log n)\) committing time and \(\mathcal {O}(n)\) evaluation opening prover time. This PCS can be used to construct zero-knowledge proofs for arithmetic circuits over Galois rings, facilitating verifiable computation in applications requiring proofs of polynomial ring operations (e.g., verifiable fully homomorphic encryption). First we construct random foldable linear codes over Galois rings with sufficient code distance and present a distance preservation theorem over Galois rings. Second we extend the \(\textsf {Basefold}\) commitment (Zeilberger et al., Crypto 2024) to multilinear polynomials over Galois rings. Our approach reduces proof size and verifier time from \(\mathcal {O}(\sqrt{n})\) to \(\mathcal {O}(\log ^2 n)\) compared to Wei et al., PKC 2025. Furthermore, we give a batched multipoint opening protocol for evaluation phase that collapses the proof size and verifier time of N polynomials at M points from \(\mathcal {O}(NM \log ^2 n)\) to \(\mathcal {O}(\log ^2 n)\) , prover time from \(\mathcal {O}(NMn)\) to \(\mathcal {O}(n)\) , further enhancing efficiency.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Polylogarithmic Polynomial Commitment Scheme over Galois Rings

  • Zhuo Wu,
  • Xinxuan Zhang,
  • Yi Deng,
  • Yuanju Wei,
  • Zhongliang Zhang,
  • Liuyu Yang

摘要

This paper introduces the first multilinear polynomial commitment scheme (PCS) over Galois rings achieving \(\mathcal {O}(\log ^2 n)\) verification cost. It achieves \(\mathcal {O}(n\log n)\) committing time and \(\mathcal {O}(n)\) evaluation opening prover time. This PCS can be used to construct zero-knowledge proofs for arithmetic circuits over Galois rings, facilitating verifiable computation in applications requiring proofs of polynomial ring operations (e.g., verifiable fully homomorphic encryption). First we construct random foldable linear codes over Galois rings with sufficient code distance and present a distance preservation theorem over Galois rings. Second we extend the \(\textsf {Basefold}\) commitment (Zeilberger et al., Crypto 2024) to multilinear polynomials over Galois rings. Our approach reduces proof size and verifier time from \(\mathcal {O}(\sqrt{n})\) to \(\mathcal {O}(\log ^2 n)\) compared to Wei et al., PKC 2025. Furthermore, we give a batched multipoint opening protocol for evaluation phase that collapses the proof size and verifier time of N polynomials at M points from \(\mathcal {O}(NM \log ^2 n)\) to \(\mathcal {O}(\log ^2 n)\) , prover time from \(\mathcal {O}(NMn)\) to \(\mathcal {O}(n)\) , further enhancing efficiency.