The k-R-ISIS (of Knowledge) Assumption

Our paper – together with Valerio Cini, Russell W. F. Lai, Giulio Malavolta and Sri Aravinda Krishnan Thyagarajan – titled Lattice-Based SNARKs: Publicly Verifiable, 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 v \gets_{\$} U(\mathcal{R}_q), let \mathbf{a} \in \mathcal{R}_{q}^{\ell} and let \mathbf{u}_{i} \in \mathcal{R}^{\ell} be short s.t. v^{i} = \left\langle \mathbf{a},\mathbf{u}_{i} \right\rangle for 1 \leq i < b and b+1 \leq i < 2b. Given (\mathbf{a}, \{\mathbf{u}_{i}\}) find a short \mathbf{u}^{\star} s.t. \left\langle \mathbf{a},\mathbf{u}^{\star} \right\rangle = v^{b}.

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 \mathcal{G} := \{X,X^2 ,\ldots, X^{b-1}, X^{b+1}, \ldots, X^{2b}\} evaluated at v and we want to find one for g^* := X^{b} evaluated at v.

Definition

On the one hand, there are pairs (\mathcal{G}, g^{\star}) that are trivially as hard as R-(I)SIS itself: for example \mathcal{G} := \{X_0,X_1,X_2,\ldots, X_{k-1}\} and g^{\star} := 0. Evaluating each element of \mathcal{G} at \mathbf{v} \gets_{\$} \mathcal{R}_{q}^{k} simply outputs \{v_0,v_1,v_2,\ldots, v_{k-1}\}, i.e. we are given short preimages of random images which are easily sampled by an adversary (pick a short \mathbf{u}_{i} and compute v_{i} := \left\langle \mathbf{a}, \mathbf{u}_{i} \right\rangle). On th other hand, e.g. \mathcal{G} := \{X\} and g^{\star} := X is trivially insecure. So we need to define which pairs (\mathcal{G},g^{\star}) we admit and which we do not:

Let g(\mathbf{X}) \in \mathcal{R}(\mathbf{X}) be a Laurent monomial, i.e. g(\mathbf{X}) = \mathbf{X}^{\mathbf{e}} := \prod_{i \in \mathbb{Z}_w} X_i^{e_i} for some exponent vector \mathbf{e} = (e_i: i \in \mathbb{Z}_w) \in \mathbb{Z}^w. Let \mathcal{G} \subset \mathcal{R}(\mathbf{X}) be a set of Laurent monomials with k := |\mathcal{G}|. Let g^{\star} \in \mathcal{R}(\mathbf{X}) be a target Laurent monomial. We call a family \mathcal{G} k-M-ISIS-admissible if

  1. all g \in \mathcal{G} have constant degree, i.e. \|\mathbf{e}\|_{1} \in O(1);
  2. all g \in \mathcal{G} are distinct, i.e. \mathcal{G} is not a multiset; and
  3. 0 \not\in\mathcal{G}.

We call a family (\mathcal{G}, g^*) k-M-ISIS-admissible if \mathcal{G} is k-MISIS-admissible, g^* has constant degree, and g^* \notin \mathcal{G}.

To explain the conditions:

  • Condition (1) rules out monomials that depend on the ring \mathcal{R}, such as X^{\phi(m)}.
  • 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 \mathbf{t} = (1,0,\ldots,0). Let \mathcal{G} \subset \mathcal{R}(\mathbf{X}) be a set of w-variate Laurent monomial. Let g^{\star} \in \mathcal{R}(\mathbf{X}) be a target Laurent monomial. Let (\mathcal{G},g^\star) be k-M-ISIS-admissible. Let \mathbf{A} \gets_{\$} \mathcal{R}_q^{\eta \times \ell}, \mathbf{v} \gets_{\$} (\mathcal{R}_q^\star)^w. Given (\mathbf{A}, \{\mathbf{u}_{g}\}) with \mathbf{u}_{g} short and

g(\mathbf{v}) \cdot \mathbf{t} \equiv \mathbf{A}\cdot \mathbf{u}_{g} \bmod q

it is hard to find a short \mathbf{u}_{g^*} and small s^{*} s.t.

s^* \cdot g^{*}(\mathbf{v}) \cdot \mathbf{t} \equiv \mathbf{A} \cdot \mathbf{u}_{g^*} \bmod q.

