Ring-LWE 現在（2021）壞了嗎？
Hao Chen 最近（2021 年 3 月 29 日）的文章“Ring-LWE over two-to-power cyclotomics is not hard”可在此處獲得預印本：https ://eprint.iacr.org/2021/418
我不是密碼學家。這篇文章是否意味著 Ring-LWE 不適合後量子非對稱密碼學？這是否意味著其他算法可能會受到類似的影響？還是作者有什麼不對？
更新：20210403
TL;博士
- 如果正確，該論文將影響廣泛的 RLWE 系統的安全性，包括所有最常用的變體。
- 然而，該論文違反了Peikert已審查和確立的論文的“不可行”定理。
撇開論文是否正確的問題不談，有一些RLWE實例不是在兩個分圓環的功率下發生的（儘管它是迄今為止最受歡迎的選擇）。對於 NIST 流程，值得注意的是CRYSTALS 送出（KYBER 和 DILITHIUM）、FALCON和SABRE都使用了兩個分圓環的功率。然而， NTRU使用 $ x^{509}-1 $ , $ x^{677}-1 $ 和 $ x^{821}-1 $ , NTRUPrime甚至不使用分圓環。
因此，即使滿足要求，它們也不會破壞所有環格系統，甚至也不會破壞所有 NIST 環格候選者。
（從技術上講，NTRU 和 LWE 問題是不同的，儘管兩者在實踐中都是通過解決 SVP/CVP 實例來解決的，所以我將粗暴地忽略 RLWE 和環格實例之間的區別）。
該論文聲稱打破了決定性的 RLWE（區分 $ (\mathbf a, \mathbf {as}+\mathbf e) $ 從 $ (\mathbf a, \mathbf b) $ 而不是恢復 $ \mathbf s $ 和 $ \mathbf e $ ) 在 2 個分圓環的冪。然後它聲稱對一個簡短的子基礎問題進行了量子攻擊。在LPR 論文的第 5 節中，決策 RLWE 方法將轉換為在分圓環上的搜尋 RLWE 方法（感謝Mark和Chris Peikert指出了這種減少）。Hao Chen 的論文第 3.4 節沒有提出這一觀察。
在區分攻擊方面，這個想法的核心似乎是我們可以找到一個子晶格 $ \mathbf L_2 $ 其中既包含一個理想晶格 $ \mathbf Q $ 這足夠密集，以至於很多隨機元素最終會出現在那里和另一個子晶格 $ \mathbf L_1 $ 其中錯誤向量出現的機會較高（例如，錯誤向量出現在 $ \mathbf L_1 $ 是隨機向量出現在 $ \mathbf L_2 $ ）。那麼，如果給定一個大集合 $ (\mathbf a,\mathbf b) $ 我們必須從中猜出其中的對 $ \mathbf b $ 產生於 $ \mathbf b=\mathbf{as}+\mathbf e $ 我們專注於子集 $ \mathbf a\in \mathbf Q $ . 如果通過 RLWE 生成，則 $ \mathbf{as}\in \mathbf Q\subset \mathbf L_2 $ 由理想的財產和 $ \mathbf e\in \mathbf L_1\subset \mathbf L_2 $ 機率較高，因此 $ \mathbf{as}+\mathbf e\in \mathbf L_2 $ 機率較高。如果我們因此選擇 $ (\mathbf a,\mathbf b) $ 對在哪裡 $ \mathbf a\in Q $ 和 $ \mathbf b\in L_2 $ 並將這些聲明為 RLWE 實例，我們更有可能是正確的。Cyclotomic 晶格確實可以提供多種選擇 $ \mathbf Q $ .
然而，格子如 $ L_2 $ 對於最壞情況的錯誤分佈不存在。TL;DR 中連結的 Peikert 論文的第 5 節表明，如果 $ \mathbf Q $ 密度足以容納許多 $ \mathbf a $ ，那麼最壞情況下的誤差分佈是平滑的（即沒有升高的機率） $ \mathbf Q $ 因此 $ \mathbf L_2 $ . 可證明的硬環 LWE 實例通常會減少最壞情況下的錯誤分佈。
“不行”的觀察是由於 Chris Peikert 造成的，並且主要取自他的推特提要，如上段所述。任何錯誤和失實陳述都是我造成的。