如何證明基於乘法循環群的加密是 IND-CPA？
考慮以下加密和解密函式，其中 $ \mathbb{Z}_{N}^{*} $ 是循環乘法群， $ g $ 是組的生成器，並且 $ F $ 是一個鍵控 PRF。
$ E(m, i, k) = m \times g^{F_k(i)} \bmod N $
$ D(c, i, k) = c \times g^{-F_k(i)} \bmod N $
以上方案是IND-CPA嗎？我將如何證明？
我的第一個想法是我需要證明如果 $ g $ 那麼是發電機 $ m \times g^{F_k(i)} \bmod N $ 是雙射，但我不確定如何提出正式證明。
這是我將如何處理證明（這是一個草圖）：
可以在《現代密碼學概論》第 89 頁的定理 3.26 的證明中找到具有類似方法的證明。
步驟 1) 證明替換 $ F_k $ 具有統一的功能 $ f $ 只能在不可區分博弈中給予對手微不足道的不同優勢。為此，請選擇一個區分器 $ D $ 對於偽隨機鍵控函式 $ F_{k} $ . $ D $ 可以訪問一個等於 $ F_k $ 或者 $ f $ . 有 $ D $ 模擬不可區分遊戲的視圖 $ A $ 通過選擇隨機 $ i $ 並有 oracle 輸出 $ f(i) $ 或者 $ F_k(i) $ ( $ D $ 不知道是哪一個）。如果 $ A $ 是正確的， $ D $ 輸出 1，否則 $ D $ 輸出 0。因為 $ F_k $ 是一個偽隨機函式，它遵循 $ A $ 必須使用實際加密方案贏得遊戲，與修改後的加密方案（其中 $ F_k $ 被替換為 $ f $ ).
步驟 2) 證明修改後的加密方案，其中 $ F_k $ 被替換為 $ f $ 是 IND-CPA 安全的。這可以通過機率分析來完成。首先註意到因為 $ g $ 是組的生成器，組中的每個元素都可以表示為 $ g^{x} $ 對於一個整數 $ x $ . 因此，由於 $ f $ 是統一的， $ g^{f} $ 均勻分佈在乘法群中 $ \mathbb{Z}{N}^{*} $ . 接下來，由於 $ g $ 是生成器，並且由於 $ m\in\mathbb{Z}{N}^{*} $ , $ m=g^{x} $ 從某個整數 x。因此我們可以寫 $ E(m, i, k) = m \times g^{f(i)} \bmod N = g^{x} \times g^{f(i)} \bmod N = g^{x+f(i)} \bmod N $ . 自從 $ f $ 是統一的， $ x+f(i) $ 也是均勻的，因此 $ g^{x+f(i)} \bmod N $ 也是統一的。通過讓來完成證明 $ q(n) $ 是查詢數的上限 $ A $ 可以發送到不可區分遊戲的神諭。A具有優勢的唯一方法是如果相同 $ i $ 使用了兩次。如果 $ i $ 均一地選自 $ {{0,1}}^{n} $ ，那麼這個機率是 $ q(n) \times 2^{-n} $ 這是微不足道的。