When \eta = 1, i.e. when \mathbf{A} 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 c \cdot \mathbf{t} the adversary can produce together with a short preimage, it essentially produced that as some small linear combination of the preimages \{\mathbf{u}_{g}\} we have given it. Thus, roughly:

If an adversary outputs any c, \mathbf{u}_{c} s.t.

c \cdot \mathbf{t} \equiv \mathbf{A} \cdot \mathbf{u}_{c} \bmod q

then there is an extractor that – with access to the adversary’s randomness – outputs short \{c_{g}\} s.t.

c \equiv \sum_{g \in \mathcal{G}} c_{g} \cdot g(\mathbf{v}) \bmod q.

The knowledge assumption only makes sense for \eta \geq 2, To see this, consider an adversary \mathcal{A} which does the following: First, it samples random short \mathbf{u} and checks whether \mathbf{A} \cdot \mathbf{u} is in the submodule of \mathcal{R}_q^{\eta} generated by \mathbf{t}. If not, \mathcal{A} aborts. If it does not abort, it finds c such that \mathbf{A} \cdot \mathbf{u} = c \cdot \mathbf{t} \bmod q and outputs (c,\mathbf{u}). When \eta = 1, we observe that t = 1 generates \mathcal{R}_q, which means \mathcal{A} never aborts. Clearly, when \mathcal{A} does not abort, it has no “knowledge” of how c can be expressed as a linear combination of \{g(\mathbf{v})\}_{g \in \mathcal{G}}. Yet, when \eta \geq 2 the adversary \mathcal{A} aborts with overwhelming probability since \mathbf{A} \cdot \mathbf{u} is close to uniform over \mathcal{R}_q^\eta but the submodule generated by \mathbf{t} is only a negligible faction of \mathcal{R}_q^\eta.

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 \{{[1]}_1, {[g(\mathbf{v})]}_t\}_{g \in \mathcal{G}} are publicly available to all parties. An authority, knowing the secret exponents \mathbf{v}, is responsible for giving out secret elements \{{[g(\mathbf{v})]}_2\}_{g \in \mathcal{G}} to Alice. Alice can then compute {[u]}_2 := \sum_{g \in \mathcal{G}} c_g \cdot {[g(\mathbf{v})]}_2 and present that to Bob. Bob can then check the correctness of {[u]}_2 by checking

\left\langle {{[1]}_1}, {{[u]}_2} \right\rangle ?= \sum_{g \in \mathcal{G}} c_g \cdot {[g(\mathbf{v})]}_t.

This is a fairly common pairing-based pattern. Now, note that in this check one side of the pairing (i.e. {[1]}_1) is public, while the other side (i.e. {[u]}_2) is computed from secrets delegated by the authority to Alice. This gives us, at least syntactically (!), an angle to translate such constructions.

We map

{[1]}_1 \rightarrow \mathbf{a}

and

\{{[g(\mathbf{v})]}_t\}_{g \in \mathcal{G}} \rightarrow g(\mathbf{v})_{g \in \mathcal{G}}.

Note that since \{g(\mathbf{v})\}_{g \in \mathcal{G}} does not necessarily hide \mathbf{v} in the lattice setting (e.g. when \mathcal{G} consists of many linear functions), the authority might as well publicly hand out the vectors \{\mathbf{a}, \mathbf{v}\} directly. We then map

\{{[g(\mathbf{v})]}_2\}_{g \in \mathcal{G}} \rightarrow \mathbf{u}_{g}.

Now, given \{\mathbf{u}_g\}_{g \in \mathcal{G}}, Alice can similarly compute \mathbf{u} := \sum_{g \in \mathcal{G}} \cdot c_g \cdot \mathbf{u}_g, although the coefficients c_g are now required to be short. The pairing-product check is then translated to checking

\left\langle \mathbf{a}, \mathbf{u} \right\rangle ?\equiv \sum_{g \in \mathcal{G}} \cdot c_g \cdot g(\mathbf{v}) \bmod q \quad\text{and}\quad \mathbf{u} \text{ is short.}

To see it in action, let’s build a vector commitment scheme with a functional opening, i.e. we can open to f(\mathbf{x}) for a committed vector \mathbf{x}. To keep things simple I will consider \mathbf{x} \in \mathcal{R}^{2}, linear functions (we support any constant degree f() in our paper) and the simplified (non-knowledge) version of our scheme.

