Recently, there is a growing need for SNARKs to operate over a broader range of algebraic structures, and one important structure is Galois ring. We present transparent SNARK schemes over arbitrary Galois rings. Compared with Rinocchio scheme in Ganesh et al. (J Cryptol 2023), our SNARK schemes do not require a trusted third party to establish a structured reference string (SRS). In this paper, we present the expander code over arbitrary Galois rings, which can be encoded in O(n) time. Using this expander code, we then extend the Brakedown commitment scheme in Golovnev et al. (CRYPTO 2023) to Galois rings. By combining the Libra framework in Xie et al. (CRYPTO 2019), we present a transparent SNARK for log-space uniform circuits over Galois rings, achieving O(n) prover time, \(O(\sqrt{n})\) proof size, and \(O(\sqrt{n})\) verifier time. And by combining HyperPlonk in Chen et al. (EUROCRYPT 2023), we present a transparent SNARK for NP circuits over Galois rings, with \(O(n\log ^2 n)\) prover time, \(O(\sqrt{n})\) proof size, and \(O(\sqrt{n})\) verifier time.

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

Transparent SNARKs over Galois Rings

  • Yuanju Wei,
  • Xinxuan Zhang,
  • Yi Deng

摘要

Recently, there is a growing need for SNARKs to operate over a broader range of algebraic structures, and one important structure is Galois ring. We present transparent SNARK schemes over arbitrary Galois rings. Compared with Rinocchio scheme in Ganesh et al. (J Cryptol 2023), our SNARK schemes do not require a trusted third party to establish a structured reference string (SRS). In this paper, we present the expander code over arbitrary Galois rings, which can be encoded in O(n) time. Using this expander code, we then extend the Brakedown commitment scheme in Golovnev et al. (CRYPTO 2023) to Galois rings. By combining the Libra framework in Xie et al. (CRYPTO 2019), we present a transparent SNARK for log-space uniform circuits over Galois rings, achieving O(n) prover time, \(O(\sqrt{n})\) proof size, and \(O(\sqrt{n})\) verifier time. And by combining HyperPlonk in Chen et al. (EUROCRYPT 2023), we present a transparent SNARK for NP circuits over Galois rings, with \(O(n\log ^2 n)\) prover time, \(O(\sqrt{n})\) proof size, and \(O(\sqrt{n})\) verifier time.