Generalised ISIS$_f$ (GenISIS$_f$)

Propose Edit

Updated:

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 ISIS$_f$ assumption introduced in [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.

Definition

GenISIS$_{f}$

Let $(n,m,q,\beta,k,s,\mathcal{R})$ be public parameters, matrix $\mat{A} \in \mathcal{R}_q^{n \times m}$ be chosen uniformly at random, $f$ be a keyed function $f: \mathcal{K} \times D \rightarrow \mathcal{R}_q^n$, and $\chi$ be a distribution over $D$. The challenger chooses a key $\kappa \sample \mathcal{K}$ uniformly and generates $k$ hints $(x_i, \vec{s}_i)$ in the following way.

  • $x_i \sample \chi$
  • $\vec{s}_i \sample \mat{A}_s^{-1}(f(\kappa, x_i))$

Given the matrix $\mat{A}$, the key $\kappa$, and the set of hints $\set{(x_i, \vec{s}_i)}_{i \in [k]}$, the adversary is asked to find a new tuple $(x^{*}, \vec{s}^{*}) \in D \times \mathcal{R}^m$ satisfying \[\mat{A} \cdot \vec{s}^{*} = f(\kappa, x^{*}) \bmod q \land \norm{\vec{s}^{*}} \leq \beta \land (x^{*}, \vec{s}^{*}) \notin \set{(x_i, \vec{s}_i)}_{i \in [k]}.\]

The provided definition [3] simplifies notation and removes the condition $\vec{s}^{*} \neq \vec{0}$ compared to [1].

Intuition. GenISIS$_f$ essentially expects the adversary to either successfully solve ISIS or compute a preimage of the function $f(\kappa, \cdot)$. Thus, the hardness of GenISIS$_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 $\vec{s}^{*} \in \mathcal{R}^m$ short and finding a preimage of $\mat{A} \cdot \vec{s}^{*}$.
  • Assume $f$ is a linear function and $D = \ZZ_q$. Then, any hint $(x_i, \vec{s}_i)$ can be used to generate a valid GenISIS$_f$ solution $(-x_i, \vec{s}_i)$.

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 GenISIS$_f$

Let $(n,m,\ell,q,\beta_s,\beta_m,s,\mathcal{R})$ be public parameters, matrices $\mat{A} \in \mathcal{R}_q^{n \times m}$, $\mat{C} \in \mathcal{R}_q^{n \times \ell}$ be chosen uniformly at random, $f$ be a keyed function $f: \mathcal{K} \times D \rightarrow \mathcal{R}_q^n$, $\chi$ be a distribution over $D$, $\mathcal{H} = \emptyset$, and a uniformly chosen key $\kappa \in \mathcal{K}$. Given the matrices $\mat{A}$, $\mat{C}$, and the key $\kappa$, an adversary is able to query an oracle $O_\text{pre}$ adaptively, which on input $\vec{m} \in \mathcal{R}^\ell$ proceeds as follows.

  1. if $\norm{\vec{m}} > \beta_m$ then return $\perp$
  2. $x \sample \chi$
  3. $\vec{s} \sample \mat{A}_s^{-1}(f(x) + \mat{C} \cdot \vec{m})$
  4. $\mathcal{H} \leftarrow \mathcal{H} \cup \set{x,\vec{s},\vec{m}}$
  5. return $(x, \vec{s})$

An adversary is asked to find a new tuple $(x^{*}, \vec{s}^{*}, \vec{m}^{*})$ satisfying \[ (x^{*}, \vec{s}^{*}, \vec{m}^{*}) \notin \mathcal{H} \land \mat{A} \cdot \vec{s}^{*} = f(x^{*}) + \mat{C} \cdot \vec{m}^{*} \land \norm{\vec{s}^{*}} \leq \beta_s \land \norm{\vec{m}^{*}} \leq \beta_m. \]

Intuition. The interactive version extends GenISIS$_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 D$, which can be thought of as salt in the context of a signature whereas $\vec{s} \in \mathcal{R}^m$ is the signature.

Compared to the interactive version of ISIS$_f$, interactive GenISIS$_f$ introduces a “strong unforgeability” flavour.

Hardness

If $f$ is a random oracle then the GenISIS$_f$ instance, is at least as hard as SIS [4]. Furthermore, Lemma C.1 in [3] shows that the standard-model signature given in [5] can be adapted to GenISIS$_f$ s.t. the adapted GenISIS$_f$ instance is at least as hard as SIS in the standard model.

Dubois et al. [1] provide a translation of Theorem 3.3 from [2] to GenISIS$_f$, which states that interactive GenISIS$_f$ is at least as hard as GenISIS$_f$. This reduction comes with a polynomial loss factor within the size of queries to $O_\text{pre}$. This polynomial loss-factor is removed in a tight reduction given in Theorem 4.3 of [3].

Otherwise, the authors [1] show in Theorem 7 that GenISIS$_f$ is equivalent to the sEUF-RMA experiment for signatures based on vanishing SIS, which are introduced in the same work.

Constructions built from 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][6]
  • Anonymous credentials [2][6]

References

  • [1]Adrien Dubois, Michael Klooß, Russell W. F. Lai, and Ivy K. Y. Woo. 2025. Lattice-Based Proof-Friendly Signatures from Vanishing Short Integer Solutions. In Public-Key Cryptography - PKC 2025 - 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Røros, Norway, May 12-15, 2025, Proceedings, Part I (Lecture Notes in Computer Science), 2025. Springer, 452–486. Retrieved from https://ia.cr/2025/356
  • [2]Jonathan Bootle, Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Alessandro Sorniotti. 2023. A Framework for Practical Anonymous Credentials from Lattices. In Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part II (Lecture Notes in Computer Science), 2023. Springer, 384–417. Retrieved from https://ia.cr/2023/560
  • [3]Ngoc Khanh Nguyen and Jan Niklas Siemer. 2026. Tight Reductions for SIS-with-Hints Assumptions with Applications to Anonymous Credentials. Retrieved from https://ia.cr/2026/291
  • [4]Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. 2008. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, 2008. ACM, 197–206. Retrieved from https://ia.cr/2007/432
  • [5]Daniele Micciancio and Chris Peikert. 2012. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings (Lecture Notes in Computer Science), 2012. Springer, 700–718. Retrieved from https://ia.cr/2011/501
  • [6]Vadim Lyubashevsky, Gregor Seiler, and Patrick Steuer. 2024. The LaZer Library: Lattice-Based Zero Knowledge and Succinct Proofs for Quantum-Safe Privacy. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS 2024, Salt Lake City, UT, USA, October 14-18, 2024, 2024. ACM, 3125–3137. Retrieved from https://ia.cr/2024/1846