RoKoko under Standard Assumptions

13 Sep 2026

“Standard assumptions” make the security of a cryptographic construction more believable. Those assumptions have been studied for decades across different applications, and we have a better understanding of the attacks and parameter choices. In contrast, new assumptions can enable a more efficient construction, but they also introduce a new problem to analyse. For lattice-based SNARKs, this motivates asking how much efficiency we gain from a specialised assumption, but also what the cost would be if we were to use standard assumptions instead.

RoKoko [KLNOT26] is a fully succinct SNARK for structured algebraic statements over cyclotomic rings. Its proofs are short, and verification takes time polylogarithmic in the witness size, practically in milliseconds. The construction relies on the vanishing \(\SIS\) (\(\vSIS\)) assumption, which may be perceived as non-standard. We believe in \(\vSIS\), but RoKoko can also be instantiated under standard \(\SIS\) assumptions and in this blogpost we show how to do it. Changing the commitment key gives a construction under \(\SIS\) that retains full succinctness i.e. the proof size and verifier remain polylogarithmic in the witness size.

Relation and Witness

The relation supported in RoKoko has a short witness matrix \(\mat{W}\in\ring^{m\times r}\), where \(\ring\) is a cyclotomic ring and \(\ring_q=\ring/q\ring\). In simplified form, the relation is

\[\Xilin_{\ring,q,n,m,r,B}\coloneqq \left\{ \begin{aligned} &\bigl((\mat{F},\mat{Y},f),\mat{W}\bigr) \\[0.5em] &\quad\begin{aligned} &\mat{F}\mat{W} = \mat{Y}, \\ &\sum_{\vec{z}\in\{0,1\}^{\nu}} f\!\left(\MLE[\vectorise(\mat{W})]\right)(\vec{z}) = 0, \\ &\norm{\mat{W}} \leq B \end{aligned} \end{aligned} \right\}.\]

Here \(\mat{F}\in\ring_q^{n\times m}\) is the public commitment key, \(\mat{Y}\in\ring_q^{n\times r}\) is the Ajtai commitment, \(B\) is the norm bound, and \(\nu=\log_2(m r)\). The algebraic equalities are over \(\ring_q\). The function \(f\) expresses an algebraic constraint of bounded degree. \(\MLE\) denotes the multilinear extension of a vector, and \(\vectorise(\cdot)\) flattens a matrix into a vector by stacking its columns. Public coefficients of \(f\) must admit sufficiently efficient evaluation for the verifier to remain succinct. A trivial example is a polynomial evaluation relation.

Linearisation, Folding and Recursion

Each round of RoKoko consists of two main steps: linearisation and folding. The first step reduces the algebraic claims to linear constraints on the witness. The second step reduces the witness size.

Linearisation means reducing the algebraic claims to linear constraints on the witness. Those algebraic claims concern not only the claims relevant to the input relation, but also the norm-checks and all constraints that arise from the protocol execution so far. We run sumcheck, which leaves evaluations of \(\MLE[\vectorise(\mat{W})]\) at verifier-chosen points. Splitting each point into column coordinates \(\vec{v}_R\) and row coordinates \(\vec{v}_L\) writes the evaluation as a left--right product:

\[\MLE[\vectorise(\mat{W})](\vec{v}_R,\vec{v}_L) =\lvec^{\transpose}\mat{W}\vec{r}=t, \qquad \lvec=\mletensor(\vec{v}_L), \quad \vec{r}=\mletensor(\vec{v}_R).\]

Here \(\mletensor\) forms the tensor of multilinear evaluation weights. The prover sends the intermediate row \(\vec{t}^{\transpose}=\lvec^{\transpose}\mat{W}\). The verifier checks the right-hand consistency \(\vec{t}^{\transpose}\vec{r}=t\) itself, leaving only the left-hand constraint \(\lvec^{\transpose}\mat{W}=\vec{t}^{\transpose}\) to prove. Collecting the left vectors into the rows of \(\mat{L}\) and the intermediate rows into \(\mat{T}\) gives

\[\mat{L}\mat{W}=\mat{T}, \qquad \mat{F}\mat{W}=\mat{Y}.\]

We can then fold the columns of \(\mat{W}\) using a low-norm challenge \(\vec{c}\in\Chall^r\). Linearity gives

\[\mat{L}\vec{v}=\mat{T}\vec{c}, \qquad \mat{F}\vec{v}=\mat{Y}\vec{c},\]

which are the constraints the verifier checks for \(\vec{v} = \mat{W}\vec{c}\) delivered by the prover.

To keep communication short, the prover re-commits to the large messages (including the folded witness \(\vec{v}\) itself) and expresses the verifier's algebraic checks using the same constraint system. The protocol recurses again. Repeating this process eventually reduces the witness to a small one that the verifier can read in full. One of the claims that the verifier checks is the commitment equation \(\mat{F}\vec{v}=\mat{Y} \vec{c}\). To check such a claim efficiently, the verifier needs to take advantage of the structure of the commitment key.

Commitment Structure

The commitment check \(\mat{F}\vec{v}=\mat{Y}\vec{c}\) is itself a claim that we handle with sumcheck. Each row of the equation is an inner product between a public key row and a witness. We express that inner product as a sum of products of their multilinear extensions. For an arbitrary dense key \(\mat{F}\in\ring_q^{n\times m}\), evaluating the multilinear extension of a row costs \(O(m)\) ring operations. That would make verification linear in the witness height. The \(\vSIS\) construction solves this by making each row a tensor product. For \(m=2^{\mu}\), its key has the form

\[\mat{F}=\mat{B}_0\rowtensor\cdots\rowtensor\mat{B}_{\mu-1}, \qquad \mat{B}_j\in\ring_q^{n\times 2},\]

