Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zkSNARKs) are increasingly utilized across diverse applications. While significant advances have been made in the development of post-quantum secure zkSNARKs, these schemes face challenges, including substantial computational complexity. In this paper, we propose leveraging the Cantor special basis in post-quantum secure zkSNARKs operating over binary extension fields. This approach enables the optimization of the additive Fast Fourier Transform (FFT) algorithm in Aurora, a post-quantum secure zkSNARK, by replacing the previously used Gao–Mateer FFT with the Cantor and LCH FFTs. Our implementation demonstrates a significant reduction in computation time for Aurora, with the potential to accelerate other zkSNARKs utilizing additive FFTs. Additionally, we present a detailed theoretical analysis of the computational costs of the Cantor FFT algorithm, providing exact counts of additions, multiplications, and precomputation overhead. Furthermore, we analyze the FFT call complexity within the encoding of the Rank-1 Constraint System in the Aurora zkSNARK.

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

Accelerating Post-quantum Secure zkSNARKs by Optimizing Additive FFT

  • Mohammadtaghi Badakhshan,
  • Susanta Samanta,
  • Guang Gong

摘要

Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zkSNARKs) are increasingly utilized across diverse applications. While significant advances have been made in the development of post-quantum secure zkSNARKs, these schemes face challenges, including substantial computational complexity. In this paper, we propose leveraging the Cantor special basis in post-quantum secure zkSNARKs operating over binary extension fields. This approach enables the optimization of the additive Fast Fourier Transform (FFT) algorithm in Aurora, a post-quantum secure zkSNARK, by replacing the previously used Gao–Mateer FFT with the Cantor and LCH FFTs. Our implementation demonstrates a significant reduction in computation time for Aurora, with the potential to accelerate other zkSNARKs utilizing additive FFTs. Additionally, we present a detailed theoretical analysis of the computational costs of the Cantor FFT algorithm, providing exact counts of additions, multiplications, and precomputation overhead. Furthermore, we analyze the FFT call complexity within the encoding of the Rank-1 Constraint System in the Aurora zkSNARK.