Key-Exchange
基本 Ring-LWE-DH 密鑰協商中的失敗機率計算
這是基於 Peikert 的 Ring-LWE KEM 的基本未經身份驗證的基於 Ring-LWE 的 Diffie-Hellman 密鑰交換：（來自BCNS15）
- Alice 和 Bob 共享公共多項式 $ a $ 從隨機抽取 $ R_q = \mathbb{Z}_q /(x^n+1) $ ，以及已知的誤差分佈 $ \chi $ 有標準差 $ \sigma $
- Alice 生成隨機的小秘密多項式 $ s_A, e_A \in R_q $ 根據分佈 $ \chi $ , 計算 $ b_A = a \cdot s_A + e_A $ 並將其發送給 Bob
- Bob 生成隨機小秘密多項式 $ s_B, e_B \in R_q $ 根據分佈 $ \chi $ , 計算 $ b_B = a \cdot s_B + e_B $ 並將其發送給 Alice
- 愛麗絲計算 $ k_A = s_A \cdot b_B = a \cdot s_A \cdot s_B + s_A \cdot e_B $
- 鮑勃計算 $ k_B = s_B \cdot b_A = a \cdot s_A \cdot s_B + s_B \cdot e_A $
$ k_A $ 和 $ k_B $ 除了誤差項外，它們大致相等。因此，Alice 和 Bob 使用協調函式 rec(.) 使得 rec( $ k_A $ ) = 推薦 ( $ k_B $ ) = $ K $ 是共同的共享秘密。
基本協調方案（來自BCNS15）將多項式的每個係數四捨五入為 0 或 $ q/2 $ ， 和 $ q/2 $ 被視為 1，因此 $ K $ 是一個 $ n $ 位字元串。BCNS15表示該方案的失敗機率為 $ 1/2^{10} $ . 這是如何計算的？
這是我一直在嘗試的一般方法：
- 為了成功的密鑰交換，我們必須有 $ |k_A[i] - k_B[i]| < \delta $ 為了 $ i \in {0, 1, \cdots, n-1} $ ， 在哪裡 $ k_A[i] $ 和 $ k_B[i] $ 表示 $ i $ -th 多項式係數 $ k_A $ 和 $ k_B $ 分別和 $ \delta $ 是對賬方案的容錯度
- 在這種情況下， $ k_A - k_B = s_A \cdot e_B - s_B \cdot e_A $ 和 $ \delta = q/4 $
- 讓 $ p $ 是機率 $ |k_A[i] - k_B[i]| > \delta $ 對於一些 $ i $ ，即解碼任意一位的錯誤機率 $ K $ . 那麼，總的失效機率為 $ 1 - (1 - p)^n \approx np $ 對於小 $ p $
- 讓誤差分佈 $ \chi $ 有支持 $ [-t\sigma, +t\sigma] $ ， 在哪裡 $ t $ 是由採樣器實現的精度決定的一個因素。然後，任何係數的最大可能絕對值 $ s_A \cdot e_B $ 或者 $ s_B \cdot e_A $ 是 $ nt^2\sigma^2 $ ，所以我們必須有 $ 2nt^2\sigma^2 < q/4 $ 或者 $ q > 8nt^2\sigma^2 $
一種具體的解決方案是顯式計算每個係數的分佈。在這個特定的環中，如果 e 和 s 的係數分佈是對稱的，則可以將其計算為係數乘積分佈的 2n 倍卷積。此處提供了一個範例（由於四捨五入而有些複雜）：
https://github.com/pq-crystals/security-estimates/blob/master/Kyber_failure.py
更多的數學方法（可能會給出更寬鬆的界限）涉及研究矩生成函式。這可以使用亞高斯隨機變數理論很好地抽像出來。