Common Notation

Evasive LWE

Propose Edit

Updated:

Evasive LWE was first proposed by Wee in 2022 [1]. The assumption intends to relate the hardness of two LWE problems with and without preimages. \(\newcommand{\aux}{\mathsf{aux}} \newcommand{\Samp}{\mathsf{Samp}} \newcommand{\tr}{\mathsf{T}}\)

Intuitively, the assumption states that given a discrete Gaussian preimage matrix \(\mat{U}\) satisfying \(\mat{A} \cdot \mat{U} = \mat{P} \bmod q\) for some target matrix \(\mat{P}\), alongside a challenge \(\vec{c}^\tr\) (which is either an LWE sample vector \(\vec{s}^\tr \cdot \mat{A} + \vec{e}^\tr \bmod q\) or uniform). The assumption asserts that the only meaningful use of \(\mat{U}\) is to right-multiply \(\vec{c}^\tr\) by it to obtain \(\vec{s}^\tr \cdot \mat{P} + \text{error} \bmod q\) in an attempt to distinguish the cases, using the resulting product together with the original challenge.

Formally, this is captured by a pair of \(\mathsf{Pre}\) and \(\mathsf{Post}\) experiments, where \(\mathsf{Post}\) represents the LWE-with-preimages problem, and \(\mathsf{Pre}\) represents an LWE problem induced by the aforementioned right-multiplication operation without handing out the preimage matrix \(\mat{U}\), modelling the resulting product as fresh LWE samples.

Definition [1]

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{B}, \aux) \gets \Samp\left(1^\lambda\right)\) \((\mat{P}, \mat{B}, \aux) \gets \Samp\left(1^\lambda\right)\)
\(\mat{A} \sample \ZZ_q^{n \times m}\) \(\mat{A} \sample \ZZ_q^{n \times m}\)
\(\vec{s} \sample \ZZ_q^{n}\) \(\vec{s} \sample \ZZ_q^{n}\)
if \(b=0\) then if \(b=0\) then
\(\quad \vec{e}_A \sample D_{\ZZ,\chi_A}^{m}, \vec{e}_B \sample D_{\ZZ,\chi_B}^{m_B}, \vec{e}_P \sample D_{\ZZ,\chi_P}^{m_P}\) \(\quad \vec{e}_A \sample D_{\ZZ,\chi_A}^{m}, \vec{e}_B \sample D_{\ZZ,\chi_B}^{m_B}\)
\(\quad \vec{c}_A^\tr = \vec{s}^\tr \mat{A} + \vec{e}_A^\tr \bmod q\) \(\quad \vec{c}_A^\tr = \vec{s}^\tr \mat{A} + \vec{e}_A^\tr \bmod q\)
\(\quad \vec{c}_B^\tr = \vec{s}^\tr \mat{B} + \vec{e}_B^\tr \bmod q\) \(\quad \vec{c}_B^\tr = \vec{s}^\tr \mat{B} + \vec{e}_B^\tr \bmod q\)
\(\quad \vec{c}_P^\tr = \vec{s}^\tr \mat{P} + \vec{e}_P^\tr \bmod q\) \(\quad \mat{U} \sample D_{\Lambda_q^{\mat{P}}(\mat{A}), \sigma}\)
if \(b=1\) then if \(b=1\) then
\(\quad \vec{c}_A \sample \ZZ_q^{m}\) \(\quad \vec{c}_A \sample \ZZ_q^{m}\)
\(\quad \vec{c}_B \sample \ZZ_q^{m_B}\) \(\quad \vec{c}_B \sample \ZZ_q^{m_B}\)
\(\quad \vec{c}_P \sample \ZZ_q^{m_P}\) \(\quad \mat{U} \sample D_{\Lambda_q^{\mat{P}}(\mat{A}), \sigma}\)
return \(b = \adv(\mat{A}, \mat{B}, \mat{P}, \vec{c}_A, \vec{c}_B, \vec{c}_P, \aux)\) return \(b = \bdv(\mat{A}, \mat{B}, \mat{P}, \vec{c}_A, \vec{c}_B, \mat{U}, \aux)\)

Evasive LWE\(_{q,n,m,m_B,m_P,\chi_A,\chi_B,\chi_P,\sigma}\)

