減少 NTRU 中的消息擴展
在1998 年的原始 NTRU 提案中，它在第 16 頁上說：
不過，值得一提的是，有一個簡單的。可用於顯著減少消息擴展的屏蔽技術。通過這種方法，Alice 發送了一對多項式 $ (e_1, e_2) $ . 第一個多項式是加密 $ e_1 =r_1 \cdot h+r_2 \mod q $ ， 在哪裡 $ r_2 $ 是一個隨機選擇的多項式，所有係數都等於 -1、0 和 1。第二個多項式是 $ e_2 =r_2 \cdot h+ m’ \mod q $ ， 在哪裡 $ m’ $ 是在合適的數字信封模中的明文消息 $ q $ .
因為 Bob 可以解密 $ e_1 $ 恢復 $ r_2 $ , 他能夠恢復 $ m’ \mod q $ . 換句話說，以加密消息的長度加倍為代價 $ 2 n \log_2 q $ 比特，愛麗絲能夠向鮑勃發送一個 $ n \log_2 q $ 位的資訊。原則上，這將消息擴展減少到 2 對 1，儘管使用數字信封自然會增加消息擴展。
在目前的 NTRU 實例化中這仍然可能嗎？
我在擁有 NTRU 算法的 Security Innovation 工作。很高興看到這種興趣！
您可以將此方法視為兩種單獨的加密：一種用於傳輸的公鑰加密 $ r_2 $ , 和一種對稱加密使用 $ r_2 $ 作為加密的鑰匙 $ m $ . 這使它看起來更像非對稱加密中的標準做法，您通常使用公鑰加密算法來同意密鑰，然後使用對稱算法來加密數據。
所以問題是，正在使用 $ r_2*h + m $ 一個好的對稱加密方案？答案是否定的，它不是真的。例如：
- 它對選擇的明文攻擊並不安全。考慮一個知道消息 00000… 和 11111… 之一已被加密的攻擊者。她將密文乘以 $ h^{-1} $ . 如果結果的形式為 $ r $ ，她知道消息是 00000 …… 如果沒有，她就知道消息是 11111……
- 它沒有經過身份驗證。知道我正在發送消息“支付 200 美元”的攻擊者可以輕鬆地將其更改為“支付999 美元” 。
- 目前尚不清楚如何最好地加密多塊消息。當然，您可以提出諸如 CBC 之類的臨時結構，但這需要定義。
您可以解決所有這些問題，但代價是額外的處理時間。可能，儘管原始加密機制非常快，但如果您安全地執行它，它不會比使用標準對稱算法更快。因此，我們建議僅使用 NTRUEncrypt 進行密鑰傳輸或加密小消息，如果您有更多數據要加密，請使用強大的對稱算法進行加密。