帶錯誤的環學習的偽隨機性
我的問題是在有錯誤的環學習中，讓 $ a(x)\in \mathbb{Z}_q(x)/(X^n+1) $ 在哪裡 $ n $ 是一種力量 $ 2 $ , 是一個隨機多項式, $ s(x),e(x)\in \mathbb{Z}q(x)/(X^n+1) $ 分別是具有從離散高斯分佈採樣的係數的秘密多項式和誤差多項式 $ D\sigma $ . 現在，RLWE 的決定性硬度表示樣本 $ a(x)\cdot s(x) + e(x) $ 與隨機多項式無法區分 $ u(x)\in \mathbb{Z}_q(x)/(X^n+1) $ .
- 現在，我的問題是多項式是否 $ a(x)\cdot s(x) $ $ i.e $ 沒有錯誤的 RLWE 樣本在多項式上與隨機字元串無法區分？據我所知，誤差多項式 $ e(x) $ 僅用於問題的硬度。它是否也有助於樣本的多項式不可區分性？
我問這個問題的原因是，最近我在Banerjee 等人的這些論文中發現了一個新問題 LWR。, Alwen 等人 Bogdanov 等人。它消除了誤差，但在四捨五入的每個係數中引入了一個誤差 $ a(x)\cdot s(x) $ , $ \lfloor p/q(.)\rceil : \mathbb{Z}_q\rightarrow \mathbb{Z}_p $ . 他們竭盡全力證明 LWR 樣本的計算不可區分性。RLWR 的計算不可區分性尚未得到證實。如果 $ a(x)\cdot s(x) $ 在計算上與隨機多項式無法區分 $ \mathbb{Z}_q $ 那我們不能說 $ \lfloor p/q(a(x)\cdot s(x))\rceil $ 在計算上也與隨機多項式無法區分 $ \mathbb{Z}_p/(X^n+1) $ 如果 $ p|q $
讓 $ R $ 成為戒指 $ \mathbb{Z}_p[X]/(X^n+1) $ ， 在哪裡 $ n $ 是 2 的冪。Ring-LWE 假設表明，對於任何隨機選擇的固定 $ s\in R $ , 的分佈
$$ ((a_1,a_1s+e_1),\ldots,(a_k,a_ks+e_k)) $$與分佈沒有區別$$ ((a_1,u_1),\ldots,(a_k,u_k)), $$在哪裡 $ a_i,u_i $ 是均勻隨機的 $ R $ 和 $ e_i $ 是從一些具有小係數的分佈中選擇的。 當然，如果一個 $ only $ 輸出 $ ((a_1s+e_1),\ldots,(a_ks+e_k)) $ 也沒有透露 $ a_i $ ，那麼這個分佈是平凡均勻隨機的（假設 $ s $ 是可逆的 $ R $ ，但這是一個小問題），因為 $ a_i $ 是均勻隨機的。這將是一個非常無用的屬性。
Ring-LWE 中有趣的部分是，即使當 $ a_i $ 顯示，分佈看起來仍然均勻。基本上，小的附加熵 $ e_i $ 允許創建一個具有更大熵的新的外觀均勻的元素。