Let \(\Samp\) be a ppt algorithm which, on input \(1^\lambda\), outputs \((\mat{P}, \mat{B}, \aux)\) \(\in\) \(\ZZ_q^{n \times m_P} \times\) \(\ZZ_q^{n \times m_B} \times\) \(\set{0,1}^*\), where \(\aux\) contains all coin tosses used by \(\Samp\). Let \(\chi_A\), \(\chi_B\), \(\chi_P\), and \(\sigma\) be positive Gaussian widths. The Evasive LWE assumption states that for any ppt \(\Samp\) and \(\bdv\) there exists a ppt \(\adv\), a polynomial \(\poly{\cdot}\) and a negligible function \(\negl{\cdot}\), such that

\[\mathsf{Adv}_\adv^\mathsf{Pre}(\lambda) \geq \mathsf{Adv}_\bdv^\mathsf{Post}(\lambda) / \poly{\lambda} - \negl{\lambda}.\]

The paper by Wee [1] discusses the public-coin sampler property of its assumption, and the literature commonly refers to it as public-coin Evasive LWE. There are numerous Evasive LWE variants and related attacks, including incomparable variants carrying the same name (see Variants below). No existing attack applies to the variant above, except under unnatural choices of parameters (see the second note below). A special case of this assumption, together with standard LWE, is known to imply the Succinct LWE assumption (see Evasive LWE (Wee24) below).

Note on Adaption: The above definition is adapted from [1] with the following changes: (1) each error vector and the preimage matrix \(\mat{U}\) is equipped with its own Gaussian width parameter, and (2) the distinguishers \(\adv\) and \(\bdv\) are explicitly given \(\mat{P}\) as input. The first is to allow for more general parameter settings, to allow for a more fine-grained analysis in different regimes. The second is only for clarity and does not change the assumption, since \(\mat{P}\) is recoverable from the coin tosses of \(\Samp\), which are included in \(\aux\). There are also minor presentation and notational changes, which do not affect the actual assumption and are there to increase consistency with the other entries in this Zoo.

Note on Sensitivity of Gaussian widths: In Remark 2 of [1], it is noted that the Gaussian widths of the errors and preimages influence the assumption’s strength, in that larger error and preimage widths in \(\mathsf{Post}\) (hence harder to win \(\mathsf{Post}\)), and/or smaller error widths in \(\mathsf{Pre}\) (hence easier to win \(\mathsf{Pre}\)), lead to a weaker assumption. In [2], it is shown that if the error width \(\chi_P\) in \(\mathsf{Pre}\) is super-polynomially larger than the error and preimage widths \(\chi_A,\sigma\) in \(\mathsf{Post}\), then there are simple counterexamples to the assumption. The counterexamples crucially rely on these unusual parameter choices and do not apply otherwise.

Variants

The section on variants is currently:

🚧 Under Construction 🚧

The intuition behind Evasive LWE has been formalised in numerous ways in the literature, primarily by defining different pairs of \(\mathsf{Pre}\) and \(\mathsf{Post}\) experiments, or changing the quantification of the sampler class. Many variants are formally incomparable. Sometimes different definitions are referred to by the same name (e.g. public-coin Evasive LWE), while some are not given a specific name beyond Evasive LWE.

To avoid confusion or misunderstanding that may arise from naming, the following list of variants refers to each by the paper which introduced it, instead of trying to endow each with a name. If a particular assumption name has been used in the paper, this is noted below.

The list attempts to include the majority of variants in the literature, but is not meant to be exhaustive.

Evasive LWE (WWW22)

Waters, Wee, and Wu [3] define a variant for constructing a multi-authority ABE for subset policies based on a variant of Evasive LWE. The \(\mathsf{Pre}\) and \(\mathsf{Post}\) experiments consist of multiple tuples of LWE samples (including their preimages in \(\mathsf{Post}\)) and further LWE samples with a correlated LWE secret. Similar to [1], the work [3] discusses the public-coin sampler property of the assumption, and it is commonly called public-coin Evasive LWE.

Evasive LWE (VWW22) broken

