Randomised One-More-ISIS (rOM-ISIS)

Propose Edit

Updated:

The Randomised One-More-ISIS (rOM-ISIS) assumption was introduced in 2024 by Baldimtsi, Cheng, Goyal and Yadav [1]. Randomised One-More-ISIS differs only slightly from One-More-ISIS, but the authors claim that the randomised variant is more robust.

Definition

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

Let matrix $\mat{A}, \mat{B} \in \ZZ_q^{n \times m}$, and $T \subset \ZZ_q^n$ be chosen uniformly at random. Given the challenge matrices $\mat{A}$ and $\mat{B}$, 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 tuple $(\hat{\vec{s}}, \hat{\vec{u}})$ containing a preimage $\hat{\vec{s}} \sample \mat{A}_s^{-1}(\hat{\vec{s}} - \mat{B} \cdot \hat{\vec{u}})$ and a uniformly chosen vector $\hat{\vec{u}} \sample \bin^m$. 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, \vec{u}_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 + \mat{B} \cdot \vec{u}_i \in T \land \norm{\vec{s}_i} \leq \beta \land \vec{u}_i \in \set{-1,1}^m.\]

Context. Compared to One-More-ISIS, the randomised variant essentially imposes the restriction $\vec{u}_i \in \set{-1,1}^m$ for half of the preimage vector. Ultimately, the restriction on $\vec{u}_i$ to the set $\set{-1,1}^m$ can be seen as an introduction of the generalised knapsack problem to make the assumption more robust than One-More-ISIS.

Hardness

Baldimtsi et al. [1] dedicate Section 6.1 towards cryptanalysis of their assumption, where they recall and generalise the cryptanalytic approaches from [2] mounted on One-More-ISIS, and essentially show that the restriction $\vec{u}_i \in \set{-1,1}^m$ renders these attacks impractical. This leads them to their claim that Randomised One-More-ISIS is more robust than One-More-ISIS and more importantly, that they can pick parameters with significantly more freedom than for One-More-ISIS.

In Theorem 5.3 of [3], Nguyen and Siemer show that One-More-ISIS is at least as hard as Randomised One-More-ISIS. Furthermore, they analyse a binary version of rOM-ISIS switching the restriction from $\vec{u}_i \in \set{-1,1}^m$ to $\vec{u}_i \in \bin^m$ and show their equivalence in Lemma D.1.

Constructions built from rOM-ISIS

  • Non-interactive blind signature [1]

References

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