Paper 2026/2792

Independent Leakage Does Not Save Evasive LWE: Refuting Folklore Fixes in the Private-Coin Setting

Yao-Ching Hsieh, University of Washington
Abstract

The evasive learning with errors (evasive LWE) assumption has enabled a wide range of advanced cryptographic constructions from lattices in the past few years. The simple intuition that LWE remains secure even when additional ``non-zeroizing'' short preimages are given has proved highly versatile in applications. Unfortunately, recent counterexamples have refuted its general private-coin formulations, showing that having the short preimages along with arbitrary auxiliary leakage about the secret and target matrices can invalidate this intuition. To preserve important applications, particularly witness encryption, the community has sought to repair the assumption by restricting the allowed leakage. One folklore proposal requires the secret and target matrices, together with their respective leakage, to be generated independently. This restriction appears to preserve the application to witness encryption while ruling out all previously known counterexamples. In this work, we refute this proposal. Assuming LWE and indistinguishability obfuscation, we show that both the binding and hiding variants of private-coin evasive LWE are false even with the independent sampler restriction. Our counterexamples exploit only auxiliary leakage about the target matrix. We sample the secret honestly from a standard uniform or Gaussian distribution, independently of the target and its leakage, and we use no auxiliary information about the secret.

Note: Correct a typo in the AI disclosure on the GPT version numbers.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Evasive LWE
Contact author(s)
ychsieh @ cs washington edu
History
2026-11-09: revised
2026-11-05: received
See all versions
Short URL
https://ia.cr/2026/2792
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2792,
      author = {Yao-Ching Hsieh},
      title = {Independent Leakage Does Not Save Evasive {LWE}: Refuting Folklore Fixes in the Private-Coin Setting},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2792},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2792}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.