Vaikuntanathan, Wee, and Wichs [4] define a variant to prove the security of witness encryption (WE) schemes and null-iO constructions from [5]. It quantifies over a class of samplers that can generate the secret \(\vec{s}\), the image \(\mat{P}\) and the auxiliary input \(\aux\) together. The matrix \(\mat{A}\) is not available to the distinguishers. Likewise, \(\mat{P}\) and the coins used by \(\Samp\) are not necessarily available. The work [4] calls this private-coin Evasive LWE.

The first attack and fix on this variant are given in [6]. The proposed fix is subsequently broken by [6] in its eprint update, concurrently also in [7] and [8]. None of the attacks apply to the WE or null-iO constructions in [5].

A morally similar (although formally different) assumption is given in [9], also used for constructing WE and attacked in [6].

Evasive LWE (HLL23) broken

Hsieh, Lin, and Luo [10] introduce a variant called Evasive circular small-secret LWE for constructing unbounded-depth ABE. The \(\mathsf{Pre}\) and \(\mathsf{Post}\) experiments involve, among others, a GSW encryption [11] of the LWE secret and circular LWE samples where the matrix encodes the GSW encryption.

An attack on this assumption is given in [2]. The attack does not apply to the ABE construction in [10].

Evasive LWE (ARYY23) broken

Agrawal, Rossi, Yadav, and Yamada [12] define a variant for constructing multi-input ABE. It is similar to the VWW22 variant, with a difference: the matrix \(\mat{A}\) is given to the distinguishers. This makes the two formally incomparable.

The first attack and fix on this variant are given in [6]. The proposed fix is subsequently broken by [6] in its eprint update, concurrently also in [7] and [8]. None of the attacks apply to the multi-input ABE construction in [12].

Evasive LWE (Wee24)

Wee [13] considers a special case of the assumption in [1], where \(\mat{B}\) and \(\vec{c}_B\) are dropped. This special case is informally described in [1] although not formalised therein. This work [13] shows that, under appropriate parameters, this special case together with the standard LWE assumption implies the \(\ell\)-succinct LWE assumption.

Evasive LWE (BÜW24 Def. 7)

Brzuska, Ünal, and Woo [6] (Definition 7) attempt to provide a general definition to capture different versions of public-coin Evasive LWE in the literature. They refer to it as public-coin Evasive LWE.

Evasive LWE (BÜW24 Def. 8, 9) broken

Further, Brzuska, Ünal, and Woo [6] attempt to characterise private-coin Evasive LWE variants in the literature. Their work provides two different definitions (Definitions 8 and 9), called private-coin binding Evasive LWE and private-coin hiding Evasive LWE.

After its publication, the eprint update of [6] provides attacks on both variants. Concurrently, [7] and [8] also provide attacks on these variants using different techniques.

Evasive LWE (BDJMMPV25) broken

Branco, Döttling, Jain, Malavolta, Mathialagan, Peters, and Vaikuntanathan [14] define a variant for constructing pseudorandom iO, a primitive introduced in the same work. The construction, and therefore also the assumption, is attacked in [2].

Evasive LWE (AKY25)

In the first eprint appearance of [15], the ARYY23 variant is used to construct pseudorandom functional encryption, a primitive introduced in the same work. The construction, and therefore also the assumption, is attacked in [2]. Subsequently, [15] refines its construction and defines a restricted form of the assumption that is sufficient for proving the security of the refined construction.

Constructions built from Evasive LWE

This is a non-exhaustive list of constructions, whose security is or can be based on Evasive LWE (and all of its variants).

  • Broadcast Encryption [1]
  • Witness Encryption [9][4]
  • Zero-Knowledge SNARKs for UP [16]
  • SNARGs for NP [17]
  • Pseudorandom Obfuscation [14]
  • Pseudorandom Functional Encryption [15][18]
  • Multi-Authority ABE [3]
  • ABE for Turing Machines [19]
  • Constant-Input ABE [12]
  • Unbounded Depth ABE [10]
  • Evasive SIS is the SIS version of Evasive LWE.
  • \(\ell\)-Succinct LWE is an assumption implied by Evasive LWE (Wee22, Wee24) together with standard LWE. A number of applications formerly from Evasive LWE are now known from \(\ell\)-succinct LWE.

