LWE 加密錯誤

在使用錯誤加密方案進行學習（例如在 Kyber 方案中）。有兩個向量： $ u = r^t A + e_2 $ 和 $ v= r^t * pk + e_3 + \lfloor \frac{q}{2}\rceil m $ 這樣 $ pk = As +e_1 $ .

我的問題是，如果我們省略，加密是否仍然安全 $ e_3 $ 所以 $ v = r^t * pk + \lfloor \frac{q}{2}\rceil m $ .

據我所知（以及我目前的理解水平）答案是肯定的，因為根本問題是（Mod/Ring/Primal）LWE 問題。

不，它不再安全。Kyber 是一種名為“LPR 加密”的密碼系統的實例。它的公鑰是零的 LWE 加密 $ (A, As + e_1) $ . 加密通過計算進行

1. $ u = r^tA + e_2 $ （所以 $ u^t = A^t r + e_2^t $ )，矩陣下零的LWE加密 $ A^t $ （這顯然與 $ A $ ）， 接著
2. $ v = r^t (As + e_1) + (q/2)m + e_3 $ ，使用隨機填充的零 LWE 加密 $ (As + e_1) $ .

爭論安全，你首先

1. 在 LWE 假設下爭論 $ As + e_1 $ 是偽隨機的，即你可以用一個均勻隨機的字元串替換它。
2. 認為 $ v $ 現在是形式 $ \langle r,pk\rangle + (q/2)m+e_3 $ , 即是一個 LWE 加密 $ m $ . 你還需要爭辯說釋放 $ (rA^t + e_2) $ 不會損害安全性，但暫時忽略這一點（不需要顯示您的提案不安全）。

根據您的修改，第二步將不再起作用，因為 $ \langle r, pk\rangle + (q/2)m $ 不是 LWE 加密（而是“無雜訊 LWE 加密”）。眾所周知，無雜訊 LWE 加密容易受到簡單攻擊，例如使用高斯消元法。因此，人們可以通過查看 ( $ pk, r^tpk + (q/2)m) $ 作為一個無雜訊的 LWE 加密 $ m $ ，並在此設置中執行標準攻擊。

---

我達到上述攻擊的方法很簡單——查看證明，看看哪一步不再有效，看看你是否可以攻擊它。我強烈建議您以這種方式思考問題，而不是簡單地“它使用 LWE，所以它很安全”，因為這樣的推理在密碼學中幾乎是不合理的。

引用自：https://crypto.stackexchange.com/questions/102127