標準模型下抗持續泄漏的基于身份加密方案

謝 鳴

(淮北師范大學 網絡與信息管理中心，安徽 淮北 235000)

為解決傳統公鑰密碼系統中的證書管理問題，Shamir[1]于1984年提出了基于身份加密(Identity-based Encryption，簡稱IBE)的思想，其中用戶的身份是其公鑰，而用戶的私鑰則由私鑰生成器(Private Key Generator，簡稱PKG)產生。近年來，已經提出了許多有效的IBE方案[2-5]。但在實際生活中，大多數在理想模型中被證明是安全的加密方案無法抵抗由側信道攻擊引起的密鑰泄漏。為形式化側信道攻擊，密碼研究人員開始研究泄漏模型，特別是持續泄漏模型[6]，在該模型中，敵手能持續獲取方案的秘密內部狀態信息。抗密鑰泄漏的加密方案最近引起了很多關注。李繼國[7]等人針對持續泄漏模型提出了抗持續泄漏的基于身份廣播加密方案，并基于雙重系統加密技術證明方案是安全的。周彥偉等人[8]給出了一種新的能抵抗持續泄漏的IBE方案，在選擇身份安全模型中證明了該方案的安全性。

許多抗泄漏IBE方案只能抵抗選擇明文攻擊(Chosen Plaintext Attack，簡稱CPA)。根據基于身份的密鑰封裝機制(Identity-based Key Encapsulation Mechanism，簡稱IB-KEM)，我們提出了一種抗持續泄漏的IBE方案，并證明該方案在標準模型中能抵抗選擇密文攻擊(Chosen Ciphertext Attack，簡稱CCA)。該方案中使用了強提取器將封裝的對稱密鑰隨機化，并使用允許泄漏的封裝對稱密鑰對消息進行加密。同時該IBE方案提供了一個私鑰更新算法來容忍持續泄漏。

1 預備知識

根據定義2以及Goldreich-Levin定理，針對Goldreich-Levin核心謂詞f:GT×{0,1}μ→{0,1}，其中μ∈N，有如下引理。

引理1：令A,B,C∈G,u∈{0,1}μ,K=f(T,u)，令K'∈{0,1}是隨機選取的。假設存在一個PPT算法B以不可忽略的優勢區分分布Δ=(D,K,u)和Δrand=(D,K',u)，則存在一個PPT算法在輸入D=(g,A,B,C)前提下，以不可忽略的優勢計算出T，從而攻破CBDH問題。

定義3：最小熵 一個隨機變量X的最小熵是H∞(X)=-log(maxxP[X=x])。

2 抗持續泄漏IBE方案框架及安全模型

2.1 抗持續泄漏IBE方案框架

該框架包含以下五個算法，其中增加了UpdateSK算法來更新私鑰，具體內容如下。

初始化算法Setup：輸入安全參數1λ(λ∈N)，產生主公鑰mpk和主私鑰msk。

私鑰生成算法KeyGen：輸入mpk，msk以及身份ID，輸出私鑰skID。

加密算法Enc：輸入mpk，ID以及消息M，返回一個密文C。

解密算法Dec：輸入skID和C，返回M或者終止符⊥。

2.2 抗持續泄漏IBE安全模型

參照文獻[6-8]，形式化定義了一個IBE持續泄漏安全模型，通過游戲CL-sID-CCA(Continual Leakage，Selective-Identity and Adaptively Chosen Ciphertext Attack)來描述我們的IBE方案能抵抗選擇身份、持續泄漏和自適應選擇密文攻擊。挑戰者Ch創建一個列表Lsk以存儲形式為(ID,skID)的元組，Lsk在游戲初始化時為空。

初始化階段：敵手A把身份ID*發送給挑戰者Ch。

啟動階段：挑戰者運行Setup算法并返回mpk給A。

第一階段：敵手A能自適應地進行以下詢問。

私鑰詢問：針對身份ID(ID≠ID*)的私鑰詢問，挑戰者在列表Lsk中查找元組(ID,skID)。如果不存在，Ch運行KeyGen算法并輸出私鑰skID，并把(ID,skID)添加到列表Lsk中。

泄漏詢問：Ch創建一個包含元組形式為(ID,K,cnt)的列表Lleak，其中K表示用于加密消息的對稱密鑰，cnt∈N是一個計數器。Lleak在游戲的初始化階段為空。Ch從Lleak中查找(ID,K,cnt)，若其不存在，Ch把(ID,K,0)加入列表Lleak中。若該元組存在，Ch判斷是否cnt+li≤l，其中i∈N。若判斷為假，則輸出⊥。否則，對應的(ID,K,cnt)中設置cnt←cnt+li并返回fi(K)，其中fi:GT→{0,1}li為泄漏函數。

