Paper 2023/1610
An Efficient ZK Compiler from SIMD Circuits to General Circuits
Abstract
We propose a generic compiler that can convert any zero-knowledge proof for SIMD circuits to general circuits efficiently, and an extension that can preserve the space complexity of the proof systems. Our compiler can immediately produce new results improving upon state of the art. -By plugging in our compiler to Antman, an interactive sublinear-communication protocol, we improve the overall communication complexity for generalcircuits from $\mathcal{O}(C^{3/4})$ to $\mathcal{O}(C^{1/2})$. Our implementation shows that for a circuit of size $2^{27}$, it achieves up to $83.6\times$ improvement on communication compared to the state-of-the-art implementation. Its end-to-end running time is at least $70\%$ faster in a $10$Mbps network. -Using recent results on compressed $\Sigma$-protocol theory, we obtain a discrete-log-based constant-round zero-knowledge argument with $\mathcal{O}(C^{1/2})$ communication and common random string length, improving over the state of the art that has linear-size common random string and requires heavier computation. -We improve the communication of a designated $n$-verifier zero-knowledge proof from $\mathcal{O}(nC/B+n^2B^2)$ to $\mathcal{O}(nC/B+n^2)$. To demonstrate the scalability of our compilers, we were able to extract a commit-and-prove SIMD ZK from Ligero and cast it in our framework. We also give one instantiation derived from LegoSNARK, demonstrating that the idea of CP-SNARK also fits in our methodology.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Zero-Knowledge ProofSIMD ZK
- Contact author(s)
-
bui @ irif fr
chtvii @ sjtu edu cn
couteau @ irif fr
wangxiao @ cs northwestern edu
ckweng @ u northwestern edu
yangk @ sklc org
yuyu @ sjtu edu cn - History
- 2023-10-20: approved
- 2023-10-17: received
- See all versions
- Short URL
- https://ia.cr/2023/1610
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1610, author = {Dung Bui and Haotian Chu and Geoffroy Couteau and Xiao Wang and Chenkai Weng and Kang Yang and Yu Yu}, title = {An Efficient ZK Compiler from SIMD Circuits to General Circuits}, howpublished = {Cryptology ePrint Archive, Paper 2023/1610}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1610}}, url = {https://eprint.iacr.org/2023/1610} }