Scholarlink

<p>Recent years have seen the widespread adoption of zkSNARKs constructed over small fields, including but not limited to, the Goldilocks field, small Mersenne prime fields, and tower of binary fields. Their appeal stems primarily from their efficacy in proving computations with small bit widths, which facilitates efficient proving of general computations and offers significant advantages, notably yielding remarkably fast proving efficiency for tasks such as proof of knowledge of hash preimages. Nevertheless, employing these SNARKs to prove algebraic statements (e.g., RSA, ECDSA signature verification) presents efficiency challenges, particularly in critical applications like zk-bridges and zkVMs that require verifying standard cryptographic primitives. To address this problem, we first define a new circuit model: arithmetic circuits with additional <i>exponentiation gates</i>. These gates serve as fundamental building blocks for establishing more intricate algebraic relations. Then we present a <i>Hash-committed Commit-and-Prove (HCP)</i> framework to construct Non-interactive Zero-knowledge (NIZK) proofs for the satisfiability of these circuits. Specifically, when proving knowledge of group exponentiations in discrete logarithm hard groups and RSA groups, compared to verifying complex group exponentiations within SNARK circuits, our approach requires proving only more lightweight computations within the SNARK, such as zk-friendly hash functions (e.g., Poseidon hash function). The number of these lightweight computations depends solely on the security parameter. This differentiation leads to substantial speedups for the prover relative to direct SNARK methods, while maintaining competitive proof size and verification cost.</p>

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

Proof of exponentiation: enhanced prover efficiency for algebraic statements

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年1月27日

查看全文
  • Zhuo Wu,
  • Shi Qi,
  • Xinxuan Zhang,
  • Yi Deng,
  • Kun Lai,
  • Hailong Wang

摘要

Recent years have seen the widespread adoption of zkSNARKs constructed over small fields, including but not limited to, the Goldilocks field, small Mersenne prime fields, and tower of binary fields. Their appeal stems primarily from their efficacy in proving computations with small bit widths, which facilitates efficient proving of general computations and offers significant advantages, notably yielding remarkably fast proving efficiency for tasks such as proof of knowledge of hash preimages. Nevertheless, employing these SNARKs to prove algebraic statements (e.g., RSA, ECDSA signature verification) presents efficiency challenges, particularly in critical applications like zk-bridges and zkVMs that require verifying standard cryptographic primitives. To address this problem, we first define a new circuit model: arithmetic circuits with additional exponentiation gates. These gates serve as fundamental building blocks for establishing more intricate algebraic relations. Then we present a Hash-committed Commit-and-Prove (HCP) framework to construct Non-interactive Zero-knowledge (NIZK) proofs for the satisfiability of these circuits. Specifically, when proving knowledge of group exponentiations in discrete logarithm hard groups and RSA groups, compared to verifying complex group exponentiations within SNARK circuits, our approach requires proving only more lightweight computations within the SNARK, such as zk-friendly hash functions (e.g., Poseidon hash function). The number of these lightweight computations depends solely on the security parameter. This differentiation leads to substantial speedups for the prover relative to direct SNARK methods, while maintaining competitive proof size and verification cost.