嘗試實現 ring-LWE KE 理解概念
今天看了這麼多關於ring-LWE密鑰交換的內容，決定用java實現，看看能不能用。不是現實世界的實現，只是為了看看數學是否可行。我的假設是，給定某種多項式環，編寫程式碼會很簡單。結果證明我的假設是錯誤的。我在網際網路上搜尋基本的單變數多項式環庫，我發現了這個。它看起來很簡單，並且已經進行了一些程式碼通過的jUnit 測試。我從這裡複製了參數。簡而言之， $ \mathbb{Z_{2^{23}-1}} / (x^{1024} + 1) $ .
我遵循Regev 的基本對賬方法並執行程式碼。即使沒有錯誤，交換的密鑰也不匹配。顯然，出了點問題，我確定它來自我的程式碼而不是多項式環庫。也許我不了解 ring-LWE 的一些基本原理。我在這裡附上了程式碼：
這是 GitHub 儲存庫的連結。任何幫助，將不勝感激。我不知道我做錯了什麼。
數學：維度 = 4（任意）
$ A, S, S’ = [rx^3 + rx^2 + rx + r,\ rx^3 + rx^2 + rx + r,\ rx^3 + rx^2 + rx + r,\ rx^3 + rx^2 + rx + r] $
英石 $ r \in \mathbb{Z_{q}} $ （隨機生成）
$ B = AS + error $ , $ B’ = AS’ + error $
$ Shared key = SB’ = S’B \to $ 我沒有使用任何錯誤（ $ error =0 $ ) 但共享密鑰仍然不匹配。
虛擬碼：
dimension = 8 # arbitrary modulus = 65537 R = PolynomialRing(GF(modulus), "X") S = R.quotient(X^1024 + 1, "x") A = generate_matrix(dimension, modulus) S = generate_matrix(dimension, modulus) S_ = generate_matrix(dimension, modulus) B = A.transpose()*S B_ = A.transpose()*S_ alice = S*B_ bob = S_*B print alice == bob # returns false
在我看來，問題在於您設置的向量/矩陣乘法。
你現在擁有的： $ a, s, s’ $ 是環元素的行向量。
$$ \text{Alice: } sB’ = sa^ts’ $$ $$ \text{Bob: } s’B = s’a^ts $$ 顯然，矩陣乘法不是可交換的，但與底層環元素相乘也不是，因為它們是環元素。
所以你需要洗牌和轉置一些東西。
讓 $ B = a^ts $ ， 和 $ B’ = s’^ta $ .
現在讓愛麗絲計算 $ B’^t s^t $ , Bob 計算 $ s’B^t $ . 如果你解決了，這將為 Alice 和 Bob 提供一致的密鑰。
證明：我修改了你的 sage 腳本，它現在返回 true。