Paper 2026/2792
Independent Leakage Does Not Save Evasive LWE: Refuting Folklore Fixes in the Private-Coin Setting
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
-
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}
}