Encryption
具有二進制矩陣 A 的 LWE
在 LWE 中，我們知道給定合理的公共參數一個∈從n×lq $ A\in \mathbb{Z}_q^{n\times \lambda} $ ， 秘密s∈從lq $ s\in \mathbb{Z}_q^{\lambda} $ 和噪音和∈Xn $ e\in \mathcal{X}^{n} $ ， 隨機的r∈從nq $ r\in \mathbb{Z}_q^{n} $ ,(一個,b=一個⋅s+和) $ (A, b = A\cdot s + e) $ 和(一個,r) $ (A, r) $ 在計算上是無法區分的。
然後，考慮另一種情況一個 $ A $ 從 q 的子欄位中採樣。例如，設置一個∈從n×l2 $ A\in \mathbb{Z}_2^{n\times \lambda} $ , 其他同上。此時，是(一個,b=一個⋅s+和) $ (A, b = A\cdot s + e) $ 和(一個,r) $ (A, r) $ 在計算上仍然無法區分。
類似於問題LWE question with a sparse matrix，但是一個 $ A $ 由二進制隨機線性碼構成。
只有當 A 是均勻隨機的時，LWE 問題才被認為是困難的，事實上，在特殊情況下很容易被打破，例如當 A 是二元的或具有某種非常特殊的結構時。
請注意，在多項式環上存在擴展的 LWE 版本，其中（基本上）矩陣 A 中的所有列只是第一列的旋轉（這也可以擴展到模組，其中 A 是塊矩陣，其中每個塊都有一個新的隨機第一列，參見Vadim Lyubashevsky對 Ring-LWE 和 Module-LWE 方案的調查）。我承認這與您最初詢問的內容有些不同。