格与LWE是如何连接的？

Question

我是一名最后一年的纯数学硕士学生，我正在写我的论文。我正在研究基于格的加密和环形LWE之间的连接，以及环形LWE和同态加密之间的连接。对于第二部分，我设法找到一份适当的文件，为我提供一些信息。然而，随着基于格的加密和LWE的连接，事情似乎变得更加混乱。除了我们在我的一个过程(搜索- LWE和决策- LWE )中看到的LWE的假设之外，我还找到了Regev的定义，它给出了LWE是一个逼近序列，问题是找到解决这些近似的合适向量，并且这个问题可以在R-LWE中推广到多项式中。我还找到了LWE定义的矩阵形式。假设我能理解这三个部分是如何连接的，我仍然不知道如何把它们和格连接起来，所以我继续搜索。在许多文献中，我发现基于格子的问题-最短向量问题(SVP)和最近向量问题(CVP)的硬度与LWE联系在一起，但仅此而已。所以我想知道是否有人熟悉任何一本书/论文来解释基于格的密码学是如何与LWE相联系的，并且解释了R的结构，或者至少引导我走向一条不那么混乱的路径？

提前谢谢你。

Answer 1

我强烈推荐这次调查作为所有基于格的事物的总结。

为了回答你的问题，LWE和它的变体对某些晶格问题(例如GapSVP)的硬度降低。也就是说，打破像LWE这样的加密方案，至少和解决相应的格问题一样困难(对于某些格)。

像LWE这样的格式的安全性取决于格问题的硬度。