Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
复制标题
连续 LWE 与 LWE 一样困难
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
V. Vaikuntanathan
中科院分区：
文献类型：
--
作者：
A. Gupte;Neekon Vafa;V. Vaikuntanathan
我们显示出与错误（LWE）问题的经典学习之间的直接和概念上简单的减少，其连续的模拟（Bruna，Regev，Song and Tang，STOC 2021）。这使我们能够将基于LWE的密码学的强大机械带到Clwe的应用中。例如，我们在GAP最短矢量问题的经典最坏情况下获得了Clwe的硬度。以前，这仅在晶格问题的量子最坏情况下才知道。更广泛地说，随着我们在两个问题之间的减少，LWE的未来发展也将适用于CLWE及其下游应用程序。作为一种具体的应用，我们显示了高斯混合物密度估计的硬度结果改善。在这个计算问题中，给定样品访问高斯人的混合物，目标是输出估计混合物密度函数的函数。在经典LWE问题的（合理且众所周知）的指数硬度下，我们表明高斯混合物密度估计$ MATHBB {r}^{n} $，大约$ log n $ n $ gaussian组件给定poly $（n）$ samples需要时间n中的准多项式。在LWE的（保守）多项式硬度下，我们显示出任何常数$ epsilon> 0 $的$ n^{epsilon} $ gaussians的密度估计，它在Bruna，Regev，Song and Tang（STOC 2021）上都改进在多项式（量子）硬度假设下，至少$ sqrt {n} $ gaussian表示硬度。我们的关键技术工具是从古典LWE到LWE的减少，并使用K-Sparse Secrets将噪声的乘法增加仅为$ O（sqrt {k}）$，而与环境尺寸n无关。
We show direct and conceptually simple reductions between the classical learning with errors (LWE) problem and its continuous analog, CLWE (Bruna, Regev, Song and Tang, STOC 2021). This allows us to bring to bear the powerful machinery of LWE-based cryptography to the applications of CLWE. For example, we obtain the hardness of CLWE under the classical worst-case hardness of the gap shortest vector problem. Previously, this was known only under quantum worst-case hardness of lattice problems. More broadly, with our reductions between the two problems, any future developments to LWE will also apply to CLWE and its downstream applications. As a concrete application, we show an improved hardness result for density estimation for mixtures of Gaussians. In this computational problem, given sample access to a mixture of Gaussians, the goal is to output a function that estimates the density function of the mixture. Under the (plausible and widely believed) exponential hardness of the classical LWE problem, we show that Gaussian mixture density estimation in $mathbb{R}^{n}$ with roughly $log n$ Gaussian components given poly $(n)$ samples requires time quasi-polynomial in n. Under the (conservative) polynomial hardness of LWE, we show hardness of density estimation for $n^{epsilon}$ Gaussians for any constant $epsilon>0$, which improves on Bruna, Regev, Song and Tang (STOC 2021), who show hardness for at least $sqrt{n}$ Gaussians under polynomial (quantum) hardness assumptions. Our key technical tool is a reduction from classical LWE to LWE with k-sparse secrets where the multiplicative increase in the noise is only $O(sqrt{k})$, independent of the ambient dimension n.
登录
查看更多内容
DOI：
10.1145/3188745.3188758
发表时间：
2017-11
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
通讯作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
使用 Massart 噪声学习半空间的密码学硬度
DOI：
--
发表时间：
2022
期刊：
Advances in Neural Information Processing Systems (NeurIPS
影响因子：
--
作者：
Diakonikolas, I;Kane, D;Manurangsi, P;Ren, L.
通讯作者：
Ren, L.
关于学习分离良好的高斯的混合
DOI：
10.1109/focs.2017.17
发表时间：
2017
期刊：
Proceedings of 58th Annual IEEE Symposium on the Foundations of Computer Science
影响因子：
--
作者：
Regev, Oded;Vijayaraghavan, Aravindan
通讯作者：
Vijayaraghavan, Aravindan
连续LWE
DOI：
10.1145/3406325.3451000
发表时间：
2021
期刊：
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Bruna, Joan;Regev, Oded;Song, Min Jae;Tang, Yi
通讯作者：
Tang, Yi