SIS with Hints Zoo

(Boneh & Freeman, 2011)

We give the module variant defined in (Albrecht, Cini, Lai, Malavolta, & Thyagarajan, 2022). We recover the original definition by setting $\mathcal{R}:=\mathbb{Z}$.

For any integer $k\ge 0$, an instance of the k-M-SIS problem is a matrix $\mathbf{A}\in {\mathcal{R}}_q^{\eta \times \ell }$ and a set of $k$ vectors ${\mathbf{u}}_0,\dots {\mathbf{u}}_{k-1}$ s.t. $\mathbf{A}\cdot {\mathbf{u}}_i\equiv \mathbf{0}modq$ with $\Vert {\mathbf{u}}_i\Vert \le \beta$. A solution to the problem is a nonzero vector $\mathbf{u}\in {\mathcal{R}}^{\ell }$ such that

$$\Vert \mathbf{u}\Vert \le {\beta }^{\ast },\mathbf{A}\cdot \mathbf{u}\equiv \mathbf{0}modq,\text{and}\mathbf{u}\notin \mathcal{K}\text{-}\mathrm{span}({\{{\mathbf{u}}_i\}}_{0\le i<k}).$$

An LWE variant, called k-LWE was introduced in (Ling, Phan, Stehlé, & Steinfeld, 2014).

(Agrawal, Kirshanova, Stehlé, & Yadav, 2022)

A challenger selects a matrix $\mathbf{A}\in {\mathbb{Z}}_q^{\eta \times \ell }$ and sends it to the adversary. The adversary can perform two types of queries:

Syndrome queries The adversary can request a challenge vector which the challenger selects at random, i.e. $\mathbf{t}{\leftarrow }_{\mathrm{\$}}{\mathbb{Z}}_q^{\eta }$, adds to some set $\mathcal{S}$ and returns to the adversary.

Preimage queries. The adversary submits any vector ${\mathbf{t}}^{\prime }\in {\mathbb{Z}}_q^{\eta }$. The challenger will return a short vector ${\mathbf{y}}^{\prime }{\leftarrow }_{\mathrm{\$}}{D}_{{\mathbb{Z}}^{\ell },\sigma }$ such that $\mathbf{A}\cdot {\mathbf{y}}^{\prime }\equiv {\mathbf{t}}^{\prime }modq$. Denote $k$ for the number of preimage queries.

In the end the adversary is asked to output $k+1$ pairs $\{({\mathbf{y}}_i,{\mathbf{t}}_i){\}}_{0\le i<k+1}$ satisfying: $$\mathbf{A}\cdot {\mathbf{y}}_i\equiv {\mathbf{t}}_{i}modq,\Vert {\mathbf{y}}_i\Vert \le \beta \text{ and }{\mathbf{t}}_i\in \mathcal{S}.$$

(Albrecht, Cini, Lai, Malavolta, & Thyagarajan, 2022)

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. $\Vert \mathbf{e}{\Vert }_1\in O(1)$;
2. all $g\in \mathcal{G}$ are distinct, i.e. $\mathcal{G}$ is not a multiset; and
3. $0\notin \mathcal{G}$.

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

Now, let $\mathbf{t}=(1,0,\dots ,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}{\leftarrow }_{\mathrm{\$}}{\mathcal{R}}_q^{\eta \times \ell }$, $\mathbf{v}{\leftarrow }_{\mathrm{\$}}({\mathcal{R}}_q^{\star }{)}^w$. The K-M-ISIS assumption states that given $(\mathbf{A},\mathbf{v},\mathbf{t},\{{\mathbf{u}}_g\})$ with ${\mathbf{u}}_g$ short and $$g(\mathbf{v})\cdot \mathbf{t}\equiv \mathbf{A}\cdot {\mathbf{u}}_{g}modq$$ it is hard to find a short ${\mathbf{u}}_{g^{\ast }}$ and small $s^{\ast }$ s.t. $$s^{\ast }\cdot g^{\ast }(\mathbf{v})\cdot \mathbf{t}\equiv \mathbf{A}\cdot {\mathbf{u}}_{g^{\ast }}modq.$$ When $\eta =1$, i.e. when $\mathbf{A}$ is just a vector, we call the problem k-R-ISIS.

(Albrecht, Cini, Lai, Malavolta, & Thyagarajan, 2022)

