View source for Randomised One-More-ISIS

The Randomised One-More-ISIS assumption was introduced in 2024 by Baldimtsi, Cheng, Goyal and Yadav.<ref name=":0">Baldimtsi, F., Cheng, J., Goyal, R. and Yadav, A. [https://eprint.iacr.org/2024/614.pdf 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.</ref> 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<sub>n,m,q,β,s</sub> ===
Let matrices <math>\mathbf{A}, \mathbf{B} \in \mathbb{Z}_q^{n \times m}</math> and <math>T \subset \mathbb{Z}_q^n</math> be chosen uniformly at random. Given the challenge matrices <math>\mathbf{A}</math> and <math>\mathbf{B}</math> and the set of target vectors <math>T</math>, an adversary can query a preimage oracle <math>O_\text{pre}</math> adaptively, which on input <math>\hat{\mathbf{t}} \in \mathbb{Z}_q^n</math> outputs a tuple <math>(\hat{\mathbf{s}}, \hat{\mathbf{u}})</math> containing a preimage <math>\hat{\mathbf{s}} \leftarrow \mathbf{A}_s^{-1}(\hat{\mathbf{t}} - \mathbf{B} \cdot \hat{\mathbf{u}})</math> and a uniformly chosen vector <math>\hat{\mathbf{s}} \leftarrow \{ -1,1 \}^m</math>. Let <math>k \in \mathbb{N}_0</math> denote the number of times <math>O_\text{pre}</math> was queried. Then, an adversary is asked to output a set <math>\{ (\mathbf{s}_i, \mathbf{u}_i) \}_{i \in [k+1]}</math> of <math>k+1</math> short preimages of target vectors in <math>T</math> satisfying <math>\forall i \in [k+1]: \mathbf{A} \cdot \mathbf{s}_i + \mathbf{B} \cdot \mathbf{u}_i \in T \land \lVert \mathbf{s}_i \rVert \leq \beta \land \mathbf{u}_i \in \{ -1,1 \}^m.</math>

'''Context.''' Compared to [[One-More-ISIS]], the randomised variant doubles the length of the challenge matrix by introducing <math>\mathbf{B} \in \mathbb{Z}_q^{n \times m}</math> but multiplies this part with a vector from <math>\{ -1, 1 \}^m</math> and restricts solutions to this set as well. The authors<ref name=":0" /> argue that multiplication <math>\mathbf{B} \cdot \hat{\mathbf{u}}</math> essentially randomises the target vector of the preimage queries. Ultimately, the restriction on <math>\mathbf{u}_i</math> to the set <math>\{-1,1\}^m</math> 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<ref name=":0" />

== Related Assumptions ==

* [[One-More-ISIS]]
* One-More-RSA<ref>Bellare, Namprempre, Pointcheval and Semanko. [https://doi.org/10.1007/s00145-002-0120-1 The one-more-RSA-inversion problems and the security of Chaum's blind signature scheme]. ''Journal of Cryptology'' 16.3 (2003): 185-215.</ref>
* ISIS<sub>f</sub>
* Generalised ISIS<sub>f</sub>

== References ==
<references />