Simple and General Counterexamples for Private-Coin Evasive LWE

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

Paper 2025/374

Simple and General Counterexamples for Private-Coin Evasive LWE

Nico Döttling, Helmholtz Center for Information Security

Abhishek Jain, NTT Research, Johns Hopkins University

Giulio Malavolta, Bocconi University

Surya Mathialagan, Massachusetts Institute of Technology

Vinod Vaikuntanathan, Massachusetts Institute of Technology

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.
Keywords: Evasive LWE Attacks
Contact author(s): doettling @ cispa de
abhishek jain @ ntt-research com
giulio malavolta @ unibocconi it
smathi @ mit edu
vinodv @ mit edu
History: 2025-03-04: last of 2 revisions; 2025-02-27: received; See all versions
Short URL: https://ia.cr/2025/374
License: CC BY

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}
}