Evasive SIS

Propose Edit

Updated:

Evasive SIS was informally introduced by Wee in 2022 [1] (in conjunction with the public-coin Evasive LWE assumption) and envisioned as a tool for analysing the plausibility of SIS-based hinted lattice assumptions. However, the assumption was first formalised by Dubois, Klooß, Lai, and Woo in 2025 [2] to propose a family of proof-friendly signatures based on Vanishing SIS and Evasive SIS. \(\newcommand{\aux}{\mathsf{aux}} \newcommand{\Samp}{\mathsf{Samp}}\)

Definition

Define two experiments: \(\mathsf{Pre}\) and \(\mathsf{Post}\).

\(\mathsf{Pre}_\adv\left(1^\lambda\right)\) \(\mathsf{Post}_\bdv\left(1^\lambda\right)\)
\((\mat{P}, \mat{A}, \aux) \gets \Samp\left(1^\lambda\right)\) \((\mat{P}, \mat{A}, \aux) \gets \Samp\left(1^\lambda\right)\)
\(\mat{B} \sample \mathcal{R}_q^{n \times m}\) \(\mat{B} \sample \mathcal{R}_q^{n \times m}\)
  \(\mat{U} \sample D_{\mathcal{R},s}^{m \times m_P}\) conditioned on \(\mat{B} \cdot \mat{U} = \mat{P}\)
\(\vec{u}^* \gets \adv(\mat{B}, \mat{P}, \mat{A}, \aux)\) \(\vec{u}^* \gets \bdv(\mat{B}, \mat{P}, \mat{A}, \mat{U}, \aux)\)
\(b_0 = \left( \begin{bmatrix} \mat{B} &\mat{P} &\mat{A} \end{bmatrix} \cdot \vec{u}^* = \vec{0} \right)\) \(b_0 = \left( \begin{bmatrix} \mat{B} &\mat{A} \end{bmatrix} \cdot \vec{u}^* = \vec{0} \right)\)
\(b_1 = \left( 0 < \norm{\vec{u}^*} \leq \beta_0 \right)\) \(b_1 = \left( 0 < \norm{\vec{u}^*} \leq \beta_1 \right)\)
return \(b_0 \land b_1\) return \(b_0 \land b_1\)

Evasive SIS\(_{\mathcal{R},q,n,m,m_P,m_A,s,\beta_0,\beta_1}\)

Let \(\mathcal{R}\) be a ring admitting an embedding as a lattice in \(\RR^\varphi\) for some \(\varphi \in \NN\) and \(s, \beta_0, \beta_1 > 0\). Let \(\Samp\) be a ppt algorithm which, on input \(1^\lambda\), outputs \((\mat{P}, \mat{A}, \aux)\) \(\in\) \(\mathcal{R}_q^{n\times m_P} \times \mathcal{R}_q^{n \times m_A} \times \set{0,1}^*\), where \(\aux\) contains all coin tosses used by \(\Samp\). The Evasive SIS assumption states that for any ppt \(\Samp\) and \(\bdv\) there exists a ppt \(\adv\) such that

\[\Pr\left[\mathsf{Pre}_\adv\left(1^\lambda\right) = 1 \right] \geq \Pr\left[\mathsf{Post}_\bdv\left(1^\lambda\right) = 1\right]/\poly{\lambda} - \negl{\lambda}.\]

Intuitively, the evasive SIS assumption states that “if SIS is hard for the matrix \(\begin{bmatrix} \mat{B} &\mat{P} &\mat{A} \end{bmatrix}\), then SIS is hard for \(\begin{bmatrix} \mat{B} &\mat{A} \end{bmatrix}\) even given short preimages \(\mat{U}\) s.t. \(\mat{B} \cdot \mat{U} = \mat{P}\)”. This stems from the intuition that, there seems no alternative meaningful use of \(\mat{U}\), other than multiplying with \(\mat{B}\) to obtain \(\mat{P}\) and solve (the potentially easier) SIS problem for \(\begin{bmatrix} \mat{B} &\mat{P} &\mat{A} \end{bmatrix}\) jointly.

The presented definition is public-coin, i.e. \(\Samp\) has to output all its random coins, which avoids most known obfuscation-based counterexamples against private-coin evasive LWE [3][4][5]. Shortly after this paper was published, [6] provided counterexamples against public-coin Evasive LWE in an unnatural parameter regime and a small refinement of the assumption.

Hardness

In Section 2.3 of [2], the authors note that Evasive SIS is heuristically at least as hard as public-coin Evasive LWE by following a common heuristic that solving decision-LWE is no easier than solving SIS (which is quantumly true for random matrices [7]).

Constructions built from Evasive SIS

  • Proof-friendly signatures [2]

References

  • [1]Hoeteck Wee. 2022. Optimal Broadcast Encryption and CP-ABE from Evasive Lattice Assumptions. In Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part II (Lecture Notes in Computer Science), 2022. Springer, 217–241. Retrieved from https://ia.cr/2023/906
  • [2]Adrien Dubois, Michael Klooß, Russell W. F. Lai, and Ivy K. Y. Woo. 2025. Lattice-Based Proof-Friendly Signatures from Vanishing Short Integer Solutions. In Public-Key Cryptography - PKC 2025 - 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Røros, Norway, May 12-15, 2025, Proceedings, Part I (Lecture Notes in Computer Science), 2025. Springer, 452–486. Retrieved from https://ia.cr/2025/356
  • [3]Chris Brzuska, Akin Ünal, and Ivy K. Y. Woo. 2024. Evasive LWE Assumptions: Definitions, Classes, and Counterexamples. 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, 418–449. https://doi.org/10.1007/978-981-96-0894-2_14
  • [4]Nico Döttling, Abhishek Jain, Giulio Malavolta, Surya Mathialagan, and Vinod Vaikuntanathan. 2025. Simple and General Counterexamples for Private-Coin Evasive LWE. In Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part VII (Lecture Notes in Computer Science), 2025. Springer, 73–92. Retrieved from https://ia.cr/2025/374
  • [5]Tzu-Hsiang Huang, Wei-Hsiang Hung, and Shota Yamada. 2026. A Note on Obfuscation-Based Attacks on Private-Coin Evasive LWE. IACR Commun. Cryptol. 2, 4 (2026), 20. Retrieved from https://ia.cr/2025/421
  • [6]Shweta Agrawal, Anuja Modi, Anshu Yadav, and Shota Yamada. 2025. Zeroizing Attacks Against Evasive and Circular Evasive LWE. In Theory of Cryptography - 23rd International Conference, TCC 2025, Aarhus, Denmark, December 1-5, 2025, Proceedings, Part II (Lecture Notes in Computer Science), 2025. Springer, 259–290. https://doi.org/10.1007/978-3-032-12293-3_9
  • [7]Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. 2009. Efficient Public Key Encryption Based on Ideal Lattices. In Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings (Lecture Notes in Computer Science), 2009. Springer, 617–635. Retrieved from https://ia.cr/2009/285