說明 PK 加密方案正確性的更準確方法是什麼？
如果對所有人來說，說明公鑰加密方案是正確的，是否更準確？ $ m \in M $ 和 $ (pk, sk) \in \operatorname{Gen}(1^k) $
一個。 $ \operatorname{Dec}{sk}(\operatorname{Enc}{pk}(m))=m; $ 或者，
乙。 $ \Pr[\operatorname{Dec}{sk}(\operatorname{Enc}{pk}(m))=m] = 1 - \operatorname{negl}(k); $ 或者，
丙。它取決於方案或其他一些因素嗎？
在a或b之間做出決定是選擇公鑰加密定義的問題。顯然a是可取的，而b是一個備用方案，以便允許一些有趣的密碼系統。定義是根據所研究的密碼系統選擇的，如c中所示。
正如 poncho 在評論中指出的那樣，在b中，其含義是對於所有密鑰和消息，解密不會產生原始消息的機率可以忽略不計。加密算法被重新表示為具有額外輸入的確定性算法 $ r $ 對於隨機允許實現 CPA 安全性，這確實意味著 $$ \Pr[\operatorname{Dec}{sk}(\operatorname{Enc}{pk}(m, r))=m]\quad=\quad1 - \operatorname{negl}(k) $$ 在所有輸入上計算機率 $ r $ 隨機化加密。對於某些密碼系統，例如基於隱場方程的密碼系統，這種對罕見故障的容忍度是必要的。
b至少還有另一種流行的替代方案：我們可以要求除了極少數密鑰之外的所有密鑰都允許對所有消息進行某些加密和解密 $ m\in M $ . 因此，我們計算存在消息的機率 $ m $ 和隨機輸入 $ r $ 使加密/解密故障轉移生成的密鑰集 $ \operatorname{Gen}(1^k) $ （或者更準確地說，在該算法的一組隨機輸入上，重新表示為具有隨機輸入的確定性輸入 $ r $ ）。這是 Jonathan Katz 和 Yehuda Lindell在《現代密碼學導論》第 2版中對公鑰加密的定義。他們的理由是允許 RSA 進行機率素數測試。他們明確選擇忽略異常。
更新：在 IMC 第 3版中，略有變化。機率是根據隨機性計算的 $ \operatorname{Gen} $ 和 $ \operatorname{Enc} $ . 我認為它將堅持作為公鑰加密的標准定義。
然而，其他密碼系統僅使用a是正確的，例如具有已證明素數的 RSA，或在使用曲線族和已證明順序的生成器時的 ECIES。