Lattice-Crypto
MLWE（和 RLWE）到 LWE 減少證明
在加密論文中，MLWE/RLWE/等的密碼分析。經常被簡化為 LWE。為什麼我們可以這樣做？是否有嚴格的證據證明這種減少？
沒有已知的從 LWE 到 MLWE（或到 RLWE）的減少。也就是說，可能 MLWE 和 RLWE 都被破壞了，但 LWE 是安全的。
然而，這似乎極不可能。為了支持 LWE 的安全性，我們進行了簡化，表明打破 LWE 的平均情況硬度需要打破一些晶格問題的最壞情況硬度——這將是（用 Brakerski 等人的語言）“驚天動地” . 現在，MLWE 和RLWE都存在類似的減少（另請參見此）：兩者都可以基於晶格問題的最壞情況硬度。主要區別在於 RLWE 要求理想晶格上的最壞情況硬度，而 MWLE 要求模組晶格上的最壞情況硬度。
關於上述內容的一些注意事項：
- 一切都在很大程度上取決於參數。LWE 風格的假設是高度參數化的，如果我們不明確說明減少工作的參數，那麼說“減少”並不能說明什麼。我上面提到的減少是針對最標準的參數選擇（例如多項式模數）。
- 由於各種原因，模組晶格上的最壞情況硬度聽起來比理想晶格上的最壞情況硬度更合理。然而，在減少的一些重要損失之前，我們實際上確實將 RLWE 減少到 MLWE。這進一步說明了在討論該主題時，精確的參數選擇很重要。
- 密碼學家更喜歡使用 MLWE 或 RLWE 而不是 LWE 的主要原因是因為它們導致了更有效的方案。然而，RLWE 由一些多項式參數化，並且需要針對這個非常具體的多項式進行硬度假設。這有點令人不滿意，因為我們並不真正了解多項式的選擇對安全性的影響。然而，最近引入了一個新問題，中間產品 LWE。後者為我們提供了兩全其美的優勢：它在許多應用程序中允許與標準 RLWE 或 MLWE 基本相同的效率提升（參見論文，以及它的後續內容），但在任何應用程序方面它都與 RLWE 一樣安全多項式 - 因此要打破它，您需要打破 RLWE 以獲取多項式的每一個可能選擇。這為這個假設的安全性提供了一個非常令人滿意的基礎。