Paper 2026/2927
On the Hardness of LWE with Trapdoor Hints and Applications to Fuzzy Cryptography
Abstract
Learning with Errors (LWE) and its variants have revolutionized modern cryptography, enabling a wide range of applications that previously seemed out of reach. In recent years, there has been growing interest in hinted variants of LWE, in which the adversary receives carefully structured side information, and these assumptions have further expanded the cryptographic toolkit. In this work, we study a natural hinted LWE assumption that we call LWE with Trapdoor Hints. Concretely, we consider the hardness of distinguishing an LWE sample $(\mathbf{A},\, \mathbf{s}^{\mathsf{T}}\mathbf{A}+\mathbf{e}^{\mathsf{T}} \bmod q)$ from uniform even in the presence of a full-rank homogeneous trapdoor $\mathbf{T}$ for $\mathbf{A}$. We show that when the error $\mathbf{e}$ is drawn from a Gaussian distribution that is only slightly wider than the decoding radius associated with $\mathbf{T}$, this problem remains hard under the standard LWE assumption. We then present two compelling applications of this problem that were previously out of reach: First, we construct the first Euclidean-ball obfuscator from LWE satisfying distributional virtual black-box security. Our construction achieves the functional preserving property, reusability, and distributional VBB security, assuming the obfuscated inputs are drawn from a suitable LWE-compatible distribution such as a discrete Gaussian. To the best of our knowledge, such a notion was not previously known even assuming indistinguishability obfuscation. As a byproduct, we resolve the open question posed by Fuller, Meng, and Reyzin (Asiacrypt 2013) concerning using lattice trapdoors to construct computational fuzzy extractors supporting the Euclidean metric and with drastically larger error tolerance. Second, we introduce a new primitive that we call Threshold Difference Revealing Encryption (TDRE), which can be viewed as a public-key, two-input analogue of fuzzy extractors. Standard fuzzy extractors are highly effective for fuzzy authentication, but they are fundamentally asymmetric and do not directly support the task of comparing two independently encoded, hidden biometrics. We believe that TDRE can help fill this important conceptual gap in current techniques for fuzzy cryptography.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. FOCS 2026
- Keywords
- Lattice-based CryptographyLearning with ErrorsFuzzy Cryptography
- Contact author(s)
-
dcsdiva @ nus edu sg
aayushja @ andrew cmu edu
rachel @ cs washington edu
yuetianw @ stanford edu - History
- 2026-11-22: approved
- 2026-11-18: received
- See all versions
- Short URL
- https://ia.cr/2026/2927
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2927,
author = {Divesh Aggarwal and Aayush Jain and Huijia Lin and Yuetian Wu},
title = {On the Hardness of {LWE} with Trapdoor Hints and Applications to Fuzzy Cryptography},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2927},
year = {2026},
url = {https://eprint.iacr.org/2026/2927}
}