了解多項式 CPA (IND-CPA) 安全性的定義
我剛開始研究加密方案，在理解 IND-CPA 安全性的以下定義時遇到了一些麻煩：
$ E $ 如果對所有對手來說，多項式 CPA (IND-CPA) 是安全的 $ A $ 和所有多項式 $ p $ ， 我們有： $ Adv_a <= \frac{1}{p(\lambda)} $ 對於足夠大 $ \lambda $ ，即：對所有人 $ A $ 和所有 $ p $ , 存在一個 $ N_p>0 $ 這樣 $ Adv_a \leq \frac{1}{p(\lambda)} $ 對所有人 $ \lambda > N_p $ .
據我了解，在一個簡單的 IND-CPA 遊戲中，預言機向對手發送密文，該密文是對手選擇的兩種可能消息之一的加密。對手現在需要回复實際消息是什麼。
我不明白的是我應該如何解釋多項式 $ p $ 和參數 $ \lambda $ . 它們由什麼組成？
正如維基百科所解釋的：
使用多項式倒數公式的原因與將計算有界性定義為多項式執行時間的原因相同：它具有數學閉包特性，使其在漸近設置中易於處理。例如，如果攻擊成功違反安全條件的機率可以忽略不計，並且攻擊重複多項式次數，則整體攻擊的成功機率仍然可以忽略不計。
這就是為什麼您希望它適用於所有多項式 $ p $ 在你的定義中。
同樣重要的是要注意，在這個定義中，暗示對手具有多項式有界的計算能力。
這基本上意味著在 IND-CPA 博弈中，對手有權在將兩個明文發送給挑戰者之前執行多項式有界數量的加密或其他操作，挑戰者將選擇一個並將其加密返回給對手，後者現在必須猜測它對應於哪些明文。
讓我用一個例子來發展這個：在 RSA-OAEP 的情況下，這例如禁止對手使用GNFS 分解公鑰，因為它的複雜性為：
$$ \exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right) =L_n\left[\frac{1}{3},\sqrt[3]{\frac{64}{9}}\right] $$ 用於分解數字 $ n $ ，但我們通常對安全參數感興趣，在 RSA-OAEP 情況下，它是 $ \lambda=\log_2(n) $ , 但這不是問題，因為它的執行時間是超多項式但大小是次指數的 $ \lambda $ 輸入的 $ n $ : $$ O\left(\exp\sqrt[3]{\frac{64}{9} \lambda (\log \lambda)^2}\right) $$所以它仍然不是多項式算法，因此在研究 RSA-OAEP 的 IND-CPA 安全性時不能考慮。 但是，如果要證明因式分解是多項式的，那麼由於它，對手將在 RSA-OAEP 案例中贏得 IND-CPA 遊戲。
PS：如下所述，plain RSA 不是 IND-CPA ，因為它是確定性的。