CryptoDB
RoK and Roll – Verifier-Efficient Random Projection for $\tilde{O}(\lambda)$-size Lattice Arguments
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| Abstract: | Succinct non-interactive arguments of knowledge (SNARKs) based on lattice assumptions offer a promising post-quantum alternative to pairing-based systems, but have until now suffered from inherently quadratic proof sizes in the security parameter. We introduce RoK and Roll, the first lattice-based SNARK that breaks the quadratic barrier, achieving communication complexity of $\tilde{O}(\lambda)$ together with a succinct verification time. The protocol significantly improves upon the state of the art of fully-succinct argument systems established by ``RoK, Paper, SISsors'' (RPS) [ASIACRYPT'24] and hinges on two key innovations, presented as reductions of knowledge (RoKs): - \emph{Structured random projections:} We introduce a new technique for structured random projections that allows us to reduce the witness dimensions while approximately preserving its $\ell_2$ norm and maintaining the desired tensor structure. Such a projection does not reduce the dimensions sufficiently so the image can be sent in plain, but instead, the projection is further committed and adjoined to the original relation. - \emph{Unstructured random projection:} Similarly to projections used in LaBRADOR [CRYPTO'23], when the witness is sufficiently small, we let the projection (over coefficients $\ZZ_q$) be sent in plain. However, immediately lifting the projection claim to $\mathcal{R}_q$ and into our relation (as in LaBRADOR) would impose a quadratic communication cost. Instead, we gradually batch-and-lift the projection over the tower of intermediate extensions.This allows us to reduce the communication cost to $\tilde{O}(\lambda)$, while maintaining a succinct verification time. These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity $\tilde{O}(\lambda)$ and succinct verification for structured linear relations. |
BibTeX
@inproceedings{asiacrypt-2025-36097,
title={RoK and Roll – Verifier-Efficient Random Projection for $\tilde{O}(\lambda)$-size Lattice Arguments},
publisher={Springer-Verlag},
author={Michael Klooss and Russell W. F. Lai and Ngoc Khanh Nguyen and Michał Osadnik},
year=2025
}