Simple and General Counterexamples for Private-Coin Evasive LWE

Nico Döttling; Abhishek Jain; Giulio Malavolta; Surya Mathialagan; Vinod Vaikuntanathan

Paper 2025/374 Original: eprint.iacr.org/2025/374 ↗

Simple and General Counterexamples for Private-Coin Evasive LWE

Nico Döttling

Abhishek Jain

Giulio Malavolta

Surya Mathialagan

Vinod Vaikuntanathan

Abstract

We present a simple counterexample to all known variants of the private-coin evasive learning with errors (LWE) assumption. Unlike prior works, our counterexample is direct, it does not use heavy cryptographic machinery (such as obfuscation or witness encryption), and it applies to all variants of the assumption. Our counterexample can be seen as a "zeroizing" attack against evasive LWE, calling into question the soundness of the underlying design philosophy.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
History: 2025-04-13: last updated; 2025-02-27: published
Short URL: https://ia.cr/2025/374
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2025/374,
      author = {Nico Döttling and Abhishek Jain and Giulio Malavolta and Surya Mathialagan and Vinod Vaikuntanathan},
      title = {Simple and General Counterexamples for Private-Coin Evasive LWE},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/374},
      year = {2025},
      url = {https://eprint.iacr.org/2025/374}
}