Generalised ISISf: Difference between revisions

Latest revision as of 13:26, 27 August 2025

The Generalised ISIS_f assumption (GenISIS_f) was introduced by Dubois, Klooß, Lai, and Woo in 2025.^[1] As the name suggests, it is a generalisation of the ISISf assumption introduced in 2023.^[2] 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, β, k, s)$ be public parameters, matrix $𝐀 \in ℛ_{q}^{n \times m}$ be chosen uniformly at random, $f$ be a keyed function $f : 𝒦 \times D \to ℛ_{q}^{n}$ , and $χ$ be a distribution over $D$ . The challenger chooses a key $κ \leftarrow 𝒦$ uniformly and generates $k$ hints $(x_{i}, 𝐬_{i})$ in the following way.

$x_{i} \leftarrow χ$
$𝐬_{i} \leftarrow 𝐀_{s}^{- 1} (f (κ, x_{i}))$

Given the matrix $𝐀$ , the key $κ$ , and the set of hints ${(x_{i}, 𝐬_{i})}_{i \in [k]}$ , the adversary is asked to find a new tuple $(x^{*}, 𝐬^{*}) \in D \times ℛ^{m}$ satisfying $𝐀 \cdot 𝐬^{*} = f (κ, x^{*}) mod q \land 0 < ‖ 𝐬^{*} ‖ \leq β \land (x^{*}, 𝐬^{*}) \notin {(x_{i}, 𝐬_{i})_{i \in [k]}} .$

Intuition. Compared to ISIS_f, GenISIS_f allows hints to be chosen from any distribution $χ$ 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, ℓ_{m}, ℓ_{r}, q, β_{s}, β_{m}, s)$ be public parameters, matrices $𝐀 \in ℛ_{q}^{n \times m}, 𝐂 \in ℛ_{q}^{n \times (ℓ_{m} + ℓ_{r})}$ be chosen uniformly at random, $f$ be a keyed function $f : 𝒦 \times D \to ℛ_{q}^{n}$ , $χ$ be a distribution over $D$ , $ℳ = \emptyset$ , and a uniformly chosen key $κ \in 𝒦$ . Given the matrices $𝐀, 𝐂$ , and the key $κ$ , an adversary is able to query an oracle $O_{pre}$ adaptively, which on input $𝐦 \in ℛ^{ℓ}$ proceeds as follows.

if $‖ 𝐦 ‖ > β_{m}$ then return $⊥$
$x \leftarrow χ$
$𝐬 \leftarrow 𝐀_{s}^{- 1} (f (x) + 𝐂 \cdot 𝐦)$
$ℋ \leftarrow ℋ \cup {x, 𝐬, 𝐦}$
return $(x, 𝐬)$

