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 -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 . More formally, the language is of the form
where is a tuple of degree- multivariate homogeneous (i.e. no constant term) polynomials with small coefficients in and is a short vector over . For concreteness, think of 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 of , and “open” it to any tuple of quadratic polynomials by producing a short proof . Given , , , and , the verifier could be convinced that indeed whatever that is committed in should satisfy . The tuple is thus a SNARK proof for . More on the precise security requirements of the VC later.
In the following, we construct a basic VC which supports openings to a single polynomial (instead of a tuple).
First, a trusted setup generates a random vectors and over for some modulus , together with a SIS trapdoor for . Such a trapdoor allows the setup to further generate short vectors over satisfying , for all rational functions for some set which will be specified later. The setup then publishes , , and the ‘s as public parameters.
To commit to a short vector over which has the same dimension as , the prover simply computes and outputs the inner product .
Before describing the opening algorithm, we first look at the verification algorithm instead. All we need to know about an opening proof for now is that it is a short vector over which has the same dimension as .
To verify against , the verifier defines the a quadratic polynomial as follows:
- Parse as .
- Define .
Then, it checks that are indeed short and satisfy .
From the verification equation, we can reverse engineer that the opening proof should be computed as
where the rational functions and are contained in . (Hence we have specified .) Since the coefficients of , the vector , and the vectors are short, the opening proof is also short, as desired.
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 and for , based on the following kRISIS assumption: Given , , and generated as in the setup, it is hard to find a short vector and a short element satisfying .
To see why this is the case, suppose an efficient adversary produces valid opening proofs satisfying for , by setting and , we have . Since are short, and 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 against , then it is guaranteed that the prover must “know” a satisfying such that is a commitment of and . To achieve extractability, we augment the basic construction as follows.
- Setup: The setup further generates another random vector over together with its SIS trapdoor, as well as a random element such that the ideal generated by has exponentially many elements yet only covers a negligible fraction of . Using the trapdoor of , the setup generates short vectors satisfying for each entry of . The public parameters now further consist of , , and the ‘s.
- Commit: Unchanged.
- Open: The prover further outputs .
- Verify: The verifier further checks that is short and satisfies .
We show that the modified construction satisfies extractability based on the following knowledge kRISIS assumption: Given , , , and the ‘s generated as in the setup, if an efficient algorithm is able to produce a short vector satisfying for some , then the algorithm is guaranteed to “know” a short vector such that .
Clearly, by the above knowledge kRISIS assumption, if a prover is able to produce a valid opening proof of against , then it must know a short vector such that is a commitment of . Now suppose that . We can run the opening algorithm to produce a valid opening proof of against . However, this means we can obtain valid opening proofs of against both and , 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 which is small compared to but still large compared to “short” vectors. The public parameters additionally contain a random vector over whose dimension is equal to the number of polynomials to be opened.
- Commit: Unchanged.
- Open: To open to , define and and run the previous opening algorithm to open to .
- Verify: To verify an opening proof against , define and and run the previous verification algorithm to verify .
We show that the third construction remains to be extractable based on the SIS assumption over . To recall, the SIS assumption states that for a random it is hard to find a short non-zero vector such that .
Suppose if a prover is able to produce a valid opening proof of against . Define and . By the extractability of the second scheme, the prover must know a short vector satisfying . Expanding the expression and reducing modulo gives . Note that is short for all . Therefore, if for some , we obtain a short non-zero vector such that , violating the SIS assumption.
Last Updated on 21/07/2022.
One thought on “Lattice-based SNARKs from kRISIS of Knowledge”