NewHope 中的 LWE 樣本數量

這是關於數字後量子密鑰交換協議 New-Hope ( https://eprint.iacr.org/2015/1092.pdf )。在論文中，我們可以看到協議生成的樣本數量為 $ 2n $ 在哪裡 $ n $ 是 $ 1024 $ , 矩陣的秩 $ a $ . 一旦在伺服器端 $ b\leftarrow as+e $ 並且一旦在客戶端 $ u\leftarrow as’+e’ $ . 但是論文中的作者（第 18 頁附錄 B）說，協議的每個實例化中的樣本數是 $ 5n $ .

我不明白為什麼。此外，據我所知，LWE 樣本在矩陣中是相關的 $ a $ 和秘密 $ s $ 保持不變。但是，在協議中，秘密發生了變化 $ s $ 和 $ s’ $ .

有人可以解釋一下嗎？先感謝您。

他們實際上是在採樣 $ 5n $ 元素來自 $ \Psi_{16} $ . 也許第 5 頁的協議 2 最清楚地表明了這一點，其中 $ \textbf{s}, \textbf{e} \stackrel{$}{\leftarrow} \Psi_{16}^n $ 和 $ \textbf{s}’, \textbf{e}’, \textbf{e}’’ \stackrel{$}{\leftarrow} \Psi_{16}^n $ 被採樣（在 Alice 一側的第 3 行，在 Bob 一側的第 1 行）。

這可能也回答了您後續問題的一部分，但為了完整性：值 $ \textbf{s} $ 和 $ \textbf{s}’ $ 由 Alice 和 Bob 獨立採樣，因此完全不相關。最後的共享秘密既不是 $ \textbf{s} $ 也不 $ \textbf{s}’ $ , 但和解了 $ v $ .

引用自：https://crypto.stackexchange.com/questions/45159