糾錯碼 VS 基於格的加密
我不是 PQ 加密方面的專家，但據我了解糾錯碼和基於格的加密，加密假設非常相似。對我來說，主要區別在於噪音的性質。在一種情況下，雜訊受到“物理雜訊”的啟發，在另一種情況下，它更數學化並考慮更複雜的距離（歐幾里得距離而不是漢明距離）。
直覺地說，這個原因是有道理的，因為我所知道的涉及基於格的加密的每個應用程序都比基於糾錯加密的應用程序更有效。
- 我的直覺在你看來是正確的嗎？
- 如果是，是否有一個定理證明基於糾錯碼假設的每個加密協議都可以轉換為更有效的基於格的協議（即，具有相同的安全級別並基於較弱的格假設） ?
- 如果不是，是否存在考慮該問題的現有研究的更非正式聲明？或者只是比較這兩個假設系列沒有意義？
關於你的第一段，我不會說關鍵的區別是雜訊的類型，因為基於格的密碼學（LBC）使用了很多不同的雜訊：高斯、二進制、三元等（另見這個 SE 執行緒：Uniform與帶有錯誤的環學習中的離散高斯採樣）。但是，在 LBC 中非常有用的一點是您可以使用模數 $ q $ 戒指的 $ \mathbb{Z}_q $ 你正在努力。LBC 中的許多問題可以通過簡單地增加來解決 $ q $ ，這當然會影響基礎假設的硬度，但在許多情況下，這種影響是可控的。
另一方面，在基於程式碼的密碼學 (CBC) 中，大多數情況下模數固定為 2（例如 BIKE）。發生這種情況時，模數是 CBC 可以利用的少一種工具。與模數一起，度量當然會產生影響。例如，假設您添加 $ n $ 矢量圖 $ x_i $ 維度的 $ n $ 具有相同的歐幾里得範數（分別是漢明權重）：
- 使用歐幾里得範數，你有 $ |\sum_i x_i | \leq \sum_i |x_i| $ . 所以如果你設置模數 $ q $ 要足夠大，您仍然可以爭辯說總和很短，這對安全性和正確性都有用。
- 同樣，對於漢明權重 w，您有 $ w(\sum_i x_i) \leq \sum_i w(x_i) $ . 所以如果你添加 $ n $ 漢明權重向量 $ 1 $ 每個，你不能對總和的漢明權重說任何有意義的東西。
關於問題 1、2、3，目前最先進的 LBC 方案確實比 CBC 方案更有效。但不能保證這將永遠是正確的，因為 CBC 已經存在了 40 多年，所以密碼分析者有足夠的時間來尋找優化的攻擊。LBC 是最近的（20 年左右）。請注意，當正確參數化時，兩個族似乎都在其參數中提供指數硬度：
- 對於 CBC： $ O(2^{0.0885 \cdot n}) $ 其中 n 是系統參數，請參見本文。
- 對於 LBC： $ \tilde{O}(2^{0.295 \cdot B}) $ 其中 B 計算起來很麻煩，但似乎與系統參數或多或少呈線性增長，請參閱本文。
就像您提到的，兩個系列的假設是相似的（例如，基於 QC-MDPC 的方案使用看起來與 NTRU 和 Ring-LWE 極其相似的假設，請參見本展示文稿的幻燈片 4），並且大多數簡單的 LBC 方案具有 CBC 等價物，並且互為. 在某種程度上，人們甚至可以在更深層次上進行類比 ，我覺得這在概念上是令人滿意的。