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安全的。