The assumption essentially states that for any element $c\cdot \mathbf{t}$ that the adversary can produce together with a short preimage, it 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}modq$$ 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})modq.$$

The knowledge assumption only makes sense for $\eta \ge 2$. However, in order to be able to pun about "crises of knowledge", the authors also define a ring version of the knowledge assumption. In the ring setting, they consider proper ideals rather than submodules.

(Balbás, Catalano, Fiore, & Lai, 2022)

let $\mathbf{t}=(1,0,\dots ,0)$. Let ${\mathcal{G}}_A,{\mathcal{G}}_B\subset \mathcal{R}(\mathbf{X})$ be sets of $w$-variate Laurent monomial. Let $({\mathcal{G}}_A\cup {\mathcal{G}}_B)$ be k-M-ISIS-admissible. Let $\mathbf{A}{\leftarrow }_{\mathrm{\$}}{\mathcal{R}}_q^{\eta \times \ell }$, $\mathbf{B}{\leftarrow }_{\mathrm{\$}}{\mathcal{R}}_q^{\eta \times \ell }$, $\mathbf{v}{\leftarrow }_{\mathrm{\$}}({\mathcal{R}}_q^{\star }{)}^w$. The Twin K-M-ISIS assumption states that given $(\mathbf{A},\mathbf{B},\{{\mathbf{u}}_g{\}}_{g\in {\mathcal{G}}_A},\{{\mathbf{w}}_g{\}}_{g\in {\mathcal{G}}_B},\mathbf{t},\mathbf{v})$ with ${\mathbf{u}}_g,{\mathbf{w}}_g$ short, $$g(\mathbf{v})\cdot \mathbf{t}\equiv \mathbf{A}\cdot {\mathbf{u}}_{g}modq,\mathrm{\forall }g\in {\mathcal{G}}_A,$$ and $$g(\mathbf{v})\cdot \mathbf{t}\equiv \mathbf{B}\cdot {\mathbf{w}}_{g}modq,\mathrm{\forall }g\in {\mathcal{G}}_B$$ it is hard to find a short ${\mathbf{u}}^{\ast },{\mathbf{w}}^{\ast }$ s.t. $$\mathbf{0}\equiv \mathbf{A}\cdot {\mathbf{u}}^{\ast }+\mathbf{B}\cdot {\mathbf{w}}^{\ast }modq.$$

(Wee & Wu, 2023b)

We consider BASIS${}_{rand}$ with $k=2$, for simplicity.

Let $\mathbf{A}\in {\mathbb{Z}}_q^{\eta \times \ell }$. We're given $$\mathbf{B}:=\left(\begin{array}{ccc}{\mathbf{A}}_0& \mathbf{0}& -{\mathbf{G}}_{\eta +1}\\ \mathbf{0}& {\mathbf{A}}_1& -{\mathbf{G}}_{\eta +1}\end{array}\right)$$ and a short $\mathbf{T}$ s.t. $${\mathbf{G}}_{{\eta }^{\prime }}\equiv \mathbf{B}\cdot \mathbf{T}modq$$ where ${\mathbf{A}}_i$ are uniformly random for $i>0$ and ${\mathbf{A}}_0:=[\mathbf{a}|{\mathbf{A}}^T{]}^T$ for uniformly random $\mathbf{A}$ and $\mathbf{a}$.

The BASIS${}_{rand}$ assumption states that given $(\mathbf{B},\mathbf{T})$ it is hard to find a short $\mathbf{x}$ s.t. $\mathbf{A}\cdot \mathbf{x}\equiv \mathbf{0}$.

(Wee & Wu, 2023b)

We consider BASIS${}_{struct}$ with $k=2$, for simplicity.

Let $\mathbf{A}\in {\mathbb{Z}}_q^{\eta \times \ell }$. We're given $$\mathbf{B}:=\left(\begin{array}{ccc}{\mathbf{A}}_0& \mathbf{0}& -{\mathbf{G}}_{\eta +1}\\ \mathbf{0}& {\mathbf{A}}_1& -{\mathbf{G}}_{\eta +1}\end{array}\right)$$ and a short $\mathbf{T}$ s.t. $${\mathbf{G}}_{{\eta }^{\prime }}\equiv \mathbf{B}\cdot \mathbf{T}modq$$ where ${\mathbf{A}}_i:={\mathbf{W}}_i\cdot \mathbf{A}$ for known ${\mathbf{W}}_i\in {\mathbb{Z}}_q^{\eta \times \eta }$.

