More Web Proxy on the site http://driver.im/

research-article

Public Access

Continuous LWE

Authors:

Yi TangAuthors Info & Claims

STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

Pages 694 - 707

https://doi.org/10.1145/3406325.3451000

Published: 15 June 2021 Publication History

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).

References

[1]

Dorit Aharonov and Oded Regev. 2005. Lattice problems in NP \cap CoNP. J. ACM, 52, 5, 2005. Pages 749–765. issn:0004-5411 https://doi.org/10.1145/1089023.1089025

Digital Library

[2]

Miklós Ajtai and Cynthia Dwork. 1997. A public-key cryptosystem with worst-case/average-case equivalence. In STOC. Pages 284–293. isbn:0897918886 https://doi.org/10.1145/258533.258604

Digital Library

[3]

Sanjeev Arora and Rong Ge. 2011. New algorithms for learning in presence of errors. In ICALP. Pages 403–415.

[4]

Sanjeev Arora and Ravi Kannan. 2005. Learning mixtures of separated nonspherical Gaussians. Ann. Appl. Probab., 15, 2005. Pages 69–92. https://doi.org/10.1214/105051604000000512

[5]

László Babai. 1986. On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica, 6, 1, 1986. Pages 1–13. issn:0209-9683 https://doi.org/10.1007/BF02579403

Digital Library

[6]

Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. 2013. Classical hardness of learning with errors. In STOC. Pages 575–584. https://doi.org/10.1145/2488608.2488680

Digital Library

[7]

Spencer Charles Brubaker and Santosh Vempala. 2008. Isotropic PCA and affine-invariant clustering. In FOCS. Pages 551–560. https://doi.org/10.1109/FOCS.2008.48

Digital Library

[8]

Sebastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. 2019. Adversarial examples from computational constraints. In ICML. 97, Pages 831–840.

[9]

Sanjoy Dasgupta. 1999. Learning mixtures of Gaussians. In FOCS. Pages 634. isbn:0769504094

[10]

Sanjoy Dasgupta and Leonard Schulman. 2007. A probabilistic analysis of EM for mixtures of separated, spherical Gaussians. JMLR, 8, 2007. Pages 203–226. issn:1532-4435

[11]

Luc Devroye, Abbas Mehrabian, and Tommy Reddad. 2018. The total variation distance between high-dimensional Gaussians.

[12]

Ilias Diakonikolas. 2016. Learning structured distributions. In Handbook of Big Data. Chapman and Hall/CRC. Pages 267–284. https://doi.org/10.1201/b19567-21

[13]

Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. 2017. Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures. In FOCS. Pages 73–84. https://doi.org/10.1109/FOCS.2017.16

[14]

Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. 2018. List-decodable robust mean estimation and learning mixtures of spherical Gaussians. In STOC. Pages 1047–1060. https://doi.org/10.1145/3188745.3188758

Digital Library

[15]

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, and Ying Xiao. 2017. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64, 2, 2017. https://doi.org/10.1145/3046674

Digital Library

[16]

Samuel B. Hopkins and Jerry Li. 2018. Mixture models, robustness, and sum of squares proofs. In STOC. Pages 1021–1034. https://doi.org/10.1145/3188745.3188748

Digital Library

[17]

Sushrut Karmalkar, Adam Klivans, and Pravesh Kothari. 2019. List-decodable linear regression. In NeurIPS. Pages 7425–7434.

[18]

Michael Kearns. 1998. Efficient noise-tolerant learning from statistical queries. J. ACM, 45, 6, 1998. Pages 983–1006. issn:0004-5411 https://doi.org/10.1145/293347.293351

Digital Library

[19]

Pravesh K. Kothari, Jacob Steinhardt, and David Steurer. 2018. Robust moment estimation and improved clustering via sum of squares. In STOC. Pages 1035–1046. https://doi.org/10.1145/3188745.3188970

Digital Library

[20]

