LWE与神经网络

Question

看起来，LWE问题：As + e = b的构造类似于神经网络的工作方式：Ax + b = y。

在LWE中，给出了问题实例A和带有b误差的乘积，并要求它们生成秘密向量s。它是否类似于ML中给出的系数矩阵A和期望标号y的问题，我们能产生一个有效的样本x吗？

另外，我想知道我们在ML中使用的技术，如反向传播，是否也可以应用于LWE？

Answer 1

这似乎不太可能。最近的一篇论文提出了一个连续有限公司问题。这个问题在结构上非常类似于标准的LWE问题--它有(量子)最坏的情况，从平均情况到硬格问题。

在这篇论文中，他们还证明了ML (学习混合高斯)中的一个标准问题可以归结为连续的LWE问题。这给您提供了一个更具体的ML攻击问题。如果你能学习高斯的混合物，你可以把它简化为求解连续的LWE，然后你可以把它简化为求解最坏的格点问题。如果你能解决最坏的格问题，那么我们就不再相信LWE是困难的了。

也有一些结果表明，广泛的学习算法(符合“统计查询模型”的算法)不能解决某些学习问题。LPN问题(你可以模糊地认为它是"LWE with q = 2“)有这样的界限(例如见这个问题)，但我不知道特定的ML技术(如反向传播)是否适合于SQ模型。

Answer 2

嗯，他们可以应用，但很可能不太可能成功，否则你会有突破，所以如果你有一个具体的想法，你可以实施它。

究其原因，是由于这种离散问题(格场或有限场)的平均难度很大，通常存在许多与著名问题相关的硬度结果。

ML问题在本质上是非对抗性的，所以苹果和橘子，真的。