關於具有重複秘密矩陣 S 的 LWE 的問題
考慮一個 LWE 的公式，其中我們給出 $ (x,S x+e) $ 或者 $ (x,u) $ - - 在哪裡 $ S $ 是一個 $ m \times n $ 秘密/隱藏矩陣， $ x $ 是隨機抽樣的 $ n \times 1 $ 向量， $ e $ 是一個 $ m \times 1 $ 高斯誤差向量，和 $ u $ 是一個均勻隨機樣本 — 並被告知要區分這兩種情況。根據這裡的文章，這對於經典算法來說應該很難。將此問題稱為“反向 LWE”。
我有幾個關於設置的問題。
沒有就很難區分問題嗎 $ e $ ?
請注意，在標準 LWE 中，當我們給出 $ (A,A s+e) $ 或者 $ (x,u) $ ，並告訴區分這兩種情況，問題很容易沒有錯誤。我們只需求解一個線性方程組即可得到 $ n $ 的條目 $ s $ .
但是，在這裡我們需要找到 $ m \times n $ 我們的秘密矩陣的條目 $ S $ . 我不知道如何做到這一點 $ m $ 方程。
考慮問題的一個變體，我們得到$$ { (x_1, Sx_1 + e_1), (x_2, Sx_2 + e_2), \ldots, (x_k, Sx_k + e_k)} ~~\text{or} $$
$$ { (x_1, u_1), (x_2, u_2), \ldots, (x_k, u_k)}, $$
並告訴區分這兩種情況。將此問題稱為“具有重複秘密的反向 LWE”。 $ k $ 是多項式大的 $ n $ . 這個問題難嗎？
請注意，混合參數（如此處的答案之一中使用的參數）表明問題仍然存在。這是混合動力車 $ H_i $ :
$$ H_i = { (x_1, Sx_1 + e_1), (x_2, Sx_2 + e_2), \ldots, (x_i, Sx_i + e_i), (x_{i+1}, u_{i+1}) \ldots, (x_{k}, u_{k}) } . $$
然後，有一個直接的方法可以得出結論，如果我們解決“具有重複秘密的反向 LWE”，我們可以解決反向 LWE。由於反向 LWE 很困難，我們的問題也應該很困難。
但是，我很難理解這個事實。
請注意，如果我們沒有誤差項，則有一種非常簡單的方法可以區分這兩種情況，因為 $ k \geq n+1 $ . 注意只能有 $ n $ 線性無關 $ x_i $ -s。所以，區分者只是尋找 $ n $ 清楚的 $ x_i $ -s 在給定的樣本中，注意矩陣的位置 $ S $ 將這些向量用於 $ n+1^{\text{th}} $ 不同的樣本，使用線性首先計算哪裡 $ S $ 把它帶到，然後檢查它是否與給出的一致。
為什麼錯誤術語使此區分器失敗？即使有高斯誤差，由於線性相關，不應該 $ n+1^{\text{th}} $ 不同的樣本是否足夠集中在某個值附近，以使我的區分器成功？
單個樣本的區分問題 $ x $ 是不可能的。
這是因為對於任何非零 $ x $ 和任何 $ u $ 存在一個 $ S $ 這樣 $ Sx=u $ .
預計到達時間 20220405：
對於更廣泛的區分問題 $ (\mathbf x_i,S\mathbf x_i+\mathbf e_i) $ 從 $ (\mathbf x_i,u_i) $ 與未知 $ S $ ，我們可以寫 $ X_{i,j} $ 為了 $ m\times m $ 具有常數對角線的對角矩陣 $ j $ 的第 $ \mathbf x_i $ . 然後的行 $ mn\times km $ 矩陣 $$ \left[\begin{matrix} X_{1,1} & X_{2,1} & X_{3,1} &\ldots & X_{k,1}\ X_{1,2} & X_{2,2} & X_{3,2} &\ldots & X_{k,2}\ \vdots & \vdots & \vdots & & \vdots\X_{1,n} & X_{2,n} & X_{3,n} &\ldots & X_{k,n}\\end{matrix}\right] $$ 形成一個格子，其中向量 $ ((S\mathbf x_1+\mathbf e_1)^T,(S\mathbf x_2+\mathbf e_2)^T,(S\mathbf x_3+\mathbf e_3)^T,\ldots,(S\mathbf x_k+\mathbf e_k)^T) $ 是一個接近向量（差向量的分量是 $ \mathbf e_i $ ）。對於大 $ k $ , 這種接近的向量極不可能來自均勻分佈。這僅告訴我們存在區分器的資訊；找到如此接近的向量在計算上將非常困難，因為 $ n $ 增長並且高斯分佈的變異數增長。