Continuous LWE

DOI10.1145/3406325.3451000MaRDI QIDQ6087037zbMATH OpenOpenAlexFDO

Authors

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.09595

zbMATH Keywords

computational learning theorycryptographylatticeslearning with errorsmixture of Gaussiansquantum computing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues of (quantum) attacks on lattice problems. Our work resolves an open problem regarding the computational complexity of learning mixtures of Gaussians without separability assumptions (Diakonikolas 2016, Moitra 2018). As an additional motivation, (a slight variant of) CLWE was considered in the context of robust machine learning (Diakonikolas et al.~FOCS 2017), where hardness in the statistical query (SQ) model was shown; our work addresses the open question regarding its computational hardness (Bubeck et al.~ICML 2019).

Cited in

(9)

• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Public-key encryption from homogeneous CLWE
• Revisiting security estimation for LWE with hints from a geometric perspective
• Hardness of (M)LWE with semi-uniform seeds
• Optimal transport map estimation in general function spaces
• Sparse linear regression and lattice problems
• SQ lower bounds for random sparse planted vector problem
• Improved hardness results for learning intersections of halfspaces
• Implementing a White-Box Undetectable Backdoor for Random Fourier Features

This page was built for publication: Continuous LWE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087037)