Paper 2022/1341
LaBRADOR: Compact Proofs for R1CS from Module-SIS
Abstract
The most compact quantum-safe proof systems for large circuits are PCP-type systems such as Ligero, Aurora, and Shockwave, that only use weak cryptographic assumptions, namely hash functions modeled as random oracles. One would expect that by allowing for stronger assumptions, such as the hardness of Module-SIS, it should be possible to design more compact proof systems. But alas, despite considerable progress in lattice-based proofs, no such proof system was known so far. We rectify this situation by introducing a Lattice-Based Recursively Amortized Demonstration Of R1CS (LaBRADOR), with more compact proof sizes than known hash-based proof systems, both asymptotically and concretely for all relevant circuit sizes. LaBRADOR proves knowledge of a solution for an R1CS mod $2^{64}+1$ with $2^{20}$ constraints, with a proof size of only 58 KB, an order of magnitude more compact than previous quantum-safe proofs.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- lattice-based proof system r1cs
- Contact author(s)
-
ward @ beullens com
gseiler @ posteo net - History
- 2022-10-10: approved
- 2022-10-07: received
- See all versions
- Short URL
- https://ia.cr/2022/1341
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1341,
author = {Ward Beullens and Gregor Seiler},
title = {LaBRADOR: Compact Proofs for R1CS from Module-SIS},
howpublished = {Cryptology ePrint Archive, Paper 2022/1341},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1341}},
url = {https://eprint.iacr.org/2022/1341}
}
