基於錯誤學習問題的簡單可證明安全密鑰交換方案
在這篇論文（Ding 等人的一個簡單的可證明安全的密鑰交換）中，在第 8 頁，作者給出了該技術的正確性如下
那麼 SK A = SK B具有壓倒性的機率，即如果 Alice 和 Bob 誠實地執行協議，那麼他們將共享相同的密鑰。
上式使用引理 1，如下
作者如何使用引理 1 推導出上述方程。這個方程給出了該技術的正確性。任何人都可以請幫忙。
第一：引理 1 說 $ ||\mathbf{x}|| \leq \alpha q \sqrt{n} $ 以壓倒性的機率如果 $ \mathbf{x} $ 是從離散高斯中得出的，因為 $ \frac{1}{2^n} $ 可以忽略不計。
接下來，從絕對值的性質， $ |a + b| \leq |a| + |b| $ . 所以，離開 $ 2 $ 現在出去寫作 $ \mathbf{s_A}^T\mathbf{e_B} $ 作為 $ \mathbf{s_A}\cdot\mathbf{e_B} $ :
$ |\mathbf{s_A}\cdot\mathbf{e_B} + e’_A + \mathbf{s_B}\cdot\mathbf{e_A} + e’_B| \leq |\mathbf{s_A}\cdot\mathbf{e_B}| + |e’_A| + |\mathbf{s_B}\cdot\mathbf{e_A}| + |e’_B| $ .
現在，對於歐幾里得規範，Cauchy-Schwarz說 $ |\mathbf{a\cdot b}| \leq |\mathbf{a}|\cdot |\mathbf{b}| $ ，所以我們有，例如， $ |\mathbf{s_A}\cdot\mathbf{e_B}| \leq |\mathbf{s_A}| \cdot |\mathbf{e_B}| \leq (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n}) $ ，最後一個不等式來自引理 1。
讓我們解決 $ e’_A $ 和 $ e’B $ . 我可以對向量進行採樣 $ \mathbf{e’} $ 從 $ \mathcal{D{\mathbb{Z^n},\alpha q}} $ 引理 1 將適用於它；如果 $ e’_A $ 是成員 $ \mathbf{e’} $ , 它肯定小於 $ ||\mathbf{e’}|| $ :
$ |e’_A| \leq ||\mathbf{e’_A}|| \leq \alpha q \sqrt{n} \leq (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n}) $ . 相同的 $ e’_B $ .
因此我有四個術語，所有 $ \leq (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n}) $ . 乘回去 $ 2 $ 你有結果。
編輯
他們稍後會在第 4 節中執行類似的程序，並明確寫出規範，以供將來參考。