Common Notation

Algebraic One-More-MISIS (AOM-MISIS) implied

Propose Edit

Updated:

Algebraic One-More Module-ISIS (AOM-MISIS) was introduced in 2025 by Zhu, and Tessaro [1], extending the notion of Algebraic One-More Preimage Resistance [2] for (lattice-based) hash-functions. Given a normal-form M-SIS challenge matrix, \(Q\) target vectors \(\vec{t}_i := \mat{A} \cdot \vec{s}_i\), and access to an oracle that on input a vector \(\vec{b} \in \mathcal{R}^Q\) responds with a linear combination of its secrets \(\sum_{i \in [Q]} b_i \cdot \vec{s}_i\), the assumption states that it remains hard to find a short preimage for a bounded linear combination of the target vectors, excluding trivial induced solutions.

Definition

Algebraic One-More-MISIS\(_{n,m,q,\mathcal{R},Q,(\sigma_i)_{i\in[Q]}, \beta_u,\beta_s,\beta_b}\)

Let \(q\) be an odd prime, \(\mathcal{R} = \ZZ[X] / (X^N + 1)\), \(\mathcal{R}_q = \ZZ_q[X] / (X^N + 1)\) and consider the distributions \(D_{\sigma_{i}}\) over \(\mathcal{R}\). Sample \(\bar{\mat{A}} \sample \mathcal{R}_q^{n \times m-n}\) and \([Q]\) vectors \(\vec{s}_i \sample D_{\sigma_i}^m\). Define an empty set \(B:=\emptyset\), a matrix \(\mat{A} := \begin{bmatrix} \bar{\mat{A}} &\mat{I}_n \end{bmatrix} \in \mathcal{R}_q^{n \times m}\) and vectors \(\vec{t}_i := \mat{A} \cdot \vec{s}_i\).

Given \(\mat{A}\) and \(\set{\vec{t}_i}_{i \in [Q]}\), the adversary can adaptively query an oracle with input \(\vec{b} \in \mathcal{R}^Q\), which adds \(\vec{b}\) to the set \(B\) and returns \(\sum_{i \in [Q]} b_i \cdot \vec{s}_i\). Then, the adversary is asked to output a tuple \((\hat{\vec{s}}, \hat{\vec{b}}, \vec{u})\) that satisfies the following conditions:

  1. \(\hat{\vec{s}}\) is a preimage of a combination of target vectors \(\vec{t}_i\) under the matrix \(\mat{A}\), i.e. \(\sum_{i \in [Q]} \hat{b}_i \cdot \vec{t}_i = \mat{A} \cdot \hat{\vec{s}}\),
  2. certain vectors have to be short: \(\norm{\hat{\vec{s}}} \leq \beta_s\), \(\norm{(\hat{b}_1 \cdot \sigma_1, \dots, \hat{b}_Q \cdot \sigma_Q)} \leq \beta_b\), \(\norm{(u_1/\sigma_1, \dots, u_Q/\sigma_Q)} \leq \beta_u\), and
  3. \(\vec{u}\) is orthogonal to all previously queried vectors \(\vec{b}\), i.e. \(\forall \vec{b} \in B: \vec{b}^T \cdot \vec{u} = 0\).

Hardness

The hardness of AOM-MISIS was proven in Theorem 1 by Tessaro, and Zhu [1] and reduced from the hardness of MSIS and MLWE for a judicious choice of parameters. Due to the definition, this result only holds for secrets sampled from discrete Gaussian distributions.

Constructions built from Algebraic One-More-ISIS

  • Algebraic One-More-MLWE defined the dual version of the assumption over the Module LWE.
  • One-More-ISIS defined the (non-algebraic) version of the assumption.
  • Algebraic One-More Discrete Logarithm [6] inspired Algebraic One-More-MSIS.

References

  • [1]Chenzhi Zhu and Stefano Tessaro. 2025. The Algebraic One-More MISIS Problem and Applications to Threshold Signatures. In Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part I (Lecture Notes in Computer Science), 2025. Springer, 548–581. Retrieved from https://ia.cr/2025/436
  • [2]Stefano Tessaro and Chenzhi Zhu. 2023. Threshold and Multi-signature Schemes from Linear Hash Functions. In Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V (Lecture Notes in Computer Science), 2023. Springer, 628–658. Retrieved from https://ia.cr/2023/276
  • [3]Rutchathon Chairattana-Apirom, Stefano Tessaro, and Chenzhi Zhu. 2024. Partially Non-interactive Two-Round Lattice-Based Threshold Signatures. 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 IV (Lecture Notes in Computer Science), 2024. Springer, 268–302. Retrieved from https://ia.cr/2024/467
  • [4]Thomas Espitau, Shuichi Katsumata, and Kaoru Takemure. 2024. Two-Round Threshold Signature from Algebraic One-More Learning with Errors. In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part VII (Lecture Notes in Computer Science), 2024. Springer, 387–424. Retrieved from https://ia.cr/2024/496
  • [5]Giacomo Borin, Sofía Celi, Rafael del Pino, Thomas Espitau, Shuichi Katsumata, Guilhem Niot, Thomas Prest, and Kaoru Takemure. 2026. Hermine: An Efficient Lattice-based FROST-like Threshold Signature. Retrieved from https://ia.cr/2026/419
  • [6]Jonas Nick, Tim Ruffing, and Yannick Seurin. 2021. MuSig2: Simple Two-Round Schnorr Multi-signatures. In Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part I (Lecture Notes in Computer Science), 2021. Springer, 189–221. Retrieved from https://ia.cr/2020/1261