如何確定格密碼系統的具體安全性？
我目前正在閱讀有關格密碼學的內容，並對基於 LWE 問題的密碼系統感興趣。我理解從晶格問題到 dLWE 的減少。然後我們將我們對密碼系統（比如 Regev 或雙 Regev PKC）的信念建立在 dLWE 上。但這是漸近的。據我了解，這種方法的工作方式是我們相信打破 SIVP 或任何格子問題需要時間非常大的 n 函式，並且從減少中我們得到一個 SIVP 求解器，因此任何打破密碼系統的算法也必然是一個非常n 的大函式。
然而，我不明白的是如何為這些密碼系統提供參數（例如，如果我想要 128 位的安全性，LWE 實例應該有多大）？我已經閱讀了幾篇關於這個主題的論文，但並沒有真正理解它。我的理解是我們像解決 BDD 的實例一樣解決 LWE。但是這些論文討論了基礎縮減和解決 SVP 的方法，我不知道如何將這些東西聯繫在一起。
對不起，我的英語真的很差。
根據您的基於格的密碼系統是否具有安全性降低，存在兩種類型的參數：
$ \textbf{1. Provably secure:} $ 對於具有可證明安全性的密碼系統，參數是根據底層約簡選擇的。例如，假設您的密碼系統基於 LWE 問題的難度。現在，假設所需的安全級別 $ \ell $ 與 LWE 問題的難度級別相同（即，不涉及由安全性降低引起的差距），可以確定最知名的求解器 $ D $ 對於 LWE 問題，並確保其相應的參數提供的硬度為 $ \ell $ 位。為了找到最知名的 LWE 求解器並測量 LWE 實例的位硬度，Albrecht 等人的估計器。$$ APS15 $$可以使用。
$ \textbf{2. Non-provably secure:} $ 如果密碼系統不能被證明是安全的，那麼確定最知名的攻擊 $ A $ 在密碼系統上並選擇滿足的參數 $ \frac{t_A}{\varepsilon_A} \geq 2^{\ell} $ ， 在哪裡 $ t_A $ 和 $ \varepsilon_A $ 是執行時間和成功機率 $ A $ ， 分別。
有關詳細資訊，請參閱本文。
雖然從硬晶格問題到 LWE 的簡化為它的定性硬度提供了證據，但它並沒有說太多關於它的定量硬度，因為它不是很緊。因此，對於密碼分析，通常推測 LWE 是困難的，為了估計其具體的硬度，我們研究了解決 LWE 的所有可能算法（除其他外，如您所提到的，存在解決 BDD 的格算法）。為了更好地了解這些算法和 LWE 的具體難度，我建議閱讀這篇文章。
希望有幫助。