Lattice-based SNARKs from kRISIS of Knowledge

Our paper, Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable, together with Martin R. Albrecht, Valerio Cini, Giulio Malavolta and Sri AravindaKrish-nan Thyagarajan will be presented at CRYPTO’22. There, we build what is suggested in the title based on new families of lattice-based assumptions which we call $k$ -Ring Inhomogeneous Short Integer Solution (k-R-ISIS) and their knowledge variants, k-R-ISIS of Knowledge. These are natural generalisations of the now standard SIS assumption.

Martin has written a gentle introduction of the k-R-ISIS (of Knowledge) assumptions, and Aravind has written about cool things that one could do with our lattice-based SNARKs. In this post, I want to walk you through the construction of our lattice-based SNARKs.

Succinct Non-Interactive Arguments of Knowledge (SNARK)

Succinct non-interactive argument of knowledge (SNARK) allows a prover to convince a verifier about the veracity of statements of an NP-complete language by writing down very short proofs. Our NP-complete language of choice is the satisfiability of systems of quadratic (constant degree in general) equations with bounded coefficients and bounded solutions over certain ring $\ring$ . More formally, the language is of the form

$\set{(f,\vec{y}): \exists~\vec{x},~f(\vec{x}) = \vec{y}}$

where $f$ is a tuple of degree- $2$ multivariate homogeneous (i.e. no constant term) polynomials with small coefficients in $\ring$ and $\vec{x}$ is a short vector over $\ring$ . For concreteness, think of $\ring$ as being the ring of integers of some cyclotomic field.

Vector Commitments (VC)

Instead of building a SNARK, we actually build something even more powerful — a vector commitment (VC) scheme with openings to quadratic polynomials, also known as functional commitments. Such a VC scheme allows the prover to produce a succinct commitment $c$ of $\vec{x}$ , and “open” it to any tuple of quadratic polynomials $f$ by producing a short proof $\pi$ . Given $c$ , $f$ , $\vec{y} = f(\vec{x})$ , and $\pi$ , the verifier could be convinced that indeed whatever $\vec{x}$ that is committed in $c$ should satisfy $f(\vec{x}) = \vec{y}$ . The tuple $(c, \pi)$ is thus a SNARK proof for $(f,\vec{y})$ . More on the precise security requirements of the VC later.

Basic Construction

In the following, we construct a basic VC which supports openings to a single polynomial $f$ (instead of a tuple).

Setup

First, a trusted setup generates a random vectors $\vec{a}$ and $\vec{v}$ over $\ring_q := \ring/q\ring$ for some modulus $q$ , together with a SIS trapdoor for $\vec{a}$ . Such a trapdoor allows the setup to further generate short vectors $\vec{u}_g$ over $\ring$ satisfying $\inner{\vec{a}}{\vec{u}_g} = g(\vec{v}) \bmod q$ , for all rational functions $g \in \mathcal{G}$ for some set $\mathcal{G}$ which will be specified later. The setup then publishes $\vec{a}$ , $\vec{v}$ , and the $\vec{u}_g$ ‘s as public parameters.

Commit

To commit to a short vector $\vec{x}$ over $\ring$ which has the same dimension as $\vec{v}$ , the prover simply computes and outputs the inner product $c = \inner{\vec{v}}{\vec{x}} \bmod q$ .

Verify

Before describing the opening algorithm, we first look at the verification algorithm instead. All we need to know about an opening proof $\pi$ for now is that it is a short vector $\vec{u}$ over $\ring$ which has the same dimension as $\vec{a}$ .

To verify $(c, \pi)$ against $(f,y)$ , the verifier defines the a quadratic polynomial $\hat{f}_y(C)$ as follows:

Parse $f = f(\vec{V})$ as $\sum_i f_{i} \cdot V_i + \sum_{i,j} f_{i,j} \cdot V_i \cdot V_j$ .
Define $\hat{f}_y(C) := (2 \sum_i f_{i} \cdot v_i^{-1}) \cdot C + (\sum_{i,j} f_{i,j} \cdot v_i^{-1} \cdot v_j^{-1}) \cdot C^2 - 2y$ .
Then, it checks that $\vec{u}, f, y$ are indeed short and satisfy $\inner{\vec{a}}{\vec{u}} = \hat{f}_y(c) \bmod q$ .

Open

From the verification equation, we can reverse engineer that the opening proof $\vec{u}$ should be computed as

