RLWE 樣本的聯合分佈
假設我們有多項式空間 $ R_q $ 定義為 $ R_q = Z_q/(X^n + 1) $ . 我們抽取樣本 $ s_i \gets R_q $ 均勻隨機。此外，我們定義了誤差分佈 $ \chi $ 作為一個離散的中心高斯分佈 $ B $ . 我們計算以下數量： $ h_i = s_ip_1 + e_i $ 在哪裡 $ p_1 \in R_q $ 是一個固定多項式。我們注意到 $ s_i $ 和 $ e_i $ 不被釋放。公共多項式 $ p_1 $ 隨機選擇並為所有人共享 $ h_i $ .
根據 RLWE 問題的難度，我們知道 $ h_i $ 在計算上與隨機樣本無法區分 $ R_q $ . 我想知道我們對聯合分配有什麼保證 $ (h_0, h_1, …) $
RLWE 不保證 $ h_i $ 對於任何固定的，在計算上與製服無法區分 $ p_1 $ : 只考慮情況 $ p_1 = 0 $ .
在另一端，如果 $ p_1 $ 是可逆的 $ R_q $ （這是一般情況），然後每個 $ h_i $ 完全均勻地分佈在 $ R_q $ ，並且它們都是獨立的，因此聯合分佈在產品上是均勻的。你甚至不需要隨機性項來保持它，所以這又與 RLWE 無關（請記住，RLWE 告訴你一些關於聯合分佈的資訊 $ (s_i, h_i) $ ; 因為你不包括 $ s_i $ 對的一部分，它並不是真正需要的）。
在中間情況下，當 $ p_1 $ 是一個零除數但非零，每個 $ h_i $ 分佈為理想的均勻元素的總和 $ p_1 R $ （這完全由gcd決定 $ p_1 $ 和 $ X^n+1 $ 超過 $ \mathbb{F}_q $ ) 和隨機性 $ \chi $ . 將此類樣本與隨機樣本區分開來的難易程度基本上取決於理想的余維數作為 $ \mathbb{F}_q $ -向量子空間 $ R_q $ （即gcd的度數）和高斯寬度 $ \chi $ . 在這種情況下，同樣，您有來自同一分佈的獨立樣本，因此關於 $ h_i $ ’s: 這只是產品分佈。