为了清楚地描述加密方案的安全性概念，密码学中经常会提到一个交互游戏.游戏有两个参与者，一个称为挑战者，另一个是攻击者.挑战者作为加密方案的所有者建立系统，攻击者对系统发起挑战，挑战者接受攻击者的挑战.

一个公钥密码方案的安全性概念可以由弱到强分为选择明文攻击安全(简称CPA安全)，非适应性选择密文攻击安全(简称CCA1)以及适应性选择密文攻击安全(简称CCA2)3个级别.若非特别说明，下文中提到CCA安全均指CCA2安全.

下面介绍基于身份的公钥密码体制的形式化定义及其安全模型.基于身份的加密方案的安全性定义最早由文献[6]提出，我们这里采用文献[7]中更为简洁的定义.

一个基于身份的加密方案IBE=(Setup，KeyD，Enc，Dec)由4个多项式时间算法构成.

Setup(k)算法中可信机构PKG输入安全参数k，输出一个二元组(PK，msk).其中PK是主公钥，msk是主私钥. PKG公开PK，保密msk.记为(PK，msk)←Setup(1^k).

KeyD(ID，msk)算法中PKG收到用户ID后，为ID分发私钥SK_ID，记为SK_ID←KeyD_msk(ID).

Enc(PK，ID，M)算法中信息发送方用ID加密信息M，输出密文C，记为C←Enc_PK(ID，M).

Dec(ID，SK_ID，C)算法中拥有身份ID的用户用私钥SK_ID解密，记为M←Dec_SKID(ID，C).

