# SIS with Hints Zoo

$$\newcommand\ring{\mathcal{R}} \newcommand\ZZ{\mathbb{Z}} \renewcommand{\vec}[1]{{\boldsymbol{\mathbf{#1}}}} \newcommand\mat[1]{\vec{#1}} \newcommand{\sample}{\gets_{\}}$$

An attempt to keep track of all those new SIS-like assumptions that hand out additional hints. Some of these venture into LWE land, but for now I want to keep it more or less SIS focused.

• Designers: Please consider whether you can re-use one of those many newfangled assumptions before introducing yet another one.
• Cryptanalysts: Analyse them!

In th jolly tradition of "Are Graded Encoding Schemes broken yet?" I tag problems as BROKEN if I am aware of cryptanalysis. I also tag them as:

STANDARD
if there is a reduction from a standard (non-hint) assumption that covers meaningful parameters, i.e. those useful in applications. For example, k-SIS is tagged like this but k-R-ISIS is not because known reductions only cover parameters that, so far, seem useless in applications.
EQUIVALENT
if there is a reduction from another hint assumption. Again, this may only cover some parameters. This is meant to indicate that cryptanalytic efforts might be better directed at the equivalent problem.

Please reach out if you find a mistake or have an update.

## 1.STANDARD k-SIS

We give the module variant defined in (Albrecht, Cini, Lai, Malavolta, & Thyagarajan, 2022). We recover the original definition by setting $$\ring := \ZZ$$.

For any integer $$k \geq 0$$, an instance of the k-M-SIS problem is a matrix $$\mat{A} \in \ring_{q}^{\eta \times \ell}$$ and a set of $$k$$ vectors $$\vec{u}_{0}, \ldots \vec{u}_{k-1}$$ s.t. $$\mat{A}\cdot \vec{u}_{i} \equiv \vec{0} \bmod q$$ with $$\|{\vec{u}_i}\| \leq \beta$$. A solution to the problem is a nonzero vector $$\vec{u} \in \ring^{\ell}$$ such that

$\|{\vec{u}}\| \leq \beta^*, \quad \mat{A}\cdot \vec{u} \equiv \vec{0} \bmod q,\quad \text{and} \quad \vec{u} \notin \mathcal{K}\text{-}\operatorname{span}(\set{\vec{u}_i}_{0 \leq i < k}).$

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

### 1.1. Hardness

The original paper showed that k-SIS (over $$\ZZ$$) is hard if SIS is hard for uniform $$\mat{A}$$ and discrete Gaussian $$\vec{u}_{i}$$. This reduction was improved in (Ling, Phan, Stehlé, & Steinfeld, 2014) to cover $$k = \mathcal{O}(\ell)$$.

The condition $$\vec{u} \notin \mathcal{K}\text{-}\operatorname{span}(\set{\vec{u}_i}_{0 \leq i < k})$$ can be dropped when $$k < \ell^{1/4}$$ because then the probability that there is an additional short vector in the $$k$$-dimensional sublattice spanned by the $$\vec{u}_i$$ is negligible.

No proof was provided for the module variant.

## 2. One-more-ISIS

A challenger selects a matrix $$\mat{A} \in \ZZ_{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. $$\vec{t} \gets_{\} \ZZ_{q}^{\eta}$$, adds to some set $$\mathcal{S}$$ and returns to the adversary.

Preimage queries. The adversary submits any vector $$\vec{t}' \in \ZZ_{q}^{\eta}$$. The challenger will return a short vector $$\vec{y}' \gets_{\} D_{\ZZ^\ell,\sigma}$$ such that $$\mat{A}\cdot \vec{y}' \equiv \vec{t}' \bmod q$$. Denote $$k$$ for the number of preimage queries.

In the end the adversary is asked to output $$k+1$$ pairs $$\{(\vec{y}_i,\vec{t}_i)\}_{0 \leq i < k+1}$$ satisfying: $\mat{A}\cdot \vec{y}_{i} \equiv \vec{t}_{i} \bmod q, \|\vec{y}_{i}\| \leq \beta \text{ and }\vec{t}_{i} \in \mathcal{S}.$

### 2.1. Hardness

The hardness of the problem is analysed using direct cryptanalysis in the original paper. The authors give a combinatorial attack and a lattice attack.

Combinatorial Attack. The adversary requests $$\eta \cdot q$$ preimages for all $$\{a \cdot \vec{e}_{i}\ \mid\ a \in \ZZ_{q}, i \in \ZZ_{\eta}\}$$, here $$\vec{e}_{i}$$ is the $$i$$-th unit vector. Then, adding up $$n$$ such preimages allows to construct any image. Since the norm of the preimages returned by the challenger is $$\sqrt{\ell} \cdot \sigma$$, this allows to solve the One-more-ISIS problem when $$\sqrt{n\cdot \ell} \cdot \sigma \leq \beta$$. Of course, smaller and larger sets of preimages are possible, increasing and decreasing the output norm respectively.

Lattice Attack. The adversary requests $$\geq \ell$$ preimages of zero and uses that to produce a short basis $$\mat{T}$$ for the kernel of $$\mat{A}$$, i.e. $$\mat{A}\cdot\mat{T} \equiv \vec{0} \bmod q$$. This constitutes a trapdoor for $$\mat{A}$$ and thus permits to return short preimages for any target. The key point here is that this trapdoor is of degraded quality relative to the trapdoor used by the challenger. The key computational challenge then is to fix-up or improve this degraded trapdoor in order to be able to sample sufficiently short vectors.

## 3. K-R-ISIS

Let $$g(\vec{X}) \in \mathcal{R}(\vec{X})$$ be a Laurent monomial, i.e. $$g(\vec{X}) = \vec{X}^{\vec{e}} := \prod_{i \in \ZZ_w} X_i^{e_i}$$ for some exponent vector $$\vec{e} = (e_i: i \in \ZZ_w) \in \ZZ^w$$. Let $$\mathcal{G} \subset \mathcal{R}(\vec{X})$$ be a set of Laurent monomials with $$k := |\mathcal{G}|$$. Let $$g^{\star} \in \mathcal{R}(\vec{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. $$\|\vec{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}$$.

Now, let $$\vec{t} = (1,0,\ldots,0)$$. Let $$\mathcal{G} \subset \mathcal{R}(\vec{X})$$ be a set of $$w$$-variate Laurent monomial. Let $$g^{\star} \in \mathcal{R}(\vec{X})$$ be a target Laurent monomial. Let $$(\mathcal{G},g^\star)$$ be k-M-ISIS-admissible. Let $$\mat{A} \gets_{\} \ring_q^{\eta \times \ell}$$, $$\vec{v} \gets_{\} (\ring_q^\star)^w$$. The K-M-ISIS assumption states that given $$(\mat{A}, \vec{v}, \vec{t}, \{\vec{u}_{g}\})$$ with $$\vec{u}_{g}$$ short and $g(\vec{v}) \cdot \vec{t} \equiv \mat{A}\cdot \vec{u}_{g} \bmod q$ it is hard to find a short $$\vec{u}_{g^*}$$ and small $$s^{*}$$ s.t. $s^* \cdot g^{*}(\vec{v}) \cdot \vec{t} \equiv \mat{A} \cdot \vec{u}_{g^*} \bmod q.$ When $$\eta = 1$$, i.e. when $$\mat{A}$$ is just a vector, we call the problem k-R-ISIS.

### 3.1. Hardness

The hardness of the problem is analysed by the authors by providing some partial reductions, i.e. covering some special cases. These special cases are not interesting for applications. The authors show that

• k-R-ISIS (with $$g^{*} \equiv 1$$) is as hard as R-SIS when $$\ell > k$$ or when the system generated by $$\mathcal{G}$$ is efficiently invertible.
• k-M-ISIS is at least as hard as k-R-ISIS and that k-M-ISIS is a true generalisation of k-R-SIS.
• $$(\mathcal{G},g^*)$$ is as hard as $$(\mathcal{G},0)$$ for any $$\mathcal{G}$$, formalising the intuition that the non-homogeneous variant is no easier than the homogeneous variant.
• scaling $$(\mathcal{G},g^*)$$ multiplicatively by any non-zero Laurent monomial does not change the hardness, e.g. we may choose to normalise instances to $$g^{*} \equiv 1$$.

The authors also explore direct cryptanalysis:

• a direct SIS attack on $$\mat{A}$$.
• finding short $$\ZZ$$-linear combinations of $$\vec{u}_{i}$$
• finding $$\mathbb{Q}$$-linear combinations of $$\vec{u}_{i}$$ that produce short images.

## 4.BROKEN Knowledge K-R-ISIS

The assumption essentially states that for any element $$c \cdot \vec{t}$$ that the adversary can produce together with a short preimage, it produced that as some small linear combination of the preimages $$\{\vec{u}_{g}\}$$ we have given it. Thus, roughly:

If an adversary outputs any $$c, \vec{u}_{c}$$ s.t. $c \cdot \vec{t} \equiv \mat{A} \cdot \vec{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(\vec{v}) \bmod q.$

The knowledge assumption only makes sense for $$\eta \geq 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.

### 4.1. Cryptanalysis

The assumption is invalidated – at least "morally" – in (Wee & Wu, 2023a). Roughly speaking, the attack uses that the preimages of $$g(\vec{v}) \cdot \vec{t}$$ span a short basis of the submodule spanned by $$\vec{t}$$: essentially an Ajtai-style trapdoor. Then, sampling an arbitrary, not-necessarily short, preimage of some $$c \cdot \vec{t}$$, Babai rounding can be applied to obtain a short preimage of some other, random $$\tilde{c} \cdot \vec{t}$$.

An implementation of the attack in SageMath is available here.

## 5.EQUIVALENT Twin K-R-ISIS

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

### 5.1. Hardness

In (Albrecht, Fenzi, Lapiha, & Nguyen, 2023), it is shown that Twin k-R-ISIS is no easier than k-R-ISIS via a re-randomisation argument.

## 6.STANDARD BASIS (Random)

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

Let $$\mat{A} \in \ZZ_{q}^{\eta \times \ell}$$. We're given $\vec{B} := \begin{pmatrix}\mat{A}_{0} & \vec{0} & - \vec{G}_{\eta+1}\\ \vec{0} & \mat{A}_{1} & -\vec{G}_{\eta+1}\end{pmatrix}$ and a short $$\vec{T}$$ s.t. $\vec{G}_{\eta'} \equiv \vec{B} \cdot \vec{T} \bmod q$ where $$\mat{A}_{i}$$ are uniformly random for $$i>0$$ and $$\mat{A}_{0} := [\vec{a} | \mat{A}^{T}]^{T}$$ for uniformly random $$\mat{A}$$ and $$\vec{a}$$.

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

### 6.1. Hardness

It was shown in the original paper that BASIS$$_{rand}$$ is as hard as SIS. The idea is that we can construct $$\vec{B}$$ given $$\mat{A}$$ since we can trapdoor all $$\mat{A}_{i}$$ for $$i > 0$$.

A way of looking at is by noting that for each column $$\vec{t} = (\vec{t}^{(0)}, \vec{t}^{(1)}, \vec{t}^{(G)})$$ of $$\vec{T}$$ we have $$\mat{A}_{i} \cdot \vec{t}^{(i)} \equiv \vec{G}_{\eta+1} \cdot \vec{t}^{(G)}$$ where $$\vec{G}_{\eta+1} \cdot \vec{t}^{(G)}$$ is close to uniform. Thus, we can sample $$\vec{t}^{(0)}$$, compute $$\vec{y} := \mat{A}_{0} \cdot \vec{t}^{(0)}$$ and then use the gadget structure of $$\vec{G}_{\eta+1}$$ to find a short $$\vec{t}^{(G)}$$ s.t. $$\mat{A}_{i} \cdot \vec{t}^{(i)} \equiv \vec{G}_{\eta+1} \cdot \vec{t}^{(G)}$$. Then, using the trapdoors for $$\mat{A}_{i}$$ with $$i>0$$ we can find $$\vec{t}^{(i)}$$ s.t. $$\mat{A}_{i} \cdot \vec{t}^{(i)} \equiv \vec{G}_{\eta+1} \cdot \vec{t}^{(G)}$$.

## 7.EQUIVALENT BASIS (Structured)

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

Let $$\mat{A} \in \ZZ_{q}^{\eta \times \ell}$$. We're given $\vec{B} := \begin{pmatrix}\mat{A}_{0} & \vec{0} & - \vec{G}_{\eta+1}\\ \vec{0} & \mat{A}_{1} & -\vec{G}_{\eta+1}\end{pmatrix}$ and a short $$\vec{T}$$ s.t. $\vec{G}_{\eta'} \equiv \vec{B} \cdot \vec{T} \bmod q$ where $$\mat{A}_{i} := \vec{W}_{i} \cdot \mat{A}$$ for known $$\vec{W}_{i} \in \ZZ_{q}^{\eta \times \eta}$$.

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

### 7.1. Hardness

The authors also show that given an algorithm for solving BASIS$$_{struct}$$ there is an algorithm for solving k-M-ISIS. This reduction outputs a BASIS$$_{struct}$$ instance of size $$k < \ell/k'$$ where $$k'$$ is the parameter $$k$$ of the k-M-ISIS instance.

## 8. PRISIS

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 $$\mat{A} \in \ring_{q}^{\eta \times \ell}$$. We're given $\vec{B} := \begin{pmatrix} \mat{A} & \vec{0} & \cdots & - \vec{G}_{\eta+1}\\ \vec{0} & w \cdot \mat{A} & \cdots & -\vec{G}_{\eta+1}\\ \mat{0} & \vec{0} & \ddots & -\vec{G}_{\eta+1}\\ \vec{0} & \cdots & w^{\ell-1} \cdot \mat{A} & -\vec{G}_{\eta+1} \end{pmatrix}$ and a short $$\vec{T}$$ s.t. $\vec{G}_{\eta'} \equiv \vec{B} \cdot \vec{T} \bmod q.$

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

### 8.1. Hardness

If $$\ell=2$$ then PRISIS is no easier than M-SIS (Fenzi & Nguyen, 2023).

## 9.STANDARD $$h$$-PRISIS

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

Let $$\mat{A}_{i} \in \ring_{q}^{\eta \times \ell}$$ for $$i \in \{0,…,h-1\}$$. We're given $\vec{B}_{i} := \begin{pmatrix} \mat{A}_{i} & \vec{0} & \cdots & - \vec{G}_{\eta+1}\\ \vec{0} & w_{i} \cdot \mat{A}_{i} & \cdots & -\vec{G}_{\eta+1}\\ \mat{0} & \vec{0} & \ddots & -\vec{G}_{\eta+1}\\ \vec{0} & \cdots & w_i^{\ell-1} \cdot \mat{A}_{i} & -\vec{G}_{\eta+1} \end{pmatrix}$ and a short $$\vec{T}_{i}$$ s.t. $\vec{G}_{\eta'} \equiv \vec{B}_{i} \cdot \vec{T}_{i} \bmod q.$

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

### 9.1. Hardness

$$h$$-PRISIS is no easier than PRISIS (Albrecht, Fenzi, Lapiha, & Nguyen, 2023). In particular, if $$\ell=2$$ then $$h$$-PRISIS is no easier than M-SIS (Albrecht, Fenzi, Lapiha, & Nguyen, 2023).

## 10. ISISf

Let $$\mat{A} \in \ZZ_{q}^{\eta \times \ell}$$ and let $$f: \ZZ_{N} \rightarrow \ZZ_{q}^{\eta}$$ be a function. Given $$(\mat{A}, f)$$ and access to an oracle that when called samples a fresh $$x \sample \ZZ_{N}$$ and outputs $$x, \vec{u}_{x}$$ s.t. $\mat{A} \cdot \vec{u}_{x} \equiv f(x) \bmod q \text{ and } \|\vec{u}_{x}\| \leq \beta,$ the ISISf assumption states that it is hard to output a fresh tuple $$(x^{*}, \vec{u}^{*})$$ s.t. $\mat{A} \cdot \vec{u}^{*} \equiv f(x^*) \bmod q \text{ and } \|\vec{u}^{*}\| \leq \beta^*.$

### 10.1. Hardness

If $$f$$ is a random oracle then the problem, in the ROM, is as hard as SIS.

In (Bootle, Lyubashevsky, Nguyen, & Sorniotti, 2023) the authors set $$f$$ to be a function that first turns $$x \in \ZZ_{N}$$ into a binary vector $$\vec{x} \in \{0,1\}^{\log N}$$ and then outputs $$\mat{B} \cdot \vec{x}$$. The call this problem ISIS$$_{bin}$$. The authors analyse direct lattice reduction as well as exploiting relations on the image space. The authors also introduce an interactive variant and show its equivalence.

## Bibliography

Agrawal, S., Kirshanova, E., Stehlé, D., & Yadav, A. (2022). Practical, round-optimal lattice-based blind signatures. In H. Yin, A. Stavrou, C. Cremers, & E. Shi (Eds.), Proceedings of the 2022 ACM SIGSAC conference on computer and communications security, CCS 2022 (pp. 39–53). https://doi.org/10.1145/3548606.3560650
Albrecht, M. R., Cini, V., Lai, R. W. F., Malavolta, G., & Thyagarajan, S. A. K. (2022). Lattice-based snarks: Publicly verifiable, preprocessing, and recursively composable - (extended abstract). In Y. Dodis & T. Shrimpton (Eds.), Advances in cryptology - CRYPTO 2022 (pp. 102–132). Springer. https://doi.org/10.1007/978-3-031-15979-4\_4
Albrecht, M. R., Fenzi, G., Lapiha, O., & Nguyen, N. K. (2023). Slap: Succinct lattice-based polynomial commitments from standard assumptions. Cryptology ePrint Archive, Paper 2023/1469. Retrieved from https://eprint.iacr.org/2023/1469
Balbás, D., Catalano, D., Fiore, D., & Lai, R. W. F. (2022). Functional commitments for circuits from falsifiable assumptions. Cryptology ePrint Archive, Paper 2022/1365. Retrieved from https://eprint.iacr.org/2022/1365
Boneh, D., & Freeman, D. M. (2011). Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. In D. Catalano, N. Fazio, R. Gennaro, & A. Nicolosi (Eds.), Public key cryptography - PKC 2011 (pp. 1–16). Springer. https://doi.org/10.1007/978-3-642-19379-8\_1
Bootle, J., Lyubashevsky, V., Nguyen, N. K., & Sorniotti, A. (2023). A framework for practical anonymous credentials from lattices. Cryptology ePrint Archive, Paper 2023/560. Retrieved from https://eprint.iacr.org/2023/560
Fenzi, G., & Nguyen, N. K. (2023). Lattice-based polynomial commitments: Towards asymptotic and concrete efficiency. Cryptology ePrint Archive, Paper 2023/846. Retrieved from https://eprint.iacr.org/2023/846
Ling, S., Phan, D. H., Stehlé, D., & Steinfeld, R. (2014). Hardness of k-lwe and applications in traitor tracing. In J. A. Garay & R. Gennaro (Eds.), Advances in cryptology - CRYPTO 2014 (pp. 315–334). Springer. https://doi.org/10.1007/978-3-662-44371-2\_18
Wee, H., & Wu, D. J. (2023a). Lattice-based functional commitments: Fast verification and cryptanalysis. Asiacrypt 2023. Springer-Verlag.
Wee, H., & Wu, D. J. (2023b). Succinct vector, polynomial, and functional commitments from lattices. In C. Hazay & M. Stam (Eds.), Advances in cryptology - EUROCRYPT 2023 (pp. 385–416). Springer. https://doi.org/10.1007/978-3-031-30620-4\_13