The BASIS${}_{struct}$ assumption states that given $(\mathbf{B},\mathbf{T})$ it is hard to find a short $\mathbf{x}$ s.t. $\mathbf{A}\cdot \mathbf{x}\equiv \mathbf{0}$.

PRISIS (Fenzi & Nguyen, 2023) is a special case of BASIS. It is more structured than BASIS, so we might expect hardness results on PRISIS to translate to BASIS. It turns out the additional structure allows to prove a broader regime of parameters as hard as M-SIS.

Let $\mathbf{A}\in {\mathcal{R}}_q^{\eta \times \ell }$. We're given $$\mathbf{B}:=\left(\begin{array}{cccc}\mathbf{A}& \mathbf{0}& \cdots & -{\mathbf{G}}_{\eta +1}\\ \mathbf{0}& w\cdot \mathbf{A}& \cdots & -{\mathbf{G}}_{\eta +1}\\ \mathbf{0}& \mathbf{0}& \ddots & -{\mathbf{G}}_{\eta +1}\\ \mathbf{0}& \cdots & w^{\ell -1}\cdot \mathbf{A}& -{\mathbf{G}}_{\eta +1}\end{array}\right)$$ and a short $\mathbf{T}$ s.t. $${\mathbf{G}}_{{\eta }^{\prime }}\equiv \mathbf{B}\cdot \mathbf{T}modq.$$

The PRISIS assumption states that given $(\mathbf{A},\mathbf{B},w,\mathbf{T})$ it is hard to find a short $\mathbf{x}$ s.t. $\mathbf{A}\cdot \mathbf{x}\equiv \mathbf{0}$.

$h$-PRISIS (Albrecht, Fenzi, Lapiha, & Nguyen, 2023) is a multi-instance version of PRISIS.

Let ${\mathbf{A}}_i\in {\mathcal{R}}_q^{\eta \times \ell }$ for $i\in \{0,\dots ,h-1\}$. We're given $${\mathbf{B}}_i:=\left(\begin{array}{cccc}{\mathbf{A}}_i& \mathbf{0}& \cdots & -{\mathbf{G}}_{\eta +1}\\ \mathbf{0}& w_i\cdot {\mathbf{A}}_i& \cdots & -{\mathbf{G}}_{\eta +1}\\ \mathbf{0}& \mathbf{0}& \ddots & -{\mathbf{G}}_{\eta +1}\\ \mathbf{0}& \cdots & w_i^{\ell -1}\cdot {\mathbf{A}}_i& -{\mathbf{G}}_{\eta +1}\end{array}\right)$$ and a short ${\mathbf{T}}_i$ s.t. $${\mathbf{G}}_{{\eta }^{\prime }}\equiv {\mathbf{B}}_i\cdot {\mathbf{T}}_{i}modq.$$

The $h$-PRISIS assumption states that given $(\{{\mathbf{A}}_i\},\{{\mathbf{B}}_i\},\{w_i\},\{\mathbf{T}{\}}_i)$ it is hard to find a short ${\mathbf{x}}_i$ s.t. $\sum {\mathbf{A}}_i\cdot {\mathbf{x}}_i\equiv \mathbf{0}$.

(Bootle, Lyubashevsky, Nguyen, & Sorniotti, 2023)

Let $\mathbf{A}\in {\mathbb{Z}}_q^{\eta \times \ell }$ and let $f:{\mathbb{Z}}_N\to {\mathbb{Z}}_q^{\eta }$ be a function. Given $(\mathbf{A},f)$ and access to an oracle that when called samples a fresh $x{\leftarrow }_{\mathrm{\$}}{\mathbb{Z}}_N$ and outputs $x,{\mathbf{u}}_x$ s.t. $$\mathbf{A}\cdot {\mathbf{u}}_x\equiv f(x)modq\text{ and }\Vert {\mathbf{u}}_x\Vert \le \beta ,$$ the ISISf assumption states that it is hard to output a fresh tuple $(x^{\ast },{\mathbf{u}}^{\ast })$ s.t. $$\mathbf{A}\cdot {\mathbf{u}}^{\ast }\equiv f(x^{\ast })modq\text{ and }\Vert {\mathbf{u}}^{\ast }\Vert \le {\beta }^{\ast }.$$