Lattice-Crypto
為什麼我們在 LWE 的定義中添加錯誤？
LWE 問題的各種等效定義之一如下：
讓 $ n,q $ 為整數 ( $ q $ 通常是素數）， $ \chi $ 離散機率分佈 $ \mathbb{Z} $ （通常是離散的高斯分佈）和 $ s $ 一個秘密向量來自 $ \mathbb{Z}_q^n $ .
我們表示 $ \mathcal{L}_{s,\chi} $ 機率分佈 $ \mathbb{Z}_q^n \times \mathbb{Z}_q $ 通過選擇獲得 $ a \in \mathbb{Z}_q^n $ 均勻隨機，選擇 $ e $ 均勻隨機地從 $ \chi $ 並考慮到 $ \mathbb{Z}_q $ , 併計算 $ (a,b=(\langle a,s\rangle + e)) \in \mathbb{Z}_q^n \times \mathbb{Z}_q $ .
錯誤搜尋學習是為了恢復 $ s $ 從樣品 $ (a,b) $ 從…獲取 $ \mathcal{L}_{s,\chi} $ .
我的問題是我們為什麼要添加錯誤 $ e $ ? 我想這是出於安全原因。在那種情況下，我們將如何獲得 $ s $ 從 $ (a,b=(\langle a,s\rangle)) $ ?
由於添加了一些錯誤 $ e $ 是許多基於格的結構中的中心塊，這可能是一個更普遍的問題。添加此錯誤有什麼意義？
在那種情況下，我們將如何獲得 $ s $ 從 $ (a,b=(\langle a,s\rangle)) $ ?
操作 $ \langle a,s\rangle $ 是矩陣乘法，即完全線性，因此高斯消元允許我們恢復 $ s $ 有效率的。