ISISf

The ISIS_f assumption was introduced by Bootle, Lyubashevsky, Nguyen, and Sorniotti in 2023. It introduces a function $f$ that removes the requirement of a static target vector and passes additional hints to the adversary.

Formal Definition

ISIS_f

Let $(n,m,d,q,\beta ,k,s,N)$ be public parameters, matrix $\mathbf{𝐀}\in {{ℛ}}_q^{n\times m}$ be chosen uniformly at random and $f$ be a specified function $f:[N]\to {{ℛ}}_q^n$. The challenger generates $k$ hints $(x_i,{\mathbf{𝐬}}_i)$ in the following way.

• $x_i\leftarrow [N]$
• ${\mathbf{𝐬}}_i\leftarrow {\mathbf{𝐀}}_s^{-1}(f(x_i))$

Given the matrix $\mathbf{𝐀}$, the function $f$, and the set of hints $\{(x_i,{\mathbf{𝐬}}_i){\}}_{i\in [k]}$, the adversary is asked to find a new tuple $(x^{*},{\mathbf{𝐬}}^{*})\in [N]\times {{ℛ}}^m$ satisfying $\mathbf{𝐀}\cdot {\mathbf{𝐬}}^{*}=f\left(x^{*}\right)modq\wedge 0<\Vert {\mathbf{𝐬}}^{*}\Vert \le \beta \wedge (x^{*},{\mathbf{𝐬}}^{*})\notin \{(x_i,{\mathbf{𝐬}}_i{)}_{i\in [k]}\}.$

Intuition. ISIS_f essentially expects the adversary to either successfully solve ISIS or compute a preimage of the function $f$. Thus, the hardness of ISIS_f depends on the choice of $f$. We list few examples for insecure choices of $f$.

• Additively homomorphic functions imply trivial solutions by adding or subtracting two hints.
• Any efficiently invertible function using public information enables choosing ${\mathbf{𝐬}}^{*}\in {{ℛ}}^m$ short and finding a preimage of $\mathbf{𝐀}\cdot {\mathbf{𝐬}}^{*}$.
• Assume $f$ is a linear function and the domain of $f$ was mapped to ${\mathbb{\mathbb{Z}}}_N$. Then, any hint $(x_i,{\mathbf{𝐬}}_i)$ can be used to generate a valid ISIS_f solution $(-x_i,-{\mathbf{𝐬}}_i)$.

Interactive ISIS_f

Let $(n,m,d,{\ell }_m,{\ell }_r,q,{\beta }_s,{\beta }_m,s,N)$ be public parameters, matrices $\mathbf{𝐀}\in {{ℛ}}_q^{n\times m},\mathbf{𝐂}\in {{ℛ}}_q^{n\times ({\ell }_m+{\ell }_r)}$ be chosen uniformly at random, $f$ be a specified function $f:[N]\to {{ℛ}}_q^n$, and ${ℳ}=\mathrm{\varnothing }$. Given the matrices $\mathbf{𝐀},\mathbf{𝐂}$, and the function $f$, an adversary is able to query an oracle $O_{\text{pre}}$ adaptively, which on input $\mathbf{𝐦}\in {{ℛ}}^{{\ell }_m},\mathbf{𝐫}\in {{ℛ}}^{{\ell }_r}$ proceeds as follows.

1. if $\Vert (\mathbf{𝐦},\mathbf{𝐫})\Vert >{\beta }_m$ then return $\perp$
2. $x\leftarrow [N]$
3. $\mathbf{𝐬}\leftarrow {\mathbf{𝐀}}_s^{-1}(f(x)+\mathbf{𝐂}\cdot \left[\begin{array}{c}\mathbf{𝐦}\\ \mathbf{𝐫}\end{array}\right])$
4. ${ℳ}\leftarrow {ℳ}\cup \{\mathbf{𝐦}\}$
5. return $(x,\mathbf{𝐬})$

An adversary is asked to find a new tuple $(x^{*},{\mathbf{𝐬}}^{*},{\mathbf{𝐦}}^{*},{\mathbf{𝐫}}^{*})$ satisfying ${\mathbf{𝐦}}^{*}\notin {ℳ}\wedge \mathbf{𝐀}\cdot {\mathbf{𝐬}}^{*}=f(x^{*})+\mathbf{𝐂}\cdot \left[\begin{array}{c}\mathbf{𝐦}\\ \mathbf{𝐫}\end{array}\right]\wedge 0<\Vert {\mathbf{𝐬}}^{*}\Vert \le {\beta }_s\wedge \Vert ({\mathbf{𝐦}}^{*},{\mathbf{𝐫}}^{*})\Vert \le {\beta }_m.$

Intuition. The interactive version expands ISIS_f by an Ajtai commitment and enables adaptive queries, where an adversary controls the input to the Ajtai commitment. Notice that the adversary is not capable of influencing the choice of $x\in [N]$, which can be thought of as salt in the context of a signature whereas $\mathbf{𝐬}\in {{ℛ}}^m$ is the signature.

Hardness of ISIS_f and its interactive version

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

Bootle et al. set $f$ to be $f(x)=\mathbf{𝐁}\cdot \text{bin}(x)$, where $\text{bin}:[N]\to {\mathbb{\mathbb{Z}}}^{\lceil \log (N)\rceil }$ outputs the binary encoding of $x\in [N]$. They call this problem ISIS_bin. The authors analyse direct lattice reduction as well as exploiting relations on the image space for ISIS_bin.

In Theorem 3.3, Bootle et al. show that interactive ISIS_f is at least as hard as ISIS_f. The reduction uses $\mathbf{𝐂}=\mathbf{𝐀}\cdot \mathbf{𝐑}$ for a uniformly chosen $\mathbf{𝐑}\leftarrow \{0,1{\}}^{m\times ({\ell }_m+{\ell }_r)}$, rejection sampling, the entropy that $x\in [N]$ and $\mathbf{𝐬}\in {{ℛ}}^m$ are sampled with and introduces a polynomial loss factor depending on the number of allowed queries to $O_{\text{pre}}$.

Constructions based on ISIS_f

Bootle et al. provide a framework to generically build the following constructions from any interactive ISIS_f instance.

• Signatures
• Group signatures
• Blind signatures
• Anonymous credentials

Related Assumptions

• Generalised ISIS_f
• One-More-ISIS
• Randomised One-More-ISIS