LWE 與矩陣 A 重複
考慮以下版本的學習錯誤。
你要麼被給予(一個,一個s1+和1,一個s2+和2,…,一個sķ+和ķ) $ (A, As_1 + e_1, As_2 + e_2, \ldots, As_k + e_k) $ 或者(一個,在1,在2,…,在ķ) $ (A, u_1, u_2, \ldots, u_k) $ ， 在哪裡
- 一個 $ A $ 是一個米×n $ m \times n $ 其條目來自欄位的矩陣從q $ \mathbb{Z}_q $ — 條目是隨機均勻抽樣的。
- 在1,在2,…,在ķ $ u_1, u_2, \ldots, u_k $ 是米×1 $ m \times 1 $ , 每個條目都來自該欄位從q $ \mathbb{Z}_q $ 均勻隨機。
- 每個和1 $ e_1 $ ,和2 $ e_2 $ ,… $ \ldots $ ,和ķ $ e_k $ 是一個米×1 $ m \times 1 $ 高斯雜訊向量。
- 每個s1,s2,…,sķ $ s_1, s_2, \ldots, s_k $ 是一個n×1 $ n \times 1 $ 秘密字元串。
你被告知要區分這兩種情況。
假設標準 LWE 很難，這個問題也很難嗎？
一般來說，不同的矩陣一個 $ A $ 對每個 LWE 樣本進行採樣。在這裡，我們有相同的矩陣一個 $ A $ 但ķ $ k $ 不同的秘密。這會改變設置嗎？
您還沒有完全說明問題，但我假設它是為了區分構造的集合sķ $ \mathbf s_k $ 價值觀。
在 LWE 的通常公式中，我們給出米 $ m $ 對應不同的樣本n $ n $ -長向量。這些可以組合成一個米×n $ m\times n $ 矩陣一個 $ A $ 所以“標準”的 LWE 決策問題是區分(一個,一個s1+和1) $ (A,A\mathbf s_1+\mathbf e_1) $ 從(一個,在1) $ (A,\mathbf u_1) $ .
鑑於這樣的問題，對手可能會產生自己的問題sj $ \mathbf s_j $ ,和j $ \mathbf e_j $ 和在ķ $ \mathbf u_k $ 為了j=2,…ķ $ j=2,\ldots k $ 並通過將決策 LWE 的兩個輸入與它們自己的輸入相結合來創建問題的兩個假定實例，即{(一個,一個s1+和1,一個s2+和2,…一個sķ+和ķ),(一個,在1,…,在ķ)} $ {(A,A\mathbf s_1+\mathbf e_1,A\mathbf s_2+\mathbf e_2,\ldots A\mathbf s_K+\mathbf e_k),(A,\mathbf u_1,\ldots,\mathbf u_k)} $ 和{(一個,一個s1+和1,在2,…,在ķ),(一個,在1,一個s2+和2,…,一個sķ+和ķ)} $ {(A,A\mathbf s_1+\mathbf e_1,\mathbf u_2,\ldots,\mathbf u_k),(A,\mathbf u_1,A\mathbf s_2+\mathbf e_2,\ldots,A\mathbf s_K+\mathbf e_k)} $ . 如果有一種方法可以解決您的問題，它應該在第一種情況下工作，以區分集合s1 $ \mathbf s_1 $ 從而解決了原來的決定性 LWE。如果給定無效輸入，求解器會如何表現，這是一個問題，但我們應該能夠再次區分優勢。