One-More-ISIS (OM-ISIS)

Propose Edit

Updated:

One-More-ISIS (OM-ISIS) was introduced in 2022 by Agrawal, Kirshanova, Stehlé, and Yadav [1]. The assumption states that, given an ISIS solver, it remains hard to compute an additional preimage for a polynomial number of possible ISIS targets.

Definition

One-More-ISIS$_{n,m,q,\beta,s}$

Let matrix $\mat{A} \in \ZZ_q^{n \times m}$ and $T \subset \ZZ_q^n$ be chosen uniformly at random. Given the challenge matrix $\mat{A}$ and the set of target vectors $T$, an adversary can query a preimage oracle $O_\text{pre}$ adaptively, which on input $\hat{\vec{t}} \in \ZZ_q^n$ outputs a preimage $\hat{\vec{s}} \sample \mat{A}_s^{-1}(\hat{\vec{s}})$. Let $k \in \NN_0$ denote the number of times $O_\text{pre}$ was queried. Then, an adversary is asked to output a set $\set{\vec{s}_i}_{i \in [k+1]}$ of $k+1$ short preimages of target vectors in $T$ satisfying \[\forall i \in [k+1]: \mat{A}\cdot \vec{s}_i \in T \land \norm{\vec{s}_i} \leq \beta.\]

Hardness

The hardness of One-More-ISIS is analysed using direct cryptanalysis in the original paper [1]. The authors give a combinatorial attack and a lattice attack.

Combinatorial Attack. The adversary requests $n \cdot q$ preimages for all $\set{a \cdot \vec{e}_i : a \in \ZZ_q}_{i \in [n]}$. Then, the adversary can compute preimages for any image by adding up at most n preimages. As the length of the preimages returned by the challenger is $s \sqrt{m}$, it allows to solve the One-more-ISIS problem if $s \cdot \sqrt{n \cdot m} \leq \beta$. The attack can be adapted to smaller and larger sets of preimages, increasing and decreasing the output norm, respectively.

Lattice Attack. The adversary requests more than $m$ preimages of zero. Then, the adversary can produce a short basis trapdoor for $\mat{A}$. This trapdoor is of degraded quality relative to the trapdoor used by the challenger. They explore further options to improve the quality of the short basis trapdoor.

Constructions built from One-More-ISIS

  • Blind signature [1]
  • Non-interactive blind signature constructed in [2] based on the reduction in Theorem 5.3 of [3]

Further Reading Suggestions

References

  • [1]Shweta Agrawal, Elena Kirshanova, Damien Stehlé, and Anshu Yadav. 2022. Practical, Round-Optimal Lattice-Based Blind Signatures. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, 2022. ACM, 39–53. Retrieved from https://ia.cr/2021/1565
  • [2]Foteini Baldimtsi, Jiaqi Cheng, Rishab Goyal, and Aayush Yadav. 2024. Non-Interactive Blind Signatures: Post-Quantum and Stronger Security. In Advances in Cryptology - ASIACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9-13, 2024, Proceedings, Part II (Lecture Notes in Computer Science), 2024. Springer, 70–104. Retrieved from https://ia.cr/2024/614
  • [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]Mihir Bellare, Chanathip Namprempre, David Pointcheval, and Michael Semanko. 2003. The One-More-RSA-Inversion Problems and the Security of Chaum’s Blind Signature Scheme. J. Cryptol. 16, 3 (2003), 185–215. https://doi.org/10.1007/S00145-002-0120-1