Arjen K. Lenstra, Hendrik W. Lenstra, and László Lovász. 1982. Factoring polynomials with rational coefficients. Math. Ann., 261, 4, 1982. Pages 515–534. issn:1432-1807 https://doi.org/10.1007/BF01457454

[21]

Vadim Lyubashevsky and Daniele Micciancio. 2009. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In CRYPTO. Pages 577–594. https://doi.org/10.1007/978-3-642-03356-8_34

Digital Library

[22]

Daniele Micciancio and Chris Peikert. 2012. Trapdoors for lattices: simpler, tighter, faster, smaller. In EUROCRYPT. Pages 700–718. https://doi.org/10.1007/978-3-642-29011-4_41

Digital Library

[23]

Daniele Micciancio and Oded Regev. 2007. Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput., 37, 1, 2007. Pages 267–302. issn:0097-5397 https://doi.org/10.1137/S0097539705447360

Digital Library

[24]

Hermann Minkowski. 1910. Geometrie der Zahlen. B.G. Teubner.

[25]

Ankur Moitra. 2018. Algorithmic aspects of machine learning. Cambridge University Press. https://doi.org/10.1017/9781316882177

[26]

Ankur Moitra and Gregory Valiant. 2010. Settling the polynomial learnability of mixtures of Gaussians. In FOCS. Pages 93–102. https://doi.org/10.1109/FOCS.2010.15

Digital Library

[27]

Karl Pearson. 1894. Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A, 185, 1894. Pages 71–110.

[28]

Chris Peikert. 2010. An efficient and parallel Gaussian sampler for lattices. In CRYPTO. Pages 80–97.

[29]

Chris Peikert. 2016. A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science, 10, 4, 2016. Pages 283–424. issn:1551-305X https://doi.org/10.1561/0400000074

Digital Library

[30]

Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz. 2017. Pseudorandomness of ring-LWE for any ring and modulus. In STOC. Pages 461–473. isbn:9781450345286 https://doi.org/10.1145/3055399.3055489

Digital Library

[31]

Prasad Raghavendra and Morris Yau. 2020. List decodable learning via sum of squares. In SODA. Pages 161–180.

[32]

Oded Regev. 2004. New lattice-based cryptographic constructions. J. ACM, 51, 6, 2004. Pages 899–942. issn:0004-5411 https://doi.org/10.1145/1039488.1039490

Digital Library

[33]

Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In STOC. Pages 84–93. isbn:1-58113-960-8 https://doi.org/10.1145/1060590.1060603

Digital Library

[34]

Oded Regev and Aravindan Vijayaraghavan. 2017. On learning mixtures of well-separated Gaussians. In FOCS. Pages 85–96. https://doi.org/10.1109/FOCS.2017.17

[35]

Ronitt Rubinfeld and Rocco A. Servedio. 2009. Testing monotone high-dimensional distributions. Random Structures & Algorithms, 34, 1, 2009. Pages 24–44. https://doi.org/10.1002/rsa.20247

[36]

Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. 2014. Intriguing properties of neural networks. In ICLR. arxiv:1312.6199

[37]

Santosh Vempala and Grant Wang. 2002. A spectral algorithm for learning mixtures of distributions. In FOCS. Pages 113.

[38]

Roman Vershynin. 2018. High-dimensional probability: an introduction with applications in data science. Cambridge University Press. isbn:9781108415194 lccn:2018016910 https://doi.org/10.1017/9781108231596

Cited By

Dudeja RHsu D(2024)Statistical-computational trade-offs in tensor PCA and related problems via communication complexityThe Annals of Statistics10.1214/23-AOS233152:1Online publication date: 1-Feb-2024
https://doi.org/10.1214/23-AOS2331
Kundu SNorga QKarmakar AGangopadhyay SBermudo Mera JVerbauwhede I(2024)Scabbard: An Exploratory Study on Hardware Aware Design Choices of Learning with Rounding-based Key Encapsulation MechanismsACM Transactions on Embedded Computing Systems10.1145/369620824:1(1-40)Online publication date: 20-Sep-2024
https://dl.acm.org/doi/10.1145/3696208
Bakshi AKothari PRajendran GTulsiani MVijayaraghavan A(2024)Efficient Certificates of Anti-Concentration Beyond Gaussians2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00065(970-987)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00065
Show More Cited By

