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 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 $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

all $g \in \mathcal{G}$ have constant degree, i.e. $\|\mathbf{e}\|_{1} \in O(1)$ ;

all $g \in \mathcal{G}$ are distinct, i.e. $\mathcal{G}$ is not a multiset; and

$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.

Let $\mathcal{G} := \{X_{0}/X_{1}, X_{1}/X_{0}\}$ .

The now asks us to compute and for all , e.g. . We publish ,
- $\mathbf{u}_{X_0/X_1} \textnormal{ with } \langle \mathbf{a} , \mathbf{u}_{X_0/X_1} \rangle= v_0/v_1$ and
- $\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}$ to the function evaluation $f(\mathbf{x}) = f_{(1,0)} \cdot x_0 + f_{(0,1)} \cdot x_1 = y$ , 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”

Pingback: Lattice-based SNARKs from kRISIS of Knowledge – Russell W. F. Lai – Personal Webpage

The k-R-ISIS (of Knowledge) Assumption

Definition

What can it do?

How hard is it?

Published by martinralbrecht

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

Leave a Reply Cancel reply

Definition

What can it do?

How hard is it?

Share this:

Like this:

Related

Published by martinralbrecht

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

Leave a Reply Cancel reply