Continuous LWE

Joan Bruna; Oded Regev; Min Jae Song; Yi Tang

doi:10.1145/3406325.3451000

Continuous LWE

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

Original language	English (US)
Title of host publication	STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
Editors	Samir Khuller, Virginia Vassilevska Williams
Publisher	Association for Computing Machinery
Pages	694-707
Number of pages	14
ISBN (Electronic)	9781450380539
DOIs	https://doi.org/10.1145/3406325.3451000
State	Published - Jun 15 2021
Event	53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy Duration: Jun 21 2021 → Jun 25 2021

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Country/Territory	Italy
City	Virtual, Online
Period	6/21/21 → 6/25/21

Keywords

Learning with Errors
computational learning theory
cryptography
lattices
mixture of Gaussians
quantum computing

ASJC Scopus subject areas

Software

Access to Document

10.1145/3406325.3451000

Cite this

Continuous LWE. / Bruna, Joan; Regev, Oded; Song, Min Jae et al.
STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. ed. / Samir Khuller; Virginia Vassilevska Williams. Association for Computing Machinery, 2021. p. 694-707 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bruna, J, Regev, O, Song, MJ & Tang, Y 2021, Continuous LWE. in S Khuller & VV Williams (eds), STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 694-707, 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, Virtual, Online, Italy, 6/21/21. https://doi.org/10.1145/3406325.3451000

@inproceedings{1af426bed2a24ba585e72189acbfead9,

title = "Continuous LWE",

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

keywords = "Learning with Errors, computational learning theory, cryptography, lattices, mixture of Gaussians, quantum computing",

author = "Joan Bruna and Oded Regev and Song, {Min Jae} and Yi Tang",

note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 ; Conference date: 21-06-2021 Through 25-06-2021",

year = "2021",

month = jun,

day = "15",

doi = "10.1145/3406325.3451000",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "694--707",

editor = "Samir Khuller and Williams, {Virginia Vassilevska}",

booktitle = "STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing",

}

TY - GEN

T1 - Continuous LWE

AU - Bruna, Joan

AU - Regev, Oded

AU - Song, Min Jae

AU - Tang, Yi

PY - 2021/6/15

Y1 - 2021/6/15

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

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

KW - Learning with Errors

KW - computational learning theory

KW - cryptography

KW - lattices

KW - mixture of Gaussians

KW - quantum computing

UR - http://www.scopus.com/inward/record.url?scp=85108157293&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108157293&partnerID=8YFLogxK

U2 - 10.1145/3406325.3451000

DO - 10.1145/3406325.3451000

M3 - Conference contribution

AN - SCOPUS:85108157293

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 694

EP - 707

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

A2 - Khuller, Samir

A2 - Williams, Virginia Vassilevska

PB - Association for Computing Machinery

T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021

Y2 - 21 June 2021 through 25 June 2021

ER -

Continuous LWE

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this