IBE的选择身份安全性定义可以通过以下挑战者$\mathscr{C}$和攻击者$\mathscr{A}$之间的游戏来描述，对于该安全性的定义具体可见文献[6-8].攻击者$\mathscr{A}$在选择身份CPA安全游戏中的成功优势^[6]定义为Adv_{$\mathscr{A}$，IBE}^IND-ID-CPA(k)=$\left| {\mathit{Pr}_\mathscr{A}^{IBE}\left[{b = b'} \right] - \frac{1}{2}} \right|$.

如果对任何多项式时间的攻击者$\mathscr{A}$，存在一个可忽略的函数negl(k)，使得Adv_{$\mathscr{A}$，IBE}^IND-ID-CPA(k)≤negl(k)，那么就称这个基于身份的加密方案在选择身份攻击下具有不可区分性，或者称为选择身份CPA安全.基于身份的加密方案的CCA安全定义与CPA安全定义最大的不同是攻击者除了可以询问私钥，还能对除了挑战密文之外的密文做解密询问.

接下来简单介绍基于身份的门限密码(简记为TIBE)的形式化定义及其安全模型.

一个基于身份的门限加密方案包括以下7个算法：

Setup(n，t，k)算法中输入解密服务器个数n，门限值t，安全参数k，输出一个三元组(PK，VK，K_msk)，其中PK是系统参数，VK是验证密钥. K_msk=(msk₁，msk₂，…，msk_n)是n个主密钥份额组成的向量，解密服务器i拥有(i，msk_i)用于获得私钥份额.

ShareKeyGen(PK，i，msk_i，ID)算法中输入系统参数PK，身份ID以及主密钥份额(i，msk_i)，输出ID的第i个解密私钥份额dk_i=(i，$\mathop {dk}\limits^ \wedge $_i).

ShareVerify(PK，VK，ID，dk_i)算法中验证dk_i是否是身份ID的有效解密份额，输出“Valid”或者“Invalid”.

Combine(PK，VK，ID，{dk₁，dk₂，…，dk_t})输出身份ID对应的私钥SK_ID或者“⊥”.

Encrypt(PK，ID，M)算法中输入系统参数PK，身份ID和信息M，输出密文C.

ValidateCT(PK，ID，C)算法验证C是否为有效密文，输出“Valid”或者“Invalid”.

Decrypt(PK，ID，SK_ID，C)算法解密输出明文M或者“⊥”.

TIBE的安全性需要考虑选择身份攻击CPA安全以及密钥生成一致性两方面.可以用两个游戏来描述：选择身份攻击CPA安全游戏和密钥生成一致性游戏^[5].

在选择身份攻击CPA安全游戏中攻击者的优势定义为Adv_{$\mathscr{A}$，TIBE}^IND-ID-CPA(k)=$\left| {\mathit{Pr}\left[{b = b'} \right] -\frac{1}{2}} \right|$；密钥生成一致性游戏中攻击者的优势定义为Adv_{$\mathscr{A}$，TIBE}^CD-ID(k)=Pr[攻击者获胜].

如果对任何多项式时间的攻击者$\mathscr{A}$以及任意的n和t(0＜t≤n)，存在可忽略的函数negl(k)，使得Adv_{$\mathscr{A}$，TIBE}^IND-ID-CPA(k)≤negl(k)和Adv_{$\mathscr{A}$，TIBE}^CD-ID(k)≤negl(k)都成立，那么就说TIBE方案是选择身份攻击CPA安全的.

目前CCA2被认为是公钥加密方案的安全性概念中最强的，为了实现加密方案的CCA安全，文献[9]提出一个将CPA安全的加密方案转化成CCA安全的加密方案的简单方法，转化方法如下：

设∏：=($\mathscr{K}$，$\mathscr{E}$，$\mathscr{D}$)是一个CPA安全的加密方案，H：{0，1}^k$\xrightarrow{{}}${0，1}^l是一个Hash函数.

1) $\overline{\mathscr{K}}$(1^k)：= $\mathscr{K}$(1^k)

2) $\overline{\mathscr{E}}$_pk^H：{0，1}^k-k₀×{0，1}^k₀$\xrightarrow{{}}${0，1}^*，定义为：$\overline{\mathscr{E}}$_pk^H(x，r)：=$\mathscr{E}$_pk((x||r)，H(x||r))，其中x∈{0，1}^k-k₀且r∈{0，1}^k₀.

3) $\overline{\mathscr{D}}$_sk^H(y)：{0，1}$\xrightarrow{{}}$^* {0，1}^k-k₀∪{null}定义如下

其中：[$\mathscr{D}$_sk(y)]^k-k₀指的是$\mathscr{D}$_sk(y)的前(k-k₀)比特，“*”指存在$\mathscr{D}$_sk(y)使得y= $\mathscr{E}$_pk($\mathscr{D}$_sk(y)，H($\mathscr{D}$_sk(y))).文献[9]证明了通过这样的转化，CPA安全的解密方案确实能达到CCA安全，得到了如下的CCA安全转化定理.

定理1 假设∏=($\mathscr{K}$，$\mathscr{E}$，$\mathscr{D}$)是一个CPA安全的加密方案，则$\overline{\Pi }$=($\overline{\mathscr{K}}$，$\overline{\mathscr{E}}$，$\overline{\mathscr{D}}$)是随机预言器模型下CCA2安全的加密方案.

下面将上述转化方法应用到一个选择身份攻击CPA安全的IBE中得到一个随机预言器模型下CCA安全的IBE.

假设∏=(Setup，KeyD，$\mathscr{E}$，$\mathscr{D}$)是一个选择身份CPA安全的IBE方案，H：{0，1}^k+k₀$\xrightarrow{{}}${0，1}^l是一个安全Hash函数，下面构造∏′=(Setup，KeyD，Enc，Dec).

Setup(k)算法中可信机构PKG输入安全参数k，输出一个二元组(PK，msk)，其中PK是主公钥，msk是主私钥. PKG公开PK，保密msk，记为(PK，msk)←Setup(1^k).

KeyD(ID，msk)算法中PKG在收到身份ID后，为身份ID分发私钥SK_ID，记为SK_ID←KeyD_msk(ID).

Enc(PK，ID，M)算法中对于信息m∈{0，1}^k，随机选择r∈{0，1}^k₀，同样用主公钥和身份ID加密，记为C←$\overline{\mathscr{E}}$_PK，ID^H(m，r)= $\mathscr{E}$_PK，ID((m||r)，H(m||r))=(y₁，y₂).

Dec(ID，SK_ID，C)算法中拥有身份ID的用户先检查密文是否有效.若有效，用私钥SK_ID解密，记为m←$\overline{\mathscr{D}}$_SKID^H(ID，C)=[D_SKID(ID，C)]^k，其中[D_SKID(ID，C)]^k表示D_SKID(ID，C)的前k个比特.否则，拒绝解密，并输出“null”.

定理1保证了∏′是一个CCA安全的IBE.

下面构造一个CCA安全的TIBE方案实例.

设BDH假设成立，H：{0，1}^k→$\mathbb{Z}$_p是一个安全的Hash函数，再假设e：$\mathbb{G}$×$\mathbb{G}$→$\mathbb{G}$₁是一个双线性映射^[10]，其中群$\mathbb{G}$₁中元素的二进制长度不超过k.

Setup(n，t，k)算法设$\mathbb{G}$是p阶群，在$\mathbb{G}$中随机选择生成元g，g₂，h₁以及一个t-1次随机多项式f∈$\mathbb{Z}$_p[X].令α=f(0)，g₁=g^α，msk_i=g₂^f(i).服务器i的主密钥份额为(i，msk_i).设置系统参数PK=($\mathbb{G}$，g，g₁，g₂，h₁)，主密钥份额集K_msk=(msk₁，…，msk_n)，公开的验证密钥为VK=(g^f(1)，…，g^f(n))=(u₁，…，u_n).

ShareKeyGen(PK，i，msk_i，ID)算法随机选r∈$\mathbb{Z}$_p，计算w_i，0=msk_i·(g₁^IDh₁)^r，w_i，1=g^r，然后输出身份ID的第i个会话私钥份额dk_i=(i，(w_i，0，w_i，1)).

ShareVerify(PK，VK，ID，dk_i)算法中为了验证dk_i是身份ID的有效会话私钥份额，判断e(u_i，g₂)·e(g₁^IDh₁，w_i，1)=e(g，w_i，0)是否成立，若成立，输出“Valid”；否则，输出“Invalid”.

Combine(PK，VK，ID，{dk₁，dk₂，…，dk_t})算法中如果上一步验证未通过，输出“⊥”并退出，否则选择λ₁，…，λ_t∈$\mathbb{Z}$_p，使得α=f(0)$\sum\limits_{i=1}^{t}{{{\lambda }_{i}}f\left( i \right)}$，然后计算w₀=$\prod\limits_{i=1}^{t}{{}}$w_i，0^λ_i，w₁=$\prod\limits_{i=1}^{t}{{}}$w_i，1^λ_i，输出身份ID对应的会话私钥d_ID=(w₀，w₁).

Encrypt(PK，ID，M)算法中为了加密M∈{0，1}^k-k₀，进行以下两步

(a) 随机选v∈{0，1}^k₀，令s=H(M||v)；

(b) 计算并输出密文C=(y₁，y₂，y₃)=(e(g₁，g₂)^s$\oplus $(M||v)，g^s，g₁^s·IDh₁^s).

ValidateCT(PK，ID，C)算法中为了验证C=(y₁，y₂，y₃)是否为有效密文，判断e(y₂，g₁^IDh₁)=e(y₃，g)是否成立，若成立，输出“Valid”；否则，输出“Invalid”.

Decrypt(PK，ID，d_ID，C)算法中如果密钥有效性或者密文有效性检验有一个通不过，那么拒绝解密；否则，输出明文M′= ${{\left[{{y}_{1}}\oplus \frac{e\left( {{y}_{2}}, {{w}_{0}} \right)}{e\left( {{y}_{3}}, {{w}_{1}} \right)} \right]}^{k-{{k}_{0}}}}$.

如果C=(y₁，y₂，y₃)是ID加密的有效密文，并且d_ID是ID的有效会话私钥，那么解密一定是正确的，因为(w₀，w₁)=(g₂^α(g₁^IDh₁)^r，g^r)，其中r=r(λ₁+…+λ_t).进一步，利用双线性性质就有

假设BDH问题是难解的，本文构造中所使用的文献[5]中的基于身份的门限方案已经被证明了是选择身份CPA安全的，按照文献[9]中的方法转化得到我们构造的基于身份的门限方案，于是结合定理1不难得到下面的定理.

定理2 假设BDH问题是难解的，那么上述构造得到的TIBE是CCA安全的.

本文利用文献[9]中提高安全性的方法，提出一个既能达到CCA安全，解密私钥份额的有效性又能公开验证的基于身份的门限加密方案(TIBE)，比文献[5, 7]中提高安全性的方法更加高效.因为已有文献中CPA安全到CCA安全的转化需要在加密时额外加入一个一次签名，导致传输密文长度增大(密文多了验证密钥和签名两部分).在传输效率上本文的构造比之前的方法至少提高了两倍.