Index Terms

Continuous LWE
1. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness

Recommendations

On lattices, learning with errors, random linear codes, and cryptography
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the 'learning from parity with error' problem to higher moduli. It can also be viewed as ...
Attribute-Based Encryption for Circuits

In an attribute-based encryption (ABE) scheme, a ciphertext is associated with an ℓ-bit public index ind and a message m, and a secret key is associated with a Boolean predicate P. The secret key allows decrypting the ciphertext and learning m if and ...
KDM and Selective Opening Secure IBE Based on the LWE Problem
APKC '17: Proceedings of the 4th ACM International Workshop on ASIA Public-Key Cryptography

Based on the learning with errors (LWE) problem, we construct an identity-based encryption (IBE) scheme in the standard-model which is secure against the key dependent message (KDM) attacks and the selective opening (SO) attacks. KDM security, which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

June 2021

1797 pages

ISBN:9781450380539

DOI:10.1145/3406325

General Chair:
Samir Khuller
Northwestern University, USA
,
Program Chair:
Virginia Vassilevska Williams
Massachusetts Institute of Technology, USA

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '21

Sponsor:

SIGACT

STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing

June 21 - 25, 2021

Virtual, Italy

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
767
Total Downloads

Downloads (Last 12 months)316
Downloads (Last 6 weeks)49

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dudeja RHsu D(2024)Statistical-computational trade-offs in tensor PCA and related problems via communication complexityThe Annals of Statistics10.1214/23-AOS233152:1Online publication date: 1-Feb-2024
https://doi.org/10.1214/23-AOS2331
Kundu SNorga QKarmakar AGangopadhyay SBermudo Mera JVerbauwhede I(2024)Scabbard: An Exploratory Study on Hardware Aware Design Choices of Learning with Rounding-based Key Encapsulation MechanismsACM Transactions on Embedded Computing Systems10.1145/369620824:1(1-40)Online publication date: 20-Sep-2024
https://dl.acm.org/doi/10.1145/3696208
Bakshi AKothari PRajendran GTulsiani MVijayaraghavan A(2024)Efficient Certificates of Anti-Concentration Beyond Gaussians2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00065(970-987)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00065
Diakonikolas IKarmalkar SPang SPotechin A(2024)Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00063(949-958)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00063
Gupte AVafa NVaikuntanathan V(2024)Sparse Linear Regression and Lattice ProblemsTheory of Cryptography10.1007/978-3-031-78017-2_10(276-307)Online publication date: 28-Nov-2024
https://doi.org/10.1007/978-3-031-78017-2_10
Nitaj ARachidi T(2023)Applications of Neural Network-Based AI in CryptographyCryptography10.3390/cryptography70300397:3(39)Online publication date: 11-Aug-2023
https://doi.org/10.3390/cryptography7030039
Bresler GGuo CPolyanskiy Y(2023)Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00132(2149-2158)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00132
Dachman-Soled DGong HHanson TKippen H(2023)Revisiting Security Estimation for LWE with Hints from a Geometric PerspectiveAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38554-4_24(748-781)Online publication date: 9-Aug-2023
https://doi.org/10.1007/978-3-031-38554-4_24
Chen SGollakota AKlivans AMeka RKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Hardness of noise-free learning for two-hidden-layer neural networksProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601048(10709-10724)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601048
Diakonikolas IKane DManurangsi PRen LKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Cryptographic hardness of learning halfspaces with massart noiseProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3600532(3624-3636)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3600532
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents