1.2 公钥加密及安全模型

1.2.1 公钥加密的定义

公钥加密方案（Public Key Encryption，PKE）由以下四个多项式时间算法组成：

●系统参数生成算法SP←Setup(λ)：算法输入安全参数λ，输出系统公开参数SP。该算法由可信中心运行，其中SP包含明文空间M和密文空间C的描述且对所有实体公开。

●公私钥生成算法(pk,sk)←KeyGen(SP)：算法输入系统公开参数SP，输出用户的公私钥对(pk,sk)，其中pk是用户的公钥(用于数据加密)，sk是用户秘密保存的私钥(用于密文解密)。该算法由用户运行。

●加密算法C←Encrypt(SP,pk,M)：算法输入系统公开参数SP、接收者公钥pk和待加密消息M∈M，输出密文C∈C。

●解密算法M/⊥←Decrypt(SP,sk,C)：算法输入系统公开参数SP、解密者私钥sk以及密文C，输出明文消息M或者解密失败符号⊥。

在绝大多数场景中，公钥加密应满足正确性要求：对任意的SP←Setup(λ)和(pk,sk)←KeyGen(SP)，若C←Encrypt(SP,pk,M)，则Decrypt(SP,sk,C)=M。

1.2.2 安全模型

公钥加密算法的标准安全模型是选择密文攻击下的不可区分安全模型（Indistinguishability against Chosen-Ciphertext Attack，IND-CCA）。该安全模型通过挑战者（Challenger）和敌手（Adversary）之间的游戏来定义，模型共分为以下5个阶段：

●系统建立：令SP为系统公开参数，挑战者运行KeyGen算法生成一个公私钥对（pk，sk），并将pk发送给敌手。挑战者秘密保存sk。

●询问1：该阶段允许敌手以自适应性的方式发起密文解密询问。设敌手询问的密文为C_i，则挑战者运行解密算法并将解密结果发送给敌手。

●挑战：敌手选择两个不同的消息M₁，M₂∈M作为挑战数据。挑战者随机选取一个比特b∈{0,1}，计算挑战密文C*←Encrypt（SP，pk，M_b），并将C*发送给敌手。

●询问2：敌手可继续询问密文C_i≠C*的解密，挑战者根据询问1回复敌手。

●猜测：敌手输出对b的猜测b′∈{0,1}。如果b=b′，则敌手获胜。

以上游戏中，定义敌手获胜的优势为

定义1.1 在IND-CCA模型中，如果对于任意的多项式时间敌手，其获胜的优势都是可忽略的，则称该公钥加密方案是IND-CCA安全的。

通常认为IND-CCA安全模型是公钥加密算法的标准安全模型。根据敌手的攻击模式，可以定义一个比IND-CCA更弱的安全模型，称为选择明文攻击下的不可区分安全模型（Indistinguishability against Chosen-Plaintext Attack，IND-CPA）。在IND-CCA安全模型中，若敌手不允许询问密文解密，则称对应的安全模型为IND-CPA安全模型。

定义1.2 在IND-CPA模型中，如果对于任意的多项式时间敌手，其获胜的优势都是可忽略的，则称该公钥加密方案是IND-CPA安全的。