One-More-ISIS

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

Formal Definition

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

Let matrix $𝐀 \in ℤ_{q}^{n \times m}$ and $T \subset ℤ_{q}^{n}$ be chosen uniformly at random. Given the challenge matrix $𝐀$ 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 preimage $\hat{𝐬} \leftarrow 𝐀_{s}^{- 1} (\hat{𝐭})$ . Let $k \in ℕ_{0}$ denote the number of times $O_{pre}$ was queried. Then, an adversary is asked to output a set ${𝐬_{i}}_{i \in [k + 1]}$ of $k + 1$ short preimages of target vectors in $T$ satisfying $\forall i \in [k + 1] : 𝐀 \cdot 𝐬_{i} \in T \land ‖ 𝐬_{i} ‖ \leq β .$

Hardness of One-More-ISIS

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 ${a \cdot 𝐞_{i} : a \in ℤ_{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 β$ . 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 $𝐀$ . 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 based on One-More-ISIS

Blind signature^[1]

Related Assumptions

References

↑ ^1.0 ^1.1 ^1.2 Agrawal, S., Kirshanova, E., Stehlé, D. and Yadav, A. Practical, round-optimal lattice-based blind signatures. Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022.
↑ 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 Agrawal, S., Kirshanova, E., Stehlé, D. and Yadav, A. Practical, round-optimal lattice-based blind signatures. Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022.

[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]