NTRU 後門和 NewHope TLS 協議
昨天發布了預印本《NewHope的非結構化反轉》，並使用針對 NTRU 的後門方法聲稱 Grover 的算法和反轉預言可以應用於NewHope。
我的問題是，Unstructured Inversions 文章中的後門是否真的可以用來對付 NTRU？我對它可能對 NewHope 產生或不產生的影響不感興趣，只是 NTRU 的形式。
我叫張振飛。我在 Security Innovation Inc. 工作，該公司於 2010 年收購了 NTRU Inc.。
基於 R-LWE 的密鑰交換
$$ 1 $$使用公共矩陣 $ a $ 這可能會被操縱。例如，如果 $ a $ 是 NTRU 風格的公鑰，即 $ a = g/f $ 在哪裡 $ g $ 和 $ f $ 很短，那麼可以通過恢復來破壞系統 $ f $ . 特別是，引用的論文建議人們可以使用 Grover 來加速搜尋 $ f $ . 這是一段時間以來社區的一個已知問題。新希望論文
$$ 2 $$解決這個問題 $ a $ 在客戶端執行時作為散列函式的輸出。所以在合理的假設下，沒有人能夠操縱公共矩陣 $ a $ . 這會影響NTRU嗎？如果正確使用 NTRU，答案是否定的。
NTRU 使用結構化公鑰 $ a $ 以實現高效計算。因此，它設計了一個活板門。因此，如果 NTRU 用於 Diffie-Hellman 類型的密鑰交換，其中 $ a $ 是由（受信任的）第三方生成的，那麼是的，它可能容易受到這種威脅。
但是，在密鑰交換協議中正確使用 NTRU 是通過密鑰封裝機制 (KEM) 對其進行實例化，例如
$$ 3 $$ $$ 4 $$. 在這些情況下，客戶端生成公鑰（作為公共參數 $ a $ 在基於 R-LWE 的方案中）。只有客戶知道活板門。在這種情況下，攻擊者需要執行 Grover 算法來找到陷門。這和使用 Grover 算法破解 NTRU 一樣難。建議的參數集$$ 5 $$確保這種攻擊是不可能的。
謝謝您的答复。你指的是來自的混合攻擊
$$ 5 $$在第 8 節中的參數的上下文中$$ 5 $$?
是的。
我還看到您確實專門解決了與 f(1)≠0mod2 相關的問題，再次感謝您。
它不僅僅是 $f(1) \neq 0 mod 2" 部分。在
$$ 5 $$該算法是CCA-2安全加密算法，排除了反轉預言機$$ 6 $$“非結構化反演”論文要求。
看起來 Unstructured Inversion 預印本更多地關注近似 x 座標，而不是修改公共矩陣 a。
“非結構化反演”論文不夠詳細，所以以下是我的猜測，可能不正確。總的來說，恕我直言，這篇論文依賴於幾個非常強大的假設。
- (R-)LWE 公鑰中存在陷門 $ a $ ，攻擊者不知道。
這是一種罕見的情況，因為攻擊者插入了活板門（如針對
$$ 1 $$)，在這種情況下，他已經知道活板門，因此不需要執行此攻擊；或者 $ a $ 由客戶端如實生成（如$$ 2 $$)，因此不存在活板門。這是一個奇怪的情況，有人（但不是攻擊者）生成 $ a $ 帶有陷門，但攻擊者不知道。如果客戶端正確地遵循協議，這將永遠不會發生。 2. 反轉預言機的存在。
反轉預言是比 CCA 定義中使用的解密預言更強大的預言。此外，在 newhope 風格和 NTRU-KEM 風格的密鑰交換中，公共參數/密鑰只使用一次。對於臨時密鑰，這種預言機不太可能存在。換句話說，如果存在這樣一種適用於臨時密鑰的預言機，那麼攻擊可能會比論文中描述的要強得多。
$$ 1 $$ https://eprint.iacr.org/2014/599 $$ 2 $$ https://eprint.iacr.org/2015/1092 $$ 3 $$ https://eprint.iacr.org/2015/287 $$ 4 $$ https://datatracker.ietf.org/doc/html/draft-whyte-qsh-tls12-02 $$ 5 $$ https://eprint.iacr.org/2015/708 $$ 6 $$ http://cseweb.ucsd.edu/~pmol/Publications/Recovering%20NTRU%20Secret%20Key%20From%20Inversion%20Oracles.pdf