Affine Hill Cipher 的語義安全 IND-CPA
密文 $ c $ 對應明文 $ m $ 是（誰）給的 $ c= mK + w $ . $ K $ 是可逆矩陣，w 是均勻分佈的隨機向量。
如果 $ w $ 在每次加密過程中都會改變，這個仿射希爾密碼會滿足 IND-CPA 嗎？
如果 $ w $ 使用 PRNG 生成，並且這種類型的加密用作同態加密保持 $ K $ 同樣，它還會提供IND-CPA嗎？
在解密過程中， $ w $ 應該先從密文中減去，然後乘以 $ K $ . 對於解密，可以使用 PRNG（基於 LFSR）的密鑰。
$ (m1 + m2) = [(c1 + c2) - (w1 + w2)]K^{-1} $
讓 $ G:{0,1}^{r+l}\to{0,1}^* $ 是一些偽隨機生成器，讓 $ K\in\text{GL}(\mathbb K,d\times d) $ 是某個域上的任何可逆矩陣 $ \mathbb K $ 然後讓 $ k\in{0,1}^{r+l} $ 成為秘鑰 $ G $ 和 $ f:{0,1}^*\to \mathbb K^d $ 是一些將 PRG 輸出映射到向量的雙射函式，然後 $ E_{K,k}(m):=m\cdot K+f(G(k)) $ .
該方案是確定性的，即給定相同的密鑰和相同的消息，它將始終返回相同的加密，因此不能是 CPA 安全的。
但是，我們可以輕鬆修改上述方案以使其具有 CPA 安全性。讓 $ G,K,f $ 如上，讓 $ k\in{0,1}^r $ . 定義 $ E_{K,k}’:=n\stackrel{$}{\gets}{0,1}^l;n\parallel m\cdot K+f(G(k\parallel n)) $ ， 在哪裡 $ \stackrel{$}{\gets} $ 意思是 $ n $ 從 $ {0,1}^l $ .
基本上對於每個加密，我們都會生成一個隨機數 $ n $ ，將其附加到密文中，然後使用隨機數和密鑰的組合生成隨機比特流。這就是流密碼的工作原理，但我們使用的是向量加法而不是 XOR。實際上，人們可以做出適當的選擇 $ f,K $ 通過選擇將其變成經典的流密碼 $ K=\mathbb F_2 $ 和 $ f $ 將位串映射到相同字元串的向量。雙射性 $ f $ 需要保持輸出元素的均勻隨機分佈，使其成為適當的“墊”。至於為什麼 $ K $ 在那裡，我不知道，它對這個方案的安全沒有任何作用。