兩個 LWE 類型樣本的計算不可區分性
考慮區分多項式多個樣本的問題 $$ \begin{equation} (x, b, As + e)
\text{or}\left(x, b, ~Ax + b\cdot(As + e) + e’\right). \end{equation} $$這裡， $ A $ 是一個公共矩陣並且 $ s $ 是一個隨機均勻選擇的秘密向量。 $ e $ 和 $ e’ $ 是高斯誤差。 $ x $ 和 $ b $ 隨機均勻採樣。
不同物體的尺寸為：
$$ \begin{align} b &\in {0, 1}, \ x &\in \mathbb{Z}{q}^{n}, \ s &\in \mathbb{Z}{q}^{n}, \ A &\in \mathbb{Z}{q}^{m \times n}, \ e, e’ &\in \mathbb{Z}{q}^{m}, \ \end{align} $$
$ q \geq 2 $ 是一個素數。
當我們給定多項式許多樣本時，這兩種情況（在計算上）是否無法區分？我認為它們是，但我無法將它們與猜想聯繫起來。
請注意，通過 LWE，
$$ \begin{equation} (x, b, As + e)
\text{and}\left(x, b, u\right), \end{equation} $$ 在計算上無法區分，因此 $$ \begin{equation} (x, b, ~Ax + b\cdot(As + e) + e’)\text{and}\left(x, b, ~Ax + b\cdot u + e’\right). \end{equation} $$$ u $ 是一個均勻隨機的樣本。但是，我無法將我的案例簡化為 LWE。
可以輕易分辨 $ (x,0,u) $ 從 $ (x,0,Ax+e’) $ 通過減去 $ Ax $ 從第三個條目開始，看看這些條目看起來是均勻的還是高斯的。
區分 $ (x,1,u) $ 從 $ (x,1,A(x+s)+(e+e’)) $ 是一個標準的 LWE 問題（注意 $ e+e’ $ 是變異數的總和 $ e $ 和 $ e’ $ .
因此樣本與 $ b=0 $ 是微不足道的，樣本與 $ b=1 $ 估計不是。取多項式許多樣本幾乎肯定會給出至少一個 $ b=0 $ 因此，讓我們可以簡單地區分。