形式陈述

公钥加密方案由概率算法 $(\operatorname{Gen},\operatorname{Enc},\operatorname{Dec})$$(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$ 组成：

$$ (pk,sk)\leftarrow\operatorname{Gen}(1^\lambda),\quad c\leftarrow\operatorname{Enc}_{pk}(m),\quad \operatorname{Dec}_{sk}(c)=m $$$$(pk,sk)\leftarrow \mathrm{Gen}(1^{\lambda }),c\leftarrow {\mathrm{Enc}}_{pk}(m),{\mathrm{Dec}}_{sk}(c)=m$$

以压倒性概率满足正确性。公钥可公开用于加密，私钥用于解密。现代保密性通常以 IND-CPA 定义：攻击者即使取得公钥并选择两条等长消息，也不能区分其中哪条被加密；更强的 IND-CCA 允许受限解密查询。安全加密通常必须随机化或带随机 nonce。

直觉

把“上锁能力”和“开锁能力”分离：任何人可用公开信息封装消息，只有私钥持有者能恢复内容。

例子与边界

朴素确定性 RSA 不满足一般 IND-CPA，因为攻击者可自行加密候选消息比较密文；安全方案需使用经证明的随机填充或 KEM–DEM 组合。公钥加密本身不认证发送者，也不解决公钥属于谁的问题，需证书、已认证信道或其他信任机制。消息长度、密文合法性和解密错误处理也属于方案定义的一部分。

推论与应用

公钥加密支持开放网络中的密钥封装、混合加密和多接收者通信。实际系统通常用公钥部分建立短会话密钥，再用高效对称认证加密传输数据。

参考资料

• Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023，Chs. 11–12, public-key encryption and chosen-ciphertext security。
• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020，Chs. 11–13, public-key encryption and security notions。