Paper 2026/2927

On the Hardness of LWE with Trapdoor Hints and Applications to Fuzzy Cryptography

Divesh Aggarwal, National University of Singapore
Aayush Jain, Carnegie Mellon University
Huijia Lin, University of Washington
Yuetian Wu, Stanford University
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.