Key-Exchange

嘗試實現 ring-LWE KE 理解概念

  • October 22, 2016

今天看了這麼多關於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

更新:我嘗試用sage編寫程式碼(沒有任何錯誤),但仍然有問題。我現在確定我的數學是錯誤的。是聖人程式碼的連結。

在我看來,問題在於您設置的向量/矩陣乘法。

你現在擁有的: $ 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。

引用自:https://crypto.stackexchange.com/questions/40309