ISIS$_f$

Propose Edit

Updated:

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

Definition

ISIS$_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, and $f$ be a specified function $f: [N] \rightarrow \mathcal{R}_q^n$. The challenger generates $k$ hints $(x_i, \vec{s}_i)$ in the following way.

  • $x_i \sample [N]$
  • $\vec{s}_i \sample \mat{A}_s^{-1}(f(x_i))$

Given the matrix $\mat{A}$ 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 [N] \times \mathcal{R}^m$ satisfying \[\mat{A} \cdot \vec{s}^{*} = f(x^{*}) \bmod q \land 0 < \norm{\vec{s}^{*}} \leq \beta \land (x^{*}, \vec{s}^{*}) \notin \set{(x_i, \vec{s}_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 $\vec{s}^{*} \in \mathcal{R}^m$ short and finding a preimage of $\mat{A} \cdot \vec{s}^{*}$.
  • Assume $f$ is a linear function and the domain of $f$ was mapped to $\ZZ_N$. Then, any hint $(x_i, \vec{s}_i)$ can be used to generate a valid ISIS$_f$ solution $(-x_i, \vec{s}_i)$.

InteractiveISIS$_f$

Let $(n,m,\ell_m,\ell_r,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_m + \ell_r)}$ be chosen uniformly at random, $f$ be a specified function $f: [N] \rightarrow \mathcal{R}_q^n$, and $\mathcal{M} = \emptyset$. Given the matrices $\mat{A}$ and $\mat{C}$, an adversary is able to query an oracle $O_\text{pre}$ adaptively, which on input $(\vec{m}, \vec{r}) \in \mathcal{R}^{(\ell_m + \ell_r)}$ proceeds as follows.

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

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

Intuition. The interactive version extends 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 $\vec{s} \in \mathcal{R}^m$ is the signature.

Hardness

If $f$ is a random oracle then the ISIS$_f$ instance, is at least as hard as SIS [2].

Bootle et al. [1] set $f$ to be $f(x) = \mat{B} \cdot \operatorname{bin}(x)$, where $\operatorname{bin}: [N] \rightarrow \ZZ^{\ceil{\log N}}$ outputs the binary encoding of $x \in [N]$. They call this problem ISIS$_{\operatorname{bin}}$. The authors analyse direct lattice reduction as well as exploiting relations on the image space for ISIS$_{\operatorname{bin}}$.

In Theorem 3.3, Bootle et al. [1] show that interactive ISIS$_f$ is at least as hard as ISIS$_f$. The reduction uses $\mat{C} = \mat{A} \cdot \mat{R}$ for a uniformly chosen $\mat{R} \in \bin^{m \times (\ell_m + \ell_r)}$, rejection sampling, the entropy that $x \sample [N]$ and $\vec{s} \sample D_{\Lambda_q^{f(x)}, s}$ are sampled with and introduces a polynomial loss factor depending on the number of allowed queries to $O_\text{pre}$. This polynomial loss-factor is removed in a tight reduction given in Theorem 4.3 of [3] for Generalised ISIS$_f$.

Constructions built from ISIS$_f$

Bootle et al. [1] provide a framework to generically build the following constructions from any interactive ISIS$_f$ instance.

  • Signatures [1]
  • Group signatures [1]
  • Blind signatures [1][4]
  • Anonymous credentials [1][4]

References

  • [1]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
  • [2]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
  • [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]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