$\vec{u} = 2 \sum_{i \neq i'} f_{i} \cdot x_{i'} \cdot \vec{u}_{\frac{V_{i'}}{V_i}} + \sum_{{i,j} \neq {i',j'}} f_{i,j} \cdot x_{i'} \cdot x_{j'} \cdot \vec{u}_{\frac{V_{i'} \cdot V_{j'}}{V_i \cdot V_j}},$

where the rational functions $V_{i'}/V_i$ and $(V_{i'} \cdot V_{j'})/(V_i \cdot V_j)$ are contained in $\mathcal{G}$ . (Hence we have specified $\mathcal{G}$ .) Since the coefficients of $f$ , the vector $\vec{x}$ , and the vectors $\vec{u}_g$ are short, the opening proof $\vec{u}$ is also short, as desired.

Weak Binding

We show that the above basic construction satisfies a security notion called weak binding, meaning that it is infeasible for a prover to produce valid opening proofs for $(f,y_0)$ and $(f,y_1)$ for $y_0 \neq y_1$ , based on the following kRISIS assumption: Given $\vec{a}$ , $\vec{v}$ , and $(\vec{u}_g)_{g\in \mathcal{G}}$ generated as in the setup, it is hard to find a short vector $\vec{u}^*$ and a short element $s^*$ satisfying $\inner{\vec{a}}{\vec{u}^*} = s^* \bmod q$ .

To see why this is the case, suppose an efficient adversary produces valid opening proofs $\vec{u}_b$ satisfying $\inner{\vec{a}}{\vec{u}_b} = \hat{f}_{y_b}(c) \bmod q$ for $b \in {0,1}$ , by setting $\vec{u}^* = \vec{u}_0 - \vec{u}_1$ and $s^* = 2 (y_1 - y_0)$ , we have $\inner{\vec{a}}{\vec{u}^*} = s^* \bmod q$ . Since $\vec{u}_0, \vec{u}_1, y_0, y_1$ are short, $\vec{u}^*$ and $s^*$ are also short. We thus have an efficient algorithm for the above kRISIS problem, which we assumed to be hard.

From Weak Binding to Extractability

As the name suggests, the weak binding property is weak. In particular, it is insufficient to give a SNARK. What we need instead is extractability, meaning that if a prover is able to produce a valid opening proof of $c$ against $(f,y)$ , then it is guaranteed that the prover must “know” a satisfying $\vec{x}$ such that $c$ is a commitment of $\vec{x}$ and $f(\vec{x}) = y$ . To achieve extractability, we augment the basic construction as follows.

Setup: The setup further generates another random vector $\vec{a}'$ over $\ring_q$ together with its SIS trapdoor, as well as a random element $t \in \ring_q$ such that the ideal $\langle t \rangle$ generated by $t$ has exponentially many elements yet only covers a negligible fraction of $\ring_q$ . Using the trapdoor of $\vec{a}'$ , the setup generates short vectors $\vec{u}'_i$ satisfying $\inner{\vec{a}'}{\vec{u}'_i} = t \cdot v_i \bmod q$ for each entry $v_i$ of $\vec{v}_i$ . The public parameters now further consist of $\vec{a}'$ , $t$ , and the $\vec{u}'_i$ ‘s.
Commit: Unchanged.
Open: The prover further outputs $\vec{u}' = \sum_i x_i \cdot \vec{u}'_i$ .
Verify: The verifier further checks that $\vec{u}'$ is short and satisfies $\inner{\vec{a}'}{\vec{u}'} = t \cdot c \bmod q$ .

We show that the modified construction satisfies extractability based on the following knowledge kRISIS assumption: Given $\vec{a}'$ , $t$ , $\vec{v}$ , and the $\vec{u'}_i$ ‘s generated as in the setup, if an efficient algorithm is able to produce a short vector $\vec{u}'$ satisfying $\inner{\vec{a}'}{\vec{u}'} = t \cdot c \bmod q$ for some $c$ , then the algorithm is guaranteed to “know” a short vector $\vec{x}$ such that $c = \inner{\vec{x}}{\vec{v}} \bmod q$ .

Clearly, by the above knowledge kRISIS assumption, if a prover is able to produce a valid opening proof of $c$ against $(f,y)$ , then it must know a short vector $\vec{x}$ such that $c = \inner{\vec{x}}{\vec{v}} \bmod q$ is a commitment of $\vec{x}$ . Now suppose that $f(\vec{x}) = y' \neq y$ . We can run the opening algorithm to produce a valid opening proof of $c$ against $(f,y')$ . However, this means we can obtain valid opening proofs of $c$ against both $(f,y)$ and $(f,y')$ , which contradicts weak binding.

Opening to Multiple Polynomials

It remains to further upgrade the construction so as to support opening to not only one but a tuple of polynomials. For this, we further modify our construction as follows.

Setup: Pick a moderate size modulus $p$ which is small compared to $q$ but still large compared to “short” vectors. The public parameters additionally contain a random vector $\vec{h}$ over $\ring_p$ whose dimension is equal to the number of polynomials to be opened.
Commit: Unchanged.
Open: To open to $((f_0,\ldots,f_{t-1}), (y_0,\ldots,y_{t-1}))$ , define $f := \sum_i h_i f_i$ and $y = \sum_i h_i y_i$ and run the previous opening algorithm to open to $(f,y)$ .
Verify: To verify an opening proof against $((f_0,\ldots,f_{t-1}), (y_0,\ldots,y_{t-1}))$ , define $f := \sum_i h_i f_i$ and $y = \sum_i h_i y_i$ and run the previous verification algorithm to verify $(f,y)$ .

We show that the third construction remains to be extractable based on the SIS assumption over $\ring_p$ . To recall, the SIS assumption states that for a random $\vec{h}$ it is hard to find a short non-zero vector $\vec{u}$ such that $\inner{\vec{h}}{\vec{u}} = 0 \bmod p$ .

Suppose if a prover is able to produce a valid opening proof of $c$ against $((f_0,\ldots,f_{t-1}), (y_0,\ldots,y_{t-1}))$ . Define $f := \sum_i h_i f_i$ and $y = \sum_i h_i y_i$ . By the extractability of the second scheme, the prover must know a short vector $\vec{x}$ satisfying $f(\vec{x}) = y$ . Expanding the expression and reducing modulo $p$ gives $\sum_i h_i (f_i(\vec{x}) - y_i) = 0 \bmod p$ . Note that $f_i(\vec{x}) - y_i$ is short for all $i$ . Therefore, if $f_i(\vec{x}) \neq y_i$ for some $i$ , we obtain a short non-zero vector $\vec{u}$ such that $\inner{\vec{h}}{\vec{u}} = 0 \bmod p$ , violating the SIS assumption.