解密詢問：給定ID，Ch運行KeyGen算法并輸出私鑰skID。Ch運行Dec算法，使用skID解密密文C，并把明文發送給A。

挑戰階段：A選取兩個同樣尺寸的消息M0，M1發送給Ch。Ch隨機選擇一個值β∈{0,1}，加密消息Mβ并返回挑戰密文C*=Enc(params,mpk,Mβ,ID*)給A。

第二階段：A繼續做與第一階段同樣的詢問，但有一個限制，A不允許對(ID*,C*)進行解密詢問。

猜測：A返回猜測β'∈{0,1}。如果β'=β則稱A贏得了該游戲。

3 抗持續泄漏IBE方案

下面提出一種新型的抗持續泄漏IBE方案，我們使用強提取器技術以及n-bits基于身份密鑰封裝機制(IB-KEM)[9]來構造方案。

解密正確性驗證如下：

4 安全性證明

定理1若CBDH問題是困難的，則提出的方案在敵手A攻擊下是CL-sID-CCA安全的。

游戲3：游戲3和游戲2除了這種情況(K*∈{0,1}nv是隨機選擇的，其中n,v∈N)之外都相同。K'*是均勻隨機的值。由于K*和K'*均是隨機選擇的，故可得Pr[E3]=1/2。

基于CBDH問題，可以推出|Pr[E2]-Pr[E3]|≤negl(λ)。該結論可以通過混合論證推出。首先定義一系列游戲：游戲(0),…,游戲(n)，且游戲(0)和游戲2相同，游戲(n)和游戲3相同。下面判定基于CBDH問題游戲(i)與游戲(i-1)是不可區分的(其中i∈[1,n])。由于游戲(0)與游戲2相同，則對于i(從1到n)，第一個K*的iv比特在游戲(i)中設置成隨機的，剩下的則和游戲(i-1)中的相同。因此游戲(n)和游戲3相同。令Wi表示在游戲(i)中敵手A輸出β'使得β'=β的情況。假設|Pr[W0]-Pr[Wn]|=1/poly'(λ)(其中poly'(·)表示一個多項式函數)，即敵手A在游戲(0)的優勢(該優勢與在游戲(n)中的一致)是不可忽略的，則一定存在一個值i使得|Pr[Wi-1]-Pr[Wi]|=1/poly(λ)成立。

假設|Pr[W0]-Pr[Wn]|=1/poly'(λ)成立，下面基于CBDH問題構造一個算法B用來區分在引理1中的Δ和Δrand。B輸入挑戰Λ=(D,R,u)(其中R或者是一個{0,1}v中的隨機數或者是一個由f(T,u)輸出的v比特串)，則算法B猜測下標值j∈[1,n]使得|Pr[Wj-1]-Pr[Wj]|=1/poly(λ)的概率至少是1/n，且與敵手A做如下交互。

初始化階段：敵手A發送挑戰身份ID*。

第一階段：下列諭言詢問是敵手A進行的自適應詢問。

泄漏詢問：B創建一個包含元組形式為(ID,K,cnt)的列表Lleak，其中K表示用于加密消息的對稱密鑰，cnt∈N是一個計數器。Lleak在游戲的初始化階段為空。B從Lleak中查找(ID,K,cnt)，若其不存在，B把(ID,K,0)加入列表Lleak中。若該元組存在，B判斷是否cnt+li≤l，其中i∈N。若判斷為假，則輸出⊥。否則，對應的(ID,K,cnt)中設置cnt←cnt+li并返回fi(K)，其中fi:GT→{0,1}li為泄漏函數。

解密詢問：已知〈ID,Ci,1,Ci,2,Ci,3,C4,C5〉，B做如下操作：如果IDID*，B運行KeyGen算法生成私鑰skID，并運行Dec算法使用skID解密密文。

第二階段：A持續地進行與第一階段相同的詢問，但A不能對(ID*,C*)進行解密詢問。

結語

本文給出了IBE方案的形式化定義和安全模型，構造了一個能抵抗持續泄漏的IBE方案，該方案在標準模型中是CCA安全的。在證明過程中，將IBE方案的安全性規約到計算雙線性Diffie-Hellman困難問題。抗泄漏的密碼學方案設計是一個新的研究方向。我們將進一步研究某些具有更強抗泄漏性能的IBE方案，如隨機數泄漏，事后泄漏等；另外，基于格困難問題等構造安全的IBE方案也是一個值得研究的方向。