Paper 2026/2943

A Transparent Post-Quantum Zero-Knowledge Argument for R1CS

Vu Hung Tung
Abstract

We construct a transparent, post-quantum zero-knowledge argument of knowledge for R1CS. Satisfiability of $n$ constraints is reduced by two masked sumchecks to linear claims on a committed short vector; every field element the prover reveals is uniform. The witness is committed row-wise with Module-SIS (Ajtai) commitments; evaluation claims are proven by folding the rows with monomial challenges, whose differences have short scaled inverses, so that the extraction norm grows only singly exponentially in the folding depth. The row commitments and partial evaluations are moved into the witness of a LaBRADOR proof and replaced by two short outer commitments, so the proof has size polylogarithmic in $n$. The verifier runs in time $\tilde O(\sqrt n)\cdot\mathrm{poly}(\lambda)$ plus $T_\mathrm{circ}$, the time to evaluate the multilinear extensions of the constraint matrices, which we bound for data-parallel circuits. We prove completeness, knowledge soundness of the interactive protocol, and classical zero-knowledge in the programmable random-oracle model, and give parameters from a Core-SVP estimate. The concrete verifier cost at $n=2^{20}$ exceeds that of checking the circuit directly; the gain is asymptotic. Soundness of the Fiat--Shamir compiled protocol and a quantum-oracle zero-knowledge bound are not proven.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
post-quantumzero-knowledgesumcheckModule-SISR1CSlattice commitments
Contact author(s)
s1rjam3s2006 @ gmail com
History
2026-11-22: approved
2026-11-19: received
See all versions
Short URL
https://ia.cr/2026/2943
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2943,
      author = {Vu Hung Tung},
      title = {A Transparent Post-Quantum Zero-Knowledge Argument for {R1CS}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2943},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2943}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.