We let \mathcal{G} := \{X_{0}/X_{1}, X_{1}/X_{0}\} and f(\mathbf{x}) = f_{(1,0)} \cdot x_0 + f_{(0,1)} \cdot x_1 = y.

  • The \mathsf{Setup} now asks us to compute \mathbf{v} \gets \mathcal{R}_q^{w} and g(\mathbf{v}) for all g \in \mathcal{G}, e.g. v_0/v_1. We publish
    • (\mathbf{a}, \mathbf{u}_{(X_0/X_1)}) \textnormal{ with } \langle \mathbf{a} , \mathbf{u}_{X_0/X_1} \rangle= v_0/v_1
    • (\mathbf{a}, \mathbf{u}_{(X_1/X_0)}) \textnormal{ with } \langle \mathbf{a} , \mathbf{u}_{X_1/X_0} \rangle= v_1/v_0
  • To \mathsf{Commit} to some \mathbf{x} we simply return c := \langle\mathbf{v}, \mathbf{x}\rangle.
  • To \mathsf{Open} we compute

    \mathbf{u} = f_{(1,0)} \cdot x_1 \cdot \mathbf{u}_{X_0/X_1} + f_{(0,1)} \cdot x_0 \cdot \mathbf{u}_{X_1/X_0}.

  • To \mathsf{Verify} we compute: \tilde{f}(c \cdot (1/v_0, 1/v_1)) :=  f((v_0 \cdot x_0 + v_1 \cdot x_1) \cdot (1/v_0, 1/v_1)) - y
    = f_{(1,0)} \cdot (v_0 \cdot x_0 + v_1 \cdot x_1)/v_0 + f_{(0,1)} \cdot (v_0 \cdot x_0 + v_1 \cdot x_1)/v_1 - y
    = f_{(1,0)} \cdot (x_0 + v_1/v_0 \cdot x_1) + f_{(0,1)} \cdot (v_0/v_1 \cdot x_0 + x_1) - y
    On the other hand, we have:
    \langle \mathbf{a} , \mathbf{u} \rangle =\ \langle \mathbf{a}, f_{(1,0)} \cdot x_1 \cdot \mathbf{u}_{X_0/X_1} \rangle +  \langle \mathbf{a}, f_{(0,1)} \cdot x_0 \cdot \mathbf{u}_{X_1/X_0} \rangle
    =\  f_{(1,0)} \cdot x_1 \cdot \langle \mathbf{a}, \mathbf{u}_{X_0/X_1} \rangle +  f_{(0,1)} \cdot x_0 \cdot \langle \mathbf{a}, \mathbf{u}_{X_1/X_0} \rangle
    =\  f_{(1,0)} \cdot x_1 \cdot v_0/v_1 +  f_{(0,1)} \cdot x_0 \cdot v_1/v_0
    and get
    \tilde{f}(c \cdot (1/v_0, 1/v_1)) - \langle \mathbf{a}, \mathbf{u} \rangle =\ f_{(1,0)} \cdot (x_0 + v_1/v_0 \cdot x_1) + f_{(0,1)} \cdot (v_0/v_1 \cdot x_0 + x_1)
    - f_{(1,0)} \cdot x_1 \cdot v_0/v_1 - f_{(0,1)} \cdot x_0 \cdot v_1/v_0 - y
    = f_{(1,0)} \cdot x_0 + f_{(0,1)} \cdot x_1 - y = 0

If k-R-ISIS is hard then this construction is weakly binding, meaning the adversary cannot open to two different values for the same f. We can also achieve binding (no inconsistent openings) for d=1 if we allow q to be exponentially large. To achieve binding for d>1, 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 k < \ell 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 k < \ell, i.e. handing out fewer preimages than the dimension of \mathbf{a}, is not very interesting. Our applications certainly need k \gg \ell.

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 g^{\star}(\mathbf{v}) \equiv \sum c_{g} \cdot g(\mathbf{v}) or finding a linear combination g^{\star}(\mathbf{v}) \equiv \sum c_{g} \cdot g(\mathbf{v}) s.t. \mathbf{u}^{*} \equiv \sum c_{g} \cdot \mathbf{u}_{g} is small.

One thought on “The k-R-ISIS (of Knowledge) Assumption

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s