Paper 2025/533

JesseQ: Efficient Zero-Knowledge Proofs for Circuits over Any Field

Mengling Liu, The Hong Kong Polytechnic University
Yang Heng, The Hong Kong Polytechnic University
Xingye Lu, The Hong Kong Polytechnic University
Man Ho Au, The Hong Kong Polytechnic University
Abstract

Recent advances in Vector Oblivious Linear Evaluation (VOLE) protocols have enabled constant-round, fast, and scalable (designated-verifier) zero-knowledge proofs, significantly reducing prover computational cost. Existing protocols, such as QuickSilver [CCS’21] and LPZKv2 [CCS’22], achieve efficiency with prover costs of 4 multiplications in the extension field per AND gate for Boolean circuits, with one multiplication requiring a O(κ log κ)-bit operation where κ = 128 is the security parameter and 3-4 field multiplications per multiplication gate for arithmetic circuits over a large field. We introduce JesseQ, a suite of two VOLE-based protocols: JQv1 and JQv2, which advance state of the art. JQv1 requires only 2 scalar multiplications in an extension field per AND gate for Boolean circuits, with one scalar needing a O(κ)- bit operation, and 2 field multiplications per multiplication gate for arithmetic circuits over a large field. In terms of communication costs, JQv1 needs just 1 field element per gate. JQv2 further reduces communication costs by half at the cost of doubling the prover’s computation. Experiments show that, compared to the current state of the art, both JQv1 and JQv2 achieve at least 3.9× improvement in the online phase for Boolean circuits. For large field circuits, JQv1 has a similar performance, while JQv2 offers a 1.3× improvement. Additionally, both JQv1 and JQv2 maintain the same communication cost as the current state of the art. Notably, on the cheapest AWS instances, JQv1 can prove 9.2 trillion AND gates (or 5.8 trillion multiplication gates over a 61-bit field) for just one US dollar. JesseQ excels in applications like inner products, matrix multiplication, and lattice problems, delivering 40%- 200% performance improvements compared to QuickSilver. Additionally, JesseQ integrates seamlessly with the sublinear Batchman framework [CCS’23], enabling further efficiency gains for batched disjunctive statements.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. IEEE S&P 2025
Keywords
Zero-Knowledge Proofs
Contact author(s)
mengling liu @ connect polyu hk
yang2023 heng @ connect polyu hk
xing-ye lu @ polyu edu hk
man-ho-allen au @ polyu edu hk
History
2025-03-24: revised
2025-03-22: received
See all versions
Short URL
https://ia.cr/2025/533
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2025/533,
      author = {Mengling Liu and Yang Heng and Xingye Lu and Man Ho Au},
      title = {{JesseQ}: Efficient Zero-Knowledge Proofs for Circuits over Any Field},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/533},
      year = {2025},
      url = {https://eprint.iacr.org/2025/533}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.