Homomorphic-Encryption
主動攻擊者如何破解 CPA 安全的 LWE 密碼系統？
LWE 加密系統僅是 CPA 安全的，例如基於格的密碼學的十年中所述。考慮那裡描述的以下系統（第 5.2 節）
- 密鑰是統一的 LWE 密鑰 $ s \in \mathbb{Z}_q^n $ , 公鑰是一些 $ m \approx (n+1) \log(q) $ 樣品 $ (\bar{a}_i, b_i = \left <\bar{a}_i, s \right > +e $ 收集為矩陣的列 $ A $ $$ A = \begin{pmatrix} \bar{A} \ b^t \end{pmatrix} \in \mathbb{Z}_q^{(n+1) \times m} $$ 在哪裡 $ b^t = s^t \bar{A} +e e^t \mod q $ .
- 加密一點 $ \mu \in \mathbb{Z}_2 = {0,1} $ 使用公鑰 $ A $ , 選擇一個 unifrom $ x \in {0,1}^m $ 並輸出密文 $$ c = A \cdot x + (0, \mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1} $$
- 使用密鑰解密 $ \mathbb{s} $ ，一個計算： $$ (-s, 1)^t \cdot c = (-s, 1)^t \cdot A \cdot x +\mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1} $$ $$ = e^t \cdot x + \mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1} $$ $$ \approx \mu \cdot \lfloor \frac{q}{2} \rceil \in \mathbb{Z}_q^{n+1} \mod q $$ 並測試它是否更接近 $ 0 $ 或者 $ \frac{q}{2} \mod q $ .
該論文指出，“我們注意到系統在主動或選擇密文攻擊下很容易被破壞”。
這樣的攻擊會是什麼樣子？我會考慮加密 $ 0 $ 位與 $ x $ 成為一切 $ 1 $ -s 向量檢索 $ e $ 然後檢索 $ s $ 通過 $ \bar{A}^{-1} \cdot (b-e) $ . 還有其他已知的方法嗎？是否有已知的方法可以將這些攻擊擴展到 NIST-pqc 入圍候選人的 CPA 安全版本，例如 Kyber？
考慮到對手 $ A $ 選擇兩條消息 $ m_1 = 0 $ 和 $ m_2 = 1 $ 根據Ind-CCA1比賽並與挑戰者比賽。
敵手 A 發送 $ m_1 $ 和 $ m_2 $ 給挑戰者。
挑戰者隨機選擇 $ b $ 之間 $ 0 $ 和 $ 1 $ ; $ b \stackrel{$}{\leftarrow} $ {0,1}
挑戰者計算 $ c:=Enc(s,m_b) $ 並且寄出 $ c $ 至 $ A $ .
對手在多項式時間內執行其他操作，包括對加密/解密預言機的呼叫，用於不同的密文 $ c $ .
- $ c_0 = EncOracle(0) $
- $ c’ = c \oplus c_0 $
即執行同態加法 $ m_b $ 零！
- $ m’ = DecOracle(c’) $
這是一個有效的請求，因為 $ c’ \neq c $ .
- 我們有 $ m’ = m_b $
如果 $ m’ = 0 $ 返回 $ 0 $
否則返回 $ 1 $
對手以優勢 1 贏得比賽。
換句話說，密文是可延展的，沒有完整性來保護 CCA1 對手。