Crypto Reading Group - Jack Zhao-Post-Quantum PKE from Unstructured Noisy Linear Algebraic Assumptions: Beyond LWE and Alekhnovich’s LPN

Abstract:  Much of post-quantum PKE from unstructured noisy linear algebra relies on LWE or Alekhnovich’s LPN: both assume samples of the form (A, As+e) are computationally indistinguishable from (A, u), but with different noise models. LWE uses “short” errors, while Alekhnovich LPN uses sparse errors. Motivated by uncertainty around future cryptanalytic advances, we ask whether one can still obtain PKE from noisy linear assumptions even if both LWE and Alekhnovich LPN were broken. We talk about two new assumptions: Learning with Two Errors (LW2E), which mixes an LWE-style short error with an LPN-style sparse error, and Learning with Short and Sparse Errors (LWSSE), which uses errors that are simultaneously short and sparse but denser than Alekhnovich LPN.