Our paper – together with Valerio Cini, Russell W. F. Lai, Giulio Malavolta and Sri Aravinda Krishnan Thyagarajan – titled Lattice-Based SNARKs: Publicly Veriﬁable, Preprocessing, and Recursively Composable will be presented at CRYPTO’22. A pre-print is available and here’s the abstract:
A succinct non-interactive argument of knowledge (SNARK) allows a prover to produce a short proof that certifies the veracity of a certain NP-statement. In the last decade, a large body of work has studied candidate constructions that are secure against quantum attackers. Unfortunately, no known candidate matches the efficiency and desirable features of (pre-quantum) constructions based on bilinear pairings.
In this work, we make progress on this question. We propose the first lattice-based SNARK that simultaneously satisfies many desirable properties: It (i) is tentatively post-quantum secure, (ii) is publicly-verifiable, (iii) has a logarithmic-time verifier and (iv) has a purely algebraic structure making it amenable to efficient recursive composition. Our construction stems from a general technical toolkit that we develop to translate pairing-based schemes to lattice-based ones. At the heart of our SNARK is a new lattice-based vector commitment (VC) scheme supporting openings to constant-degree multivariate polynomial maps, which is a candidate solution for the open problem of constructing VC schemes with openings to beyond linear functions. However, the security of our constructions is based on a new family of lattice-based computational assumptions which naturally generalises the standard Short Integer Solution (SIS) assumption.
In this post, I want to give you a sense of our new family of assumptions, the k-M-ISIS family of assumptions, and its variants. Meanwhile, Russell has written a post focusing on building the SNARK and Aravind has written about the nice things that we can do with our lattice-based SNARKs.
Let’s start with an example:
Let , let and let be short s.t. for and . Given find a short s.t. .
That is, this problem asks you to solve the ring inhomogeneous short integer solutions problem (R-ISIS) but with the twist that you get a bunch of preimages of algebraically related (to the target) images. In the above example those algebraic relations can be expressed as that we are given preimages for evaluated at and we want to find one for evaluated at .
On the one hand, there are pairs that are trivially as hard as R-(I)SIS itself: for example and . Evaluating each element of at simply outputs , i.e. we are given short preimages of random images which are easily sampled by an adversary (pick a short and compute ). On th other hand, e.g. and is trivially insecure. So we need to define which pairs we admit and which we do not:
Let be a Laurent monomial, i.e. for some exponent vector . Let be a set of Laurent monomials with . Let be a target Laurent monomial. We call a family k-M-ISIS-admissible if
- all have constant degree, i.e. ;
- all are distinct, i.e. is not a multiset; and
We call a family k-M-ISIS-admissible if is k-MISIS-admissible, has constant degree, and .
To explain the conditions:
- Condition (1) rules out monomials that depend on the ring , such as .
- Condition (2) rules out that trivial linear combinations of known preimages produce a preimage for the target.
- Condition (3) rules out trivially producing multiple preimages of the same image.
Armed with this definition, we can define the k-M-ISIS problem (I am giving a slightly simplified version here).
Let . Let be a set of -variate Laurent monomial. Let be a target Laurent monomial. Let be k-M-ISIS-admissible. Let , . Given with short and
it is hard to find a short and small s.t.
When , i.e. when is just a vector, we call the problem k-R-ISIS.
We also define a “knowledge” variant of our assumption, which essentially states that for any element the adversary can produce together with a short preimage, it essentially produced that as some small linear combination of the preimages we have given it. Thus, roughly:
If an adversary outputs any s.t.
then there is an extractor that – with access to the adversary’s randomness – outputs short s.t.
The knowledge assumption only makes sense for , To see this, consider an adversary which does the following: First, it samples random short and checks whether is in the submodule of generated by . If not, aborts. If it does not abort, it finds such that and outputs . When , we observe that generates , which means never aborts. Clearly, when does not abort, it has no “knowledge” of how can be expressed as a linear combination of . Yet, when the adversary aborts with overwhelming probability since is close to uniform over but the submodule generated by is only a negligible faction of .
However, in order to be able to pun about “crises of knowledge”, we also define a ring version of the knowledge assumption. In the ring setting, we consider proper ideals rather than submodules.
What can it do?
To see why this might be a useful definition, start with some pairing-based scheme.
For example, consider constructions where the elements are publicly available to all parties. An authority, knowing the secret exponents , is responsible for giving out secret elements to Alice. Alice can then compute and present that to Bob. Bob can then check the correctness of by checking
This is a fairly common pairing-based pattern. Now, note that in this check one side of the pairing (i.e. ) is public, while the other side (i.e. ) is computed from secrets delegated by the authority to Alice. This gives us, at least syntactically (!), an angle to translate such constructions.
Note that since does not necessarily hide in the lattice setting (e.g. when consists of many linear functions), the authority might as well publicly hand out the vectors directly. We then map
Now, given , Alice can similarly compute , although the coefficients are now required to be short. The pairing-product check is then translated to checking
To see it in action, let’s build a vector commitment scheme with a functional opening, i.e. we can open to for a committed vector . To keep things simple I will consider , linear functions (we support any constant degree in our paper) and the simplified (non-knowledge) version of our scheme.
We let and .
- The now asks us to compute and for all , e.g. . We publish
- To to some we simply return .
- To we compute
- To we compute:
On the other hand, we have:
If k-R-ISIS is hard then this construction is weakly binding, meaning the adversary cannot open to two different values for the same . We can also achieve binding (no inconsistent openings) for if we allow to be exponentially large. To achieve binding for , we need the knowledge assumption. The intuition here is that solving the non-linear system of equations produced by inconsistent openings may be exponentially hard.
How hard is it?
As already mentioned above, there are instances of k-M-ISIS that are trivially as hard as M-ISIS. We formalise these reasons in the paper. Slightly more interestingly, we also show that if k-M-ISIS is easy when then k-R-SIS is easy. The latter is a generalisation of the k-SIS problem (EPRINT:BonFre10, EPRINT:LPSS14) which is as hard as SIS. However, it is worth stressing that , i.e. handing out fewer preimages than the dimension of , is not very interesting. Our applications certainly need .
On the other hand, we did not find any attacks better than just solving M-(I)SIS directly. In the paper, we also consider the approaches of finding a small integer linear combination or finding a linear combination s.t. is small.