Randomised One-More-ISIS

The Randomised One-More-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.

Formal Definition

Randomised One-More-ISIS_n,m,q,β,s

Let matrices $𝐀, 𝐁 \in ℤ_{q}^{n \times m}$ and $T \subset ℤ_{q}^{n}$ be chosen uniformly at random. Given the challenge matrices $𝐀$ and $𝐁$ and the set of target vectors $T$ , an adversary can query a preimage oracle $O_{pre}$ adaptively, which on input $\hat{𝐭} \in ℤ_{q}^{n}$ outputs a tuple $(\hat{𝐬}, \hat{𝐮})$ containing a preimage $\hat{𝐬} \leftarrow 𝐀_{s}^{- 1} (\hat{𝐭} - 𝐁 \cdot \hat{𝐮})$ and a uniformly chosen vector $\hat{𝐬} \leftarrow {- 1, 1}^{m}$ . Let $k \in ℕ_{0}$ denote the number of times $O_{pre}$ was queried. Then, an adversary is asked to output a set ${(𝐬_{i}, 𝐮_{i})}_{i \in [k + 1]}$ of $k + 1$ short preimages of target vectors in $T$ satisfying $\forall i \in [k + 1] : 𝐀 \cdot 𝐬_{i} + 𝐁 \cdot 𝐮_{i} \in T \land ‖ 𝐬_{i} ‖ \leq β \land 𝐮_{i} \in {- 1, 1}^{m} .$

Context. Compared to One-More-ISIS, the randomised variant doubles the length of the challenge matrix by introducing $𝐁 \in ℤ_{q}^{n \times m}$ but multiplies this part with a vector from ${- 1, 1}^{m}$ and restricts solutions to this set as well. The authors^[1] argue that multiplication $𝐁 \cdot \hat{𝐮}$ essentially randomises the target vector of the preimage queries. Ultimately, the restriction on $𝐮_{i}$ to the set ${- 1, 1}^{m}$ seems to make the assumption more robust than One-More-ISIS.

Hardness of Randomised One-More-ISIS

TODO

Constructions based on Randomised One-More-ISIS

Non-interactive blind signatures^[1]

Related Assumptions

One-More-ISIS
One-More-RSA^[2]
ISIS_f
Generalised ISIS_f

References

↑ ^1.0 ^1.1 ^1.2 Baldimtsi, F., Cheng, J., Goyal, R. and Yadav, A. Non-interactive blind signatures: post-quantum and stronger security. International Conference on the Theory and Application of Cryptology and Information Security. Singapore: Springer Nature Singapore, 2024.
↑ Bellare, Namprempre, Pointcheval and Semanko. The one-more-RSA-inversion problems and the security of Chaum's blind signature scheme. Journal of Cryptology 16.3 (2003): 185-215.

[:0-1] 1.0 ^1.1 ^1.2 Baldimtsi, F., Cheng, J., Goyal, R. and Yadav, A. Non-interactive blind signatures: post-quantum and stronger security. International Conference on the Theory and Application of Cryptology and Information Security. Singapore: Springer Nature Singapore, 2024.

[2] Bellare, Namprempre, Pointcheval and Semanko. The one-more-RSA-inversion problems and the security of Chaum's blind signature scheme. Journal of Cryptology 16.3 (2003): 185-215.

[1]

[2]

Formal Definition