Paper 2025/844

Post-Quantum PKE from Unstructured Noisy Linear Algebraic Assumptions: Beyond LWE and Alekhnovich's LPN

Riddhi Ghosal, University of California, Los Angeles
Aayush Jain, Carnegie Mellon University
Paul Lou, University of California, Los Angeles
Amit Sahai, University of California, Los Angeles
Neekon Vafa, Massachusetts Institute of Technology
Abstract

Noisy linear algebraic assumptions with respect to random matrices, in particular Learning with Errors ($\mathsf{LWE}$) and Alekhnovich Learning Parity with Noise (Alekhnovich $\mathsf{LPN}$), are among the most investigated assumptions that imply post-quantum public-key encryption (PKE). They enjoy elegant mathematical structure. Indeed, efforts to build post-quantum PKE and advanced primitives such as homomorphic encryption and indistinguishability obfuscation have increasingly focused their attention on these two assumptions and their variants. Unfortunately, this increasing reliance on these two assumptions for building post-quantum cryptography leaves us vulnerable to potential quantum (and classical) attacks on Alekhnovich $\mathsf{LPN}$ and $\mathsf{LWE}$. Quantum algorithms is a rapidly advancing area, and we must stay prepared for unexpected cryptanalytic breakthroughs. Just three decades ago, a short time frame in the development of our field, Shor's algorithm rendered most then-popular number theoretic and algebraic assumptions quantumly broken. Furthermore, within the last several years, we have witnessed major classical and quantum breaks on several assumptions previously introduced for post-quantum cryptography. Therefore, we ask the following question: In a world where both $\mathsf{LWE}$ and Alekhnovich $\mathsf{LPN}$ are broken, can there still exist noisy linear assumptions that remain plausibly quantum hard and imply PKE? To answer this question positively, we introduce two natural noisy-linear algebraic assumptions that are both with respect to random matrices, exactly like $\mathsf{LWE}$ and Alekhnovich $\mathsf{LPN}$, but with different error distributions. Our error distribution combines aspects of both small norm and sparse error distributions. We design a PKE from these assumptions and give evidence that these assumptions are likely to still be secure even in a world where both the $\mathsf{LWE}$ and Alekhnovich $\mathsf{LPN}$ assumptions are simultaneously broken. We also study basic properties of these assumptions, and show that in the parameter settings we employ to build PKE, neither of them are ``lattice'' assumptions in the sense that we don't see a way to attack them using a lattice closest vector problem solver, except via $\mathsf{NP}$-completeness reductions.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2025
Keywords
public-key encryption
Contact author(s)
riddhi @ cs ucla edu
aayushja @ andrew cmu edu
pslou @ cs ucla edu
sahai @ cs ucla edu
nvafa @ mit edu
History
2025-05-16: approved
2025-05-12: received
See all versions
Short URL
https://ia.cr/2025/844
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/844,
      author = {Riddhi Ghosal and Aayush Jain and Paul Lou and Amit Sahai and Neekon Vafa},
      title = {Post-Quantum {PKE} from Unstructured Noisy Linear Algebraic Assumptions: Beyond {LWE} and Alekhnovich's {LPN}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/844},
      year = {2025},
      url = {https://eprint.iacr.org/2025/844}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.