where \(\rowtensor\) denotes the row-wise tensor product. If \(\vec{f}_i^{\transpose}\) is row \(i\) of \(\mat{F}\), then

\[\MLE[\vec{f}_i](\vec{z}) =\prod_{j\in[\mu]} \bigl((1-z_j)(\mat{B}_j)_{i,0} +z_j(\mat{B}_j)_{i,1}\bigr).\]

This takes only \(O(\mu)\) ring operations. Of course, such a friendly structure is not available under regular \(\SIS\) and the binding of such a commitment comes from the \(\vSIS\) assumption.

An alternative, following the block structure used in [CMNW24], is to repeat a short, uniformly random key along the diagonal. Let \(s\) be the number of blocks, \(d\) their width, and \(n_0\) the number of commitment rows per block. Sample \(\mat{A}\sample\ring_q^{n_0\times d}\) and set

\[\mat{F}=\mat{I}_s\otimes\mat{A} =\begin{pmatrix} \mat{A} & & \\ & \ddots & \\ & & \mat{A} \end{pmatrix}, \qquad m=sd, \quad n=sn_0.\]

Each block of witness rows is committed under the same uniformly random \(\mat{A}\). The repeated-block structure therefore preserves binding under a regular variant of \(\SIS\).

Here comes the trick to keep the verifier succinct. The verifier can read the short key \(\mat{A}\) once and reuse it across the blocks and take advantage of this succinct structure to evaluate the multilinear extension of the commitment key efficiently. More precisely, we batch them from the left with a tensor challenge. For simplicity, suppose \(s,d,n_0\) are powers of two. Let \(\vec{u}\) and \(\vec{v}\) be random points of lengths \(\log_2 s\) and \(\log_2 n_0\). Write \(\mletensor(\vec{x})=\bigotimes_j(1-x_j,x_j)^{\transpose}\) for the multilinear evaluation vector at \(\vec{x}\). Define

\[\vec{\gamma}=\mletensor(\vec{u})\otimes\mletensor(\vec{v}), \qquad \vec{a}^{\transpose}=\mletensor(\vec{v})^{\transpose}\mat{A}.\]

The mixed-product identity for tensor products gives

\[\begin{aligned} \vec{\gamma}^{\transpose}\mat{F} &=\bigl(\mletensor(\vec{u})^{\transpose} \otimes\mletensor(\vec{v})^{\transpose}\bigr) (\mat{I}_s\otimes\mat{A}) \\ &=\mletensor(\vec{u})^{\transpose}\otimes\vec{a}^{\transpose}. \end{aligned}\]

Only \(\vec{a}\) is dense, and it has length \(d\). More explicitly, let \(\lvec_F^{\transpose}=\vec{\gamma}^{\transpose}\mat{F}\) and split an evaluation point into block coordinates \(\vec{z}_B\) and within-block coordinates \(\vec{z}_D\). Then

\[\MLE[\lvec_F](\vec{z}_B,\vec{z}_D) =\eq(\vec{u},\vec{z}_B)\, \MLE[\vec{a}](\vec{z}_D),\]

where \(\eq(\vec{u},\vec{z}_B)=\prod_j((1-u_j)(1-z_{B,j})+u_jz_{B,j})\). Forming \(\vec{a}\) costs \(O(n_0d)\) ring operations, and evaluating this expression costs \(O(d+\log s)\). The verifier reads the small key once and reuses it across the blocks.

The batched commitment equation is

\[\bigl(\mletensor(\vec{u})^{\transpose} \otimes\vec{a}^{\transpose}\bigr)\mat{W} =\bigl(\mletensor(\vec{u})^{\transpose} \otimes\mletensor(\vec{v})^{\transpose}\bigr)\mat{Y} \pmod q.\]

Choosing the dense block dimensions polynomial in \(\lambda\) and \(\log(m r)\) keeps the verifier succinct. Shorter blocks produce more commitment images, but they do not increase the communication cost as those are committed anyway.

Concrete Performance

We tried the \(\SIS\) variant and kept roughly the same proof size and prover time, leaving the extra cost to the verifier. We ran the polynomial-opening benchmarks on the same Intel-based consumer-grade laptop used for the paper's experiments. In the table below, each entry reads \(x\to y\), where \(x\) is the \(\vSIS\) result and \(y\) the \(\SIS\) result. The implementation and benchmarks are available here.

As mentioned, the parameters are chosen to keep the proof size and prover time unaltered, which in practice means that the commitment-block sizes need to remain relatively large. Smaller blocks would decrease the verifier time, but also make each round less compressing (more rounds are needed to reach the target witness size) as the commitment matrix \(\mat{Y}\) (that is re-committed for the next round) grows with the number of blocks. More rounds means more prover time and more communication. Different trade-offs are possible, but we leave that for future work.

The work is currently not available on the main branch of the RoKoko repository. The reason is that the current setup of RoKoko requires hand-picking the parameters for each relation, and the \(\SIS\) variant requires a different set of parameters than the \(\vSIS\) variant, resulting in a lot of extra work to maintain both variants. We are working on a more flexible setup that would eliminate the need for hand-picking parameters altogether, and we will merge the \(\SIS\) variant once that is ready.

References

• [CMNW24]
  V. Cini, G. Malavolta, N. K. Nguyen, H. Wee; Polynomial Commitments from Lattices: Post-quantum Security, Fast Verification and Transparent Setup; Crypto 2024.
• [KLNOT26]
  M. Klooß, R. W. F. Lai, N. K. Nguyen, M. Osadnik, L. Tucci; RoKoko: Lattice-based Succinct Arguments, a Committed Refinement; Asiacrypt 2026.

For citation purposes, please use the following BibTeX entry: