Lattice-Crypto
格子和 LWE 是如何連接的？
我是去年的純數學碩士生，我正在寫我的論文。我正在研究基於格的加密和環 LWE 之間以及環 LWE 和同態加密之間的連接。對於第二部分，我設法找到了一篇合適的論文來為我提供一些資訊。然而，隨著基於格的加密和 LWE 的連接，事情似乎變得更加混亂。除了我們在我的課程中看到的 LWE 假設（搜尋 LWE 和決策 LWE）之外，我能夠找到 Regev 的定義，它表示 LWE 是一系列近似值，問題是找到合適的向量來解決這些近似值，並且這個問題可以在 R-LWE 中擴展到多項式。我還能夠找到 LWE 定義的矩陣形式。所以讓’ s說我能理解這三個部分是怎麼連接的，我還是沒看出來怎麼用格子連接，所以一直在找。在許多論文中，我發現基於格的問題，最短向量問題 (SVP) 和最近向量問題 (CVP) 的難度與 LWE 相關，僅此而已。所以我想知道是否有人熟悉任何解釋基於格的密碼學如何與 LWE 聯繫並解釋 R-LWE 的結構或至少引導我走向不那麼混亂的道路的書/論文？
先感謝您。
我強烈推薦這個調查作為對所有基於格的事物的總結。
為了回答您的問題，LWE 及其變體對某些晶格問題（例如 GapSVP）具有硬度降低。也就是說，破解像 LWE 這樣的加密方案至少和解決相應的格問題（對於某些格）一樣難。
LWE 等方案的安全性取決於晶格問題的難度。