An adversary is asked to find a new tuple $(x^{*}, 𝐬^{*}, 𝐦^{*})$ satisfying $(x^{*}, 𝐬^{*}, 𝐦^{*}) \notin ℋ \land 𝐀 \cdot 𝐬^{*} = f (x^{*}) + 𝐂 \cdot 𝐦 \land 0 < ‖ 𝐬^{*} ‖ \leq β_{s} \land ‖ 𝐦^{*} ‖ \leq β_{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.^[1] provide a translation of Theorem 3.3 to GenISIS_f provided by Bootle et al.^[2], which states that interactive ISIS_f is at least as hard as ISIS_f.

Otherwise, the authors^[1] 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.^[2] 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^[2]
Group signatures^[2]
Blind signatures^[2]^[3]
Anonymous credentials^[2]^[3]

Related Assumptions

References

↑ ^1.0 ^1.1 ^1.2 Dubois, A., Klooß, M., Lai, R.W. and Woo, I.K. Lattice-based proof-friendly signatures from vanishing short integer solutions. IACR International Conference on Public-Key Cryptography. Cham: Springer Nature Switzerland, 2025.
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 Bootle, J., Lyubashevsky, V., Nguyen, N.K. and Sorniotti, A. A framework for practical anonymous credentials from lattices. Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2023.
↑ ^3.0 ^3.1 Lyubashevsky, Vadim, Gregor Seiler, and Patrick Steuer. The LaZer library: Lattice-based zero knowledge and succinct proofs for quantum-safe privacy. Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2024.

[:2-1] 1.0 ^1.1 ^1.2 Dubois, A., Klooß, M., Lai, R.W. and Woo, I.K. Lattice-based proof-friendly signatures from vanishing short integer solutions. IACR International Conference on Public-Key Cryptography. Cham: Springer Nature Switzerland, 2025.

[:0-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 Bootle, J., Lyubashevsky, V., Nguyen, N.K. and Sorniotti, A. A framework for practical anonymous credentials from lattices. Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2023.

[:1-3] 3.0 ^3.1 Lyubashevsky, Vadim, Gregor Seiler, and Patrick Steuer. The LaZer library: Lattice-based zero knowledge and succinct proofs for quantum-safe privacy. Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2024.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-The Generalised ISIS<sub>f</sub> assumption (GenISIS<sub>f</sub>) was introduced by Dubois, Klooß, Lai, and Woo in 2025.<ref>Dubois, A., Klooß, M., Lai, R.W. and Woo, I.K. [https://eprint.iacr.org/2025/356.pdf Lattice-based proof-friendly signatures from vanishing short integer solutions]. ''IACR International Conference on Public-Key Cryptography.'' Cham: Springer Nature Switzerland, 2025.</ref> As the name suggests, it is a generalisation of the ISISf assumption introduced in 2023.<ref name=":0">Bootle, J., Lyubashevsky, V., Nguyen, N.K. and Sorniotti, A. [https://eprint.iacr.org/2023/560.pdf A framework for practical anonymous credentials from lattices]. ''Annual International Cryptology Conference''. Cham: Springer Nature Switzerland, 2023.</ref> It removes two restrictions imposed by ISIS<sub>f</sub>, which enables reducing to GenISIS<sub>f</sub>. Furthermore, GenISIS<sub>f</sub> inherits the ISIS<sub>f</sub> framework to generically generate constructions for several primitives.
+The Generalised ISIS<sub>f</sub> assumption (GenISIS<sub>f</sub>) was introduced by Dubois, Klooß, Lai, and Woo in 2025.<ref name=":2">Dubois, A., Klooß, M., Lai, R.W. and Woo, I.K. [https://eprint.iacr.org/2025/356.pdf Lattice-based proof-friendly signatures from vanishing short integer solutions]. ''IACR International Conference on Public-Key Cryptography.'' Cham: Springer Nature Switzerland, 2025.</ref> As the name suggests, it is a generalisation of the [[ISISf|ISISf assumption]] introduced in 2023.<ref name=":0">Bootle, J., Lyubashevsky, V., Nguyen, N.K. and Sorniotti, A. [https://eprint.iacr.org/2023/560.pdf A framework for practical anonymous credentials from lattices]. ''Annual International Cryptology Conference''. Cham: Springer Nature Switzerland, 2023.</ref> It removes two restrictions imposed by ISIS<sub>f</sub>, which enables reducing to GenISIS<sub>f</sub>. Furthermore, GenISIS<sub>f</sub> inherits the ISIS<sub>f</sub> framework to generically generate constructions for several primitives.
 == Formal Definition ==
 === GenISIS<sub>f</sub> ===
-TODO
+Let <math>(n,m,d,q,\beta,k,s)</math> be public parameters, matrix <math>\mathbf{A} \in \mathcal{R}_q^{n \times m}</math> be chosen uniformly at random, <math>f</math> be a keyed function <math>f: \mathcal{K} \times D \rightarrow \mathcal{R}_q^n</math>, and <math>\chi</math> be a distribution over <math>D</math>. The challenger chooses a key <math>\kappa \leftarrow \mathcal{K}</math> uniformly and generates <math>k</math> hints <math>(x_i, \mathbf{s}_i)</math> in the following way.
+* <math>x_i \leftarrow \chi</math>
+* <math>\mathbf{s}_i \leftarrow \mathbf{A}_s^{-1}(f(\kappa, x_i))</math>
+Given the matrix <math>\mathbf{A}</math>, the key <math>\kappa</math>, and the set of hints <math>\{ (x_i, \mathbf{s}_i) \}_{i \in [k]}</math>, the adversary is asked to find a new tuple <math>(x^*, \mathbf{s}^*) \in D \times \mathcal{R}^m</math> satisfying <math>\mathbf{A} \cdot \mathbf{s}^* = f\left( \kappa, x^*\right) \bmod q \land 0 < \lVert \mathbf{s}^* \rVert \leq \beta \land (x^*, \mathbf{s}^*) \notin \left\{ (x_i, \mathbf{s}_i)_{i \in [k]} \right\}.</math>
+'''Intuition.''' Compared to ISIS<sub>f</sub>, GenISIS<sub>f</sub> allows hints to be chosen from any distribution <math>\chi</math> over <math>D</math> instead of them needing to uniformly distributed over <math>[N]</math>. Otherwise, GenISIS<sub>f</sub> does not rely on a statically chosen function <math>f</math>, but a keyed function - or a family of functions, of which a specific function is chosen at runtime.
 === Interactive GenISISf ===
-TODO
+Let <math>(n,m,d,\ell_m, \ell_r,q,\beta_s, \beta_m,s)</math> be public parameters, matrices <math>\mathbf{A} \in \mathcal{R}_q^{n \times m}, \mathbf{C} \in \mathcal{R}_q^{n \times (\ell_m + \ell_r)}</math> be chosen uniformly at random, <math>f</math> be a keyed function <math>f: \mathcal{K} \times D \rightarrow \mathcal{R}_q^n</math>, <math>\chi</math> be a distribution over <math>D</math>, <math>\mathcal{M} = \emptyset</math>, and a uniformly chosen key <math>\kappa \in \mathcal{K}</math>. Given the matrices <math>\mathbf{A}, \mathbf{C}</math>, and the key <math>\kappa</math>, an adversary is able to query an oracle <math>O_\text{pre}</math> adaptively, which on input <math>\mathbf{m} \in \mathcal{R}^{\ell}</math>  proceeds as follows.
+# if <math>\lVert \mathbf{m} \rVert > \beta_m</math> then return <math>\perp</math>
+# <math>x \leftarrow \chi</math>
+# <math>\mathbf{s} \leftarrow \mathbf{A}_s^{-1}\left( f(x) + \mathbf{C} \cdot \mathbf{m} \right)</math>
+# <math>\mathcal{H} \leftarrow \mathcal{H} \cup \{ x, \mathbf{s}, \mathbf{m} \}</math>
+# return <math>(x,\mathbf{s})</math>
+An adversary is asked to find a new tuple <math>(x^*, \mathbf{s}^*, \mathbf{m}^*)</math> satisfying <math>( x^*, \mathbf{s}^*, \mathbf{m}^* ) \notin \mathcal{H} \land \mathbf{A} \cdot \mathbf{s}^* = f( x^* ) + \mathbf{C} \cdot \mathbf{m} \land 0 < \lVert \mathbf{s}^* \rVert \leq \beta_s \land \lVert \mathbf{m}^* \rVert \leq \beta_m.</math>
+'''Intuition.''' Compared to the interactive version of ISIS<sub>f</sub>, interactive GenISIS<sub>f</sub>  introduces a "strong unforgeability" flavour.
 == Hardness of GenISIS<sub>f</sub> and its interactive version ==
-TODO
+Dubois et al.<ref name=":2" /> provide a translation of Theorem 3.3 to GenISIS<sub>f</sub> provided by Bootle et al.<ref name=":0" />, which states that interactive ISIS<sub>f</sub> is at least as hard as ISIS<sub>f</sub>.
+Otherwise, the authors<ref name=":2" /> show in Theorem 7 that GenISIS<sub>f</sub> is equivalent to the sEUF-RMA experiment for [[Vanishing SIS|vSIS]]-based signatures, which are introduced in the same work.
 == Constructions based on GenISIS<sub>f</sub> ==
@@ Line 25: / Line 44: @@
 * [[One-More-ISIS]]
 * [[Randomised One-More-ISIS]]
+* [[Vanishing SIS]]
 == References ==
 <references />