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{𝐬}}^{*})\in \{(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

TODO

Hardness of ISIS_f and its interactive version

TODO

Constructions based on ISIS_f

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

• Signatures
• Group signatures
• Blind signatures
• Anonymous credentials

Related Assumptions

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