Generalised ISISf

The Generalised ISIS_f assumption (GenISIS_f) was introduced by Dubois, Klooß, Lai, and Woo in 2025. As the name suggests, it is a generalisation of the ISISf assumption introduced in 2023. It removes two restrictions imposed by ISIS_f, which enables reducing to GenISIS_f. Furthermore, GenISIS_f inherits the ISIS_f framework to generically generate constructions for several primitives.

Formal Definition

GenISIS_f

Let $(n,m,d,q,\beta ,k,s)$ be public parameters, matrix $\mathbf{𝐀}\in {{ℛ}}_q^{n\times m}$ be chosen uniformly at random, $f$ be a keyed function $f:{𝒦}\times D\to {{ℛ}}_q^n$, and $\chi$ be a distribution over $D$. The challenger chooses a key $\kappa \leftarrow {𝒦}$ uniformly and generates $k$ hints $(x_i,{\mathbf{𝐬}}_i)$ in the following way.

• $x_i\leftarrow \chi$
• ${\mathbf{𝐬}}_i\leftarrow {\mathbf{𝐀}}_s^{-1}(f(\kappa ,x_i))$

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

Intuition. Compared to ISIS_f, GenISIS_f allows hints to be chosen from any distribution $\chi$ over $D$ instead of them needing to uniformly distributed over $[N]$. Otherwise, GenISIS_f does not rely on a statically chosen function $f$, but a keyed function - or a family of functions, of which a specific function is chosen at runtime.

Interactive GenISISf

Let $(n,m,d,{\ell }_m,{\ell }_r,q,{\beta }_s,{\beta }_m,s)$ 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 keyed function $f:{𝒦}\times D\to {{ℛ}}_q^n$, $\chi$ be a distribution over $D$, ${ℳ}=\mathrm{\varnothing }$, and a uniformly chosen key $\kappa \in {𝒦}$. Given the matrices $\mathbf{𝐀},\mathbf{𝐂}$, and the key $\kappa$, an adversary is able to query an oracle $O_{\text{pre}}$ adaptively, which on input $\mathbf{𝐦}\in {{ℛ}}^{\ell }$ proceeds as follows.

1. if $\Vert \mathbf{𝐦}\Vert >{\beta }_m$ then return $\perp$
2. $x\leftarrow \chi$
3. $\mathbf{𝐬}\leftarrow {\mathbf{𝐀}}_s^{-1}(f(x)+\mathbf{𝐂}\cdot \mathbf{𝐦})$
4. ${\mathscr{H}}\leftarrow {\mathscr{H}}\cup \{x,\mathbf{𝐬},\mathbf{𝐦}\}$
5. return $(x,\mathbf{𝐬})$

An adversary is asked to find a new tuple $(x^{*},{\mathbf{𝐬}}^{*},{\mathbf{𝐦}}^{*})$ satisfying $(x^{*},{\mathbf{𝐬}}^{*},{\mathbf{𝐦}}^{*})\notin {\mathscr{H}}\wedge \mathbf{𝐀}\cdot {\mathbf{𝐬}}^{*}=f(x^{*})+\mathbf{𝐂}\cdot \mathbf{𝐦}\wedge 0<\Vert {\mathbf{𝐬}}^{*}\Vert \le {\beta }_s\wedge \Vert {\mathbf{𝐦}}^{*}\Vert \le {\beta }_m.$

Intuition. Compared to the interactive version of ISIS_f, interactive GenISIS_f introduces a "strong unforgeability" flavour.

Hardness of GenISIS_f and its interactive version

Dubois et al. provide a translation of Theorem 3.3 to GenISIS_f provided by Bootle et al., which states that interactive ISIS_f is at least as hard as ISIS_f.

Otherwise, the authors show in Theorem 7 that GenISIS_f is equivalent to the sEUF-RMA experiment for vSIS-based signatures, which are introduced in the same work.

Constructions based on GenISIS_f

Bootle et al. provide a framework to generically build the following constructions from any interactive ISIS_f instance. As any ISIS_f instance is also a GenISIS_f instance, GenISIS_f inherits this framework.

• Signatures
• Group signatures
• Blind signatures
• Anonymous credentials

Related Assumptions

• ISIS_f
• One-More-ISIS
• Randomised One-More-ISIS
• Vanishing SIS