Further Reading Suggestions

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]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
  • [3]Brent Waters, Hoeteck Wee, and David J. Wu. 2022. Multi-authority ABE from Lattices Without Random Oracles. In Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part I (Lecture Notes in Computer Science), 2022. Springer, 651–679. Retrieved from https://ia.cr/2022/1194
  • [4]Vinod Vaikuntanathan, Hoeteck Wee, and Daniel Wichs. 2022. Witness Encryption and Null-IO from Evasive LWE. In Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part I (Lecture Notes in Computer Science), 2022. Springer, 195–221. Retrieved from https://ia.cr/2022/1140
  • [5]Yilei Chen, Vinod Vaikuntanathan, and Hoeteck Wee. 2018. GGH15 Beyond Permutation Branching Programs: Proofs, Attacks, and Candidates. In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part II (Lecture Notes in Computer Science), 2018. Springer, 577–607. Retrieved from https://ia.cr/2018/360
  • [6]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
  • [7]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
  • [8]Yao-Ching Hsieh, Aayush Jain, and Huijia Lin. 2025. Lattice-Based Post-quantum iO from Circular Security with Random Opening Assumption. 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, 3–38. Retrieved from https://ia.cr/2025/390
  • [9]Rotem Tsabary. 2022. Candidate Witness Encryption from Lattice Techniques. In Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part I (Lecture Notes in Computer Science), 2022. Springer, 535–559. https://doi.org/10.1007/978-3-031-15802-5_19
  • [10]Yao-Ching Hsieh, Huijia Lin, and Ji Luo. 2023. Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, 2023. IEEE, 415–434. Retrieved from https://ia.cr/2023/1716
  • [11]Craig Gentry, Amit Sahai, and Brent Waters. 2013. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I (Lecture Notes in Computer Science), 2013. Springer, 75–92. Retrieved from https://ia.cr/2013/340
  • [12]Shweta Agrawal, Mélissa Rossi, Anshu Yadav, and Shota Yamada. 2023. Constant Input Attribute Based (and Predicate) Encryption from Evasive and Tensor LWE. In Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part IV (Lecture Notes in Computer Science), 2023. Springer, 532–564. Retrieved from https://ia.cr/2023/941
  • [13]Hoeteck Wee. 2024. Circuit ABE with poly(depth,\(λ\))-Sized Ciphertexts and Keys from Lattices. In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part III (Lecture Notes in Computer Science), 2024. Springer, 178–209. Retrieved from https://ia.cr/2024/1416
  • [14]Pedro Branco, Nico Döttling, Abhishek Jain, Giulio Malavolta, Surya Mathialagan, Spencer Peters, and Vinod Vaikuntanathan. 2025. Pseudorandom Obfuscation and Applications. In Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part V (Lecture Notes in Computer Science), 2025. Springer, 663–698. Retrieved from https://ia.cr/2024/1742
  • [15]Shweta Agrawal, Simran Kumari, and Shota Yamada. 2024. Compact Pseudorandom Functional Encryption from Evasive LWE. IACR Cryptol. ePrint Arch. 2024, (2024), 1719. Retrieved from https://ia.cr/2024/1719
  • [16]Surya Mathialagan, Spencer Peters, and Vinod Vaikuntanathan. 2024. Adaptively Sound Zero-Knowledge SNARKs for UP. In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part X (Lecture Notes in Computer Science), 2024. Springer, 38–71. Retrieved from https://ia.cr/2024/227
  • [17]Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, and Surya Mathialagan. 2025. Universal SNARGs for NP from Proofs of Correctness. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, 2025. ACM, 933–943. Retrieved from https://ia.cr/2024/2015
  • [18]Shweta Agrawal, Simran Kumari, and Shota Yamada. 2024. Pseudorandom Multi-Input Functional Encryption and Applications. IACR Cryptol. ePrint Arch. 2024, (2024), 1720. Retrieved from https://ia.cr/2024/1720
  • [19]Shweta Agrawal, Simran Kumari, and Shota Yamada. 2024. Attribute Based Encryption for Turing Machines from Lattices. In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part III (Lecture Notes in Computer Science), 2024. Springer, 352–386. Retrieved from https://ia.cr/2025/001