Paper 2026/2943
A Transparent Post-Quantum Zero-Knowledge Argument for R1CS
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
-
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}
}