何能强, 李 叶, 张 华

1国家计算机网络应急技术处理协调中心, 北京 中国 100029

2北京邮电大学网络与交换技术国家重点实验室, 北京 中国 100876

1 背景

为了移除公钥基础设施(Public key infrastructure,PKI)系统中复杂的证书认证和管理过程, Shamir[1]在1984年首次提出了基于身份的加密(Identity- Based Encryption, IBE)。用户的公钥是一个任意长度字符串,如一个电子邮件地址、电话号码或其他标识符, 代表了用户在IBE系统中的身份。当新用户想要加入IBE系统时, 其他用户可与新用户安全通信而不需要认证其证书。基于身份的加密系统工作原理如图 1所示, 私钥生成中心 PKG为 Alice生成私钥, Bob用Alice的邮箱地址作为公钥加密邮件发送给Alice。在PKG生成私钥的过程中就存在着密钥托管问题。

图1 基于身份的加密系统工作原理[1]Figure 1 The working principle of the identity-based encryption system[1]

Boneh和Franklin在2001年提出了BF-IBE[2]方案, 他们首次使用椭圆曲线上的双线性对来实现IBE系统。在他们方案的基础上, Sakai和Kasahara于2003年提出了SK-IBE[3]方案。与BF-IBE方案相比, SK-IBE方案并不适用于诸如门限密码系统[4]和分层IBE系统[5]等许多应用场景。近年来, BF-IBE方案得到了越来越多的关注。

Even, Goldreich和Micali[6]首先提出了在线/离线技术。在他们的数字签名方案中, 签名步骤分为在线和离线两个阶段。在确定签名消息之前运行离线阶段, 在消息被确定之后执行在线阶段。与在线阶段相比, 离线阶段需要更大的计算量(双线性对运算), 在线阶段中应尽可能地减少这样的运算。通过这种方式, 在线阶段只需要少量的计算就可以快速完成。这种方案适用于一些具有低计算能力的设备, 如传感器或移动终端。对于这些设备而言, 大量复杂的计算可以在离线阶段完成。

2008年, Guo等人[7]首次将在线/离线技术引入到 IBE系统方案当中, 并提出了两种基于身份的在线/离线加密(Identity-Based Online/Offline Encryption,IBOOE)算法。在他们的方案中, 大量繁重的计算将在确定具体加密消息和接收方身份之前的离线阶段完成。在确定加密消息和接收方身份后, 在线阶段只需少量计算。由于密文空间太大, Guo等人提出的这两种在线/离线的IBE方案并不适用于轻量级设备。

基于Boneh等人[8]和 Gentry[9]的 IBE方案构造,Guo等人[7]提出的两个 IBOOE方案被证明是在无随机预言机下的抗选择密文攻击 (Chosen Ciphertext Attack, CCA)安全。后来, Liu等人[10]提出了一个更为高效的 IBOOE 方案, 并在随机预言机模型下证明该方案能达到CCA安全。随后, Selvi等人[11]指出了Liu等人[10]方案中存在的问题, 在他们的 CCA安全证明当中存在一个明显的缺陷。与此同时, 在文献[12]中, Selvi等人提出了一个更为高效的可达到CCA安全的在线/离线IBE方案。2010年, 针对无线传感器网络系统, Chu等人[13]提出了一种新型的IBOOE方案, 在离线存储步骤中, 他们移除了GT中的元素。在那之后, 许多文献[14-18]提出了更为优化的基于身份的在线/离线加密方案。

但是在上述的IBOOE方案中, 由于PKG可以生成任意用户的私钥, 且可以用它的主密钥解密任意的密文, 系统存在着密钥托管的问题, 当 PKG被攻破时, 该 IBOOE系统中所有的用户私钥都将泄露,致使整个系统的数据面临极大的安全挑战。与此同时, 当用户对 PKG产生不信任时, 系统也将面临崩溃的状态。

本文为了解决IBOOE方案中密钥托管问题, 提出了一种新型高效的基于身份的在线/离线加密方案。在IBOOE系统建立之后, 用户也可根据对所属PKG的信任程度, 选择是否使用公用OKG来解决密钥托管问题, 而且不需要PKG重新初始化。另外, 该方案可扩展支持云外包解密。方案旨在为低计算能力的电子设备如传感器或移动终端等提供有效的IBOOE方案。大部分的加密运算可在离线阶段完成,而大部分的解密运算又可外包给云完成。除此之外,与其它现行IBOOE方案不同, 本方案的密钥生成算法也可采用在线/离线技术来提高 PKG的密钥生成效率。针对用户数量庞大的IBE系统, 可通过这种方式减轻PKG的计算压力。本文的IBOOE方案在随机预言机模型下满足了IND-ID-CPA安全性。方案减少了用户在离线阶段时所需的计算量, 同时, 方案在线阶段的计算量也足够小, 可以达到IBOOE方案算法的目标。在存储开销和用户通信代价方面, 本文方案也有着明显的提升。

论文其余部分的安排如下： 第二节给出了本文的相关工作。第三节为预备知识的介绍。方案的系统模型与具体方案的构造在第四节和第五节中给出。第六节给出了方案的安全性证明和效率分析。最后, 第七节为本文的结束语。

2 相关工作

自从Boneh和Franklin[2]提出安全高效的使用椭圆曲线上双线性对的基于身份的加密方案之后, 许多 IBE方案[8,9,19-24]和相关变形方案[25]相继而出。现在, IBE方案可以通过素数阶的双线性对[2,3,8,9,19,26]、合数阶的双线性对[23,24]、或者不使用双线性对[20-22,27]来构造。在相同安全性的情况下, 因为椭圆曲线密码学中群的表示较短, 所以在这些构造当中, 基于椭圆曲线的 IBE方案在计算和实现方面更加高效。例如, 一个512位长度的椭圆曲线群可以实现256位的安全性, 但相同安全性的 RSA模数长度至少需要15360位[28]。但是对于所有基于双线性对运算的IBE方案而言, 加密算法不仅需要椭圆曲线群中的点乘运算, 而且还需要乘法群中的指数运算。

与传统基于双线性对运算的IBE方案相比, 为了可以更有效地运行加密算法, 之前的文献提出了两种不同的IBE方案(基于身份的在线/离线加密方案和使用陷门离散对数群构造的基于身份的加密方案)。

文献[27]提出了一种使用陷门离散对数(Trapdoor Discrete Log)群构造的IBE方案。陷门离线对数群是一个在特定的椭圆曲线上或者是一个在ℤN上定义的最大循环子群, 其中N是一个合数。给定任意两个群元素g和h, 如果还给出了陷门信息,则求解x

h=g的离散对数x存在多项式时间算法, 否则, 求解x最有效率的算法是 Pollard rho攻击。Paterson和Srinivasan[27]研究了如何利用这样一个陷门离散对数群构造 IBE方案。由于只使用了一种类型的群上的运算(例如G1), 所以他们提出的 IBE方案在加密和解密计算效率方面是非常高效的。但是这种 IBE方案需要在特定的椭圆曲线上构造, 并且由于使用了陷门计算, 这将导致密钥生成算法的计算效率较低。对比其他基于双线性对运算的 IBE方案, 这种使用陷门离散对数群所构造的 IBE方案虽然可以在加密算法里去除GT中的指数运算, 但是需要使用更加复杂的哈希函数来构造, 所以在方案的实现过程中, 这将带来许多不便。

文献[7]和文献[11]提出了基于身份的在线/离线加密方案。在这种加密方案模型中, 消息发送方可以将加密算法分为离线和在线两个阶段。离线阶段中,在不明确接收方的身份前, 发送方可以完成尽量多的群运算。在明确接收方身份后的在线阶段, 加密算法只需要一些哈希、模乘和少量的群运算, 这种方案极大减少了确定接收方身份后的加密消息所需时间。IBOOE方案移除了大量在线阶段时的群运算, 在一定程度上减少了发送方在线计算的时间, 从而显着地节省了实现在线加密算法的硬件成本。

但是, 许多 IBOOE方案[14,16-21,29]存在密钥托管问题。在IBOOE系统中, 所有用户的私钥都由一个可信的PKG生成。在这些方案中, PKG是完全可信的, 但是当PKG进行恶意操作(例如倒卖用户私钥)时,第三方机构很难进行监督、取证和惩罚, 这对许多IBOOE系统的应用和实施构成了极大的安全威胁。

与此同时, 传统的 IBOOE方案只有一个 PKG,因此方案将面临如下的两个问题： (1)PKG需要花费一定的时间和成本并通过一个安全通道给用户传输和更新私钥, 特别是在具有庞大用户数量的大型网络中, PKG将成为该网络中性能的瓶颈。(2)PKG将成为网络攻击的首要目标。由于PKG中主密钥的存在, PKG可以生成任意用户的私钥, 一旦PKG被攻击成功或者当PKG是恶意时, 用户私钥的安全性将荡然无存。所以, 解决IBOOE系统中密钥托管的问题变得刻不容缓。

3 预备知识

3.1 符号定义

表1给出了本文所用的符号及其含义。

表1 符号定义Table 1 Definition of symbols

3.2 困难问题

定义 1.双线性映射. G是阶为素数p的(乘法)循环群, 生成元是g。GT是阶为素数p的(乘法)循环群。当该映射满足以下性质时, 称映射e：G×G→GT是双线性映射,

(1) 双线性： 对所有的u,v≠G和a, b≠, 满足e(ua,vb)=e(u,v)ab;

(2) 非退化性：e(g,g)≠1;

(3) 可计算性： 存在一个有效的算法对任何的u,v≠G, 可计算出e(u,v)。

基于文献[8,10]的Bilinear Diffie-Hellman Inver-sion(BDHI)假设如下：

假设1.l-BDHI假设. 设G是一个p阶循环群,g≠G是群的生成元并且则l-BDHI问题是：给定计算

没有一个有效的算法, 能在概率多项式时间内以不可忽略的优势解决l-BDHI问题。

假设2. 弱l-BDHI假设. 设g和h是群G的两个随机生成元, 在随机选择α。则两个弱l-BDHI问题是：

没有一个有效的算法, 能在概率多项式时间内以不可忽略的优势解决这两个弱l-BDHI问题。

4 无密钥托管的基于身份的在线/离线加密方案

4.1 方案的形式化定义

本文的IBOOE方案在用户选择使用公用外包密钥生成中心 OKG时, 包含以下七个算法： 系统初始化(Setup), OKG初始化(OKGSetup), 离线密钥生成(OffKeyGen), 在线密钥生成(OnKeyGen), 离线加密(OffEncrypt), 在线加密(OnEncrypt)和解密(Decrypt)。方案的系统框架如图2所示。

图2 无密钥托管问题的IBOOE方案系统框架Figure 2 The system framework of the IBOOE scheme without key escrow

4.2 方案的安全模型

基于文献[30], 本节定义了方案的安全模型。本文的方案可以满足IND-ID-CPA安全性, 允许敌手询问不能用于解密挑战密文的任意用户的私钥。本文方案是基于随机预言机模型证明的(随机预言机模型是指包括攻击者在内的所有协议的参与方, 都有对一个公共的随机预言机的访问权, 例如： 对一个输入x, 返回一个随机预言f(x)), 正式的安全模型定义如下：

(1) 初始化： 挑战者输入安全参数λ, 运行系统初始化算法(Setup), 将公共参数pp发给敌手A并保存主密钥msk。模拟器S运行 OKG初始化算法(OKGSetup), 将外包参数op发给敌手A并保存针对该IBOOE系统的外包主密钥omsk。这里假设PKG和OKG中至少有一个是未被攻破的。

-对被攻破的PKG(或者OKG), S将公共参数和主密钥(或者外包参数和外包主密钥)发送给A。

-对未被攻破的PKG(或者OKG), S将公共参数(或者外包参数)发送给A。

(2) 阶段1： 敌手A在多项式时间内可以对多个身份IDi发出对应的私钥查询模拟器S通过执行离线密钥生成(OffKeyGen)和在线密钥生成(OnKeyGen)算法产生对应身份的私钥并返回给A。

(3) 挑战： 一旦A决定阶段1完成, A将输出一个想要挑战的身份但身份不能在阶段1的私钥查询中出现过。S提前运行离线加密(OffEncrypt)算法生成离线密文Coff。敌手A提交两个等长的消息M0和M1, S投掷一个随机的硬币之后S运行在线加密(OnEncrypt)算法并返回挑战密文给A。

(4) 阶段2： 对更多的IDi重复阶段1的私钥查询,要求被查询身份满足

(5) 猜测： 敌手A输出一个对b的猜测A赢得游戏当且仅当b′=b。敌手A赢得游戏的优势为：

定义1. 一个IBOOE方案是IND-ID-CPA安全的,当且仅当不存在多项式有界的敌手能以不可忽略的优势赢得以上游戏。

5 一个新的安全无密钥托管的IBOOE方案

基于文献[8,10], 本节提出一个新的安全无密钥托管问题的基于身份的在线/离线加密方案, 并给出方案可外包解密的改进算法。该方案可适用于低计算能力的电子设备, 如传感器或移动终端等。加密和密钥生成算法中的大部分计算可在离线阶段完成,并且解密算法中的绝大部分计算可由用户安全地外包给云完成。这大大降低了用户端的计算压力。

5.1 方案构造

本方案7个算法具体构造如下所示：

系统输入安全参数λ, 系统参数生成如下： PKG选择一个阶为素数p的双线性群G, 其生成元为g。系统定义一个密码学中的哈希函数PKG随机选择两个指数则公共参数pp和主密钥msk为：

其中, 公共参数pp对系统中用户公开, 主密钥msk作为秘密由PKG安全保存。

OKG输入该系统的公共参数pp, OKG随机选择两个指数计算并公开针对该系统的外包参数op：

之后,Koff将由PKG安全保存。

之后,Ko′ff将由OKG安全保存。

消息发送方使用公共参数pp和外包参数op进行离线加密。发送方随机选择一个秘密值并计算发送方的离线密文为：

之后, 离线密文Coff将由发送方安全保存。

为了将消息M≠M发送给用户身份信息为ID≠{0,1}*的接收方, 消息发送方读取离线密文Coff并计算：

消息接收方收到密文CT后, 使用含自己身份的私钥dID解密：

在IBOOE方案中用户选择使用OKG的情况下,上述方案过程如图3所示。

图3 无密钥托管问题的IBOOE方案Figure 3 The IBOOE scheme without key escrow

图4 用户完全信任PKG时的IBOOE方案Figure 4 The IBOOE scheme when users fully trust PKG

在用户完全信任PKG不选择使用OKG的情况下, 上述方案移除与 OKG的所有相关项, 参与方为发送方、接收方和PKG, 方案具体过程如图4所示。

根据是否使用OKG时的算法比较, 我们可以看出在 IBOOE系统建立之后, 当用户选择使用公用OKG来解决密钥托管问题时, 针对系统中用户, 只需接收方重新获取解密私钥dID和发送方加密消息M时使用外包参数op即可, 而不需要 PKG重新初始化, 在一定程度上减轻了PKG的运算压力。

5.2 正确性验证

在IBOOE系统中用户选择使用OKG的情况下,接收方可以获得正确的明文。具体验证如下：

接收方可得

=M

在IBOOE方案中用户完全信任PKG不选择使用OKG的情况下, 接收方可以获得正确的明文。具体验证如下：

密文CT即为：

5.3 扩展方案

本节对提出的用户可选择公用外包密钥生成中心的IBOOE方案进行扩展, 使方案在保证安全性的同时支持云外包解密。即使外包的云服务器是半可信的(一方面完成自己的工作, 另一方面会受到来自内部或者外部的攻击, 还可能串通恶意用户窥探用户的文件内容, 获取非法信息), 该扩展方案同样可以保证用户的信息安全, 并且使得用户在解密阶段只需要进行一次指数运算和一次除法运算即可恢复出消息明文M。扩展方案更加适用于低计算能力的电子设备。

Setup、OKGSetup、OffKeyGen、OnKeyGen、OffEncrypt、OnEncrypt算法与5.1节中构造相同, 我们不再次赘述, 余下的算法描述如下。

(2)Transform( pp, CT, TK)接收方将密文CT和转化密钥TK发送给云端,云端通过计算：

接收方使用取回密钥RK, 密文CT和公共参数pp去验证和解密转化密文。如果T1≠C, 则输出⊥表示转化密文未通过验证。如果T1=C, 则接收方通过计算：

接收方得到消息明文M。

6 方案分析

6.1 方案的安全性证明

本节将证明本文构造的 IBOOE系统可以满足IND-ID-CPA安全性。证明中允许敌手可以询问任意用户的私钥dID, 只要被询问的用户私钥不能用于解密挑战密文。正式的安全性证明如下。

定理 1. 如果存在一个敌手A能以不可忽略的优势赢得4.2节中, 针对提出的IBOOE方案所构造的游戏, 则存在一个模拟器S能以不可忽略的优势攻破弱l-BDHI假设。

证明. 假设存在一个概率多项式时间的敌手A能以不可忽略的优势赢得本文4.2节中所描述的游戏。

(1) 初始化： 挑战者运行系统初始化()λ算法并设置问题实例其中或者GT中的一个随机群元素。PKG和OKG中至少有一个未被攻破, 也就是说对于主密钥msk和外包主密钥omsk至少有一个敌手A无法获得。

-对被攻破的PKG(或者OKG), 模拟器S随机选择。S同时发送(ξ,b)和并计算给敌手A。

-对未被攻破的PKG(或者OKG), 模拟器S随机选择并计算S发送给敌手A。

(2)阶段 1： 敌手A在多项式时间内对多个身份IDi发出对应的私钥查询q1,...,qm。如果 PKG(或者OKG)是被攻破的, A可以使用(ξ,b)计算出解密私钥组件。如果 PKG(或者 OKG)是未被攻破的, 敌手A进行自己身份ID的私钥查询, 模拟器S选取r1...r4为已知的随机值。解密私钥组件可分为两部分生成。

- PKG 从ℤp中随机选择r1,r2, 解密私钥组件可表示为

- OKG从ℤp中随机选择r3,r4, 解密私钥组件可表示为

如果敌手A进行非自己身份ID的私钥查询, 模拟器S选取r1...r4为av加上一些已知的随机值。解密私钥组件可分为两部分生成。

(3) 挑战： 敌手A决定结束阶段1私钥查询, 并输出一个它想要挑战的身份不能在阶段1的私钥查询中出现过。A提交两个等长消息M0和M1。模拟器S投掷一个随机的硬币b≠{0,1}, 建立并返回挑战密文如果如果T是中的一个随机群元素, 则

(4) 阶段2： 与阶段1相同, 对更多的IDi进行私钥查询, 但要求被查询身份满足

(5) 猜测： 敌手A最终输出一个对M的猜测M′。如果M′=M1,模拟器S猜测是一个元组并输出 1; 否则S猜测T是GT中的一个随机群元素并输出0。当T是一个元组, 模拟器S进行一个完美的仿真, 可得：当T是GT中的一个随机群元素, 敌手A获取不到任何有关于Mb的信息, 可得：

如果当敌手A能以不可忽略的优势攻破方案, 模拟器S就能以不可忽略的优势攻破弱l-BDHI假设。

表2 安全模型比较Table 2 The comparison of security model

安全模型比较如表 2所示。本文方案的安全性证明依靠于随机预言机模型。方案在弱l-BDHI假设下是IND-ID-CPA安全的。随机预言机是一种启发式的证明模型, 该模型中的分析证明比其它模型更加有效, 并且在安全性方面也普遍被人们接受。在特定的情况下, 方案的效率比安全级别更为重要。因此,本文的安全性证明使用了随机预言机模型。同时, 相比于其他方案, 本文所提出的方案还可支持云外包解密功能, 对于消息的接收方, 大部分的解密计算可以安全地外包给云完成。极大程度地减少了接收方解密的计算代价。

6.2 方案的效率分析

本节在存储开销和计算复杂度方面对所提方案进行了效率分析。在本方案的OnEncrypt算法中, 用户首先读取离线阶段时计算的离线密文Coff, 然后再进行少量的计算便可完成用户的在线加密过程, 在此过程中, 并不涉及任何双线性对运算。相比于之前的 BF-IBE[2]方案, 本文方案明显降低用户的在线计算量。

E表示在G或GT中指数运算的时间,ME表示在G中的多点乘运算时间,Te表示双线性对运算的时间,mc表示在中模运算的时间,M表示在GT中乘法运算的时间,SE表示对称密钥加密的时间。n表示信息空间大小, S表示一个强签名[7], 以及k表示对称密钥加密ε的块大小[13]。本方案所构造的IBOOE系统在计算效率、存储开销以及通信代价方面与其他方案相比具有一定优势。

表3 计算复杂度比较Table 3 The comparison of computation complexity

表 3在计算复杂度方面将本文方案与其他相关的IBOOE方案在离线计算量和在线计算量方面进行了比较。上述方案均在双线性乘法群中实现。通过对离线计算量的比较可得知, 本文所提出的方案在离线阶段时的计算量略低于上述方案, 均在设备可计算范畴内, 满足IBOOE方案算法的要求。再从在线阶段要求轻量计算的角度来看, 本文方案可以实现IBOOE方案算法的目标。在线阶段时, 本文方案的计算复杂度足够小, 可应用于许多低计算能力的电子设备, 如传感器或移动终端。同时, 本文将在线/离线技术应用到密钥生成算法, 通过这种方式,PKG可以比其他现有的IBOOE方案更快速地生成用户私钥, 当用户数量较为庞大时, 可在一定程度上减轻PKG的计算压力。

存储开销比较如表4所示。在本文的IBOOE方案中, 消息发送方的离线存储开销表示为Coff,PKG所需离线存储开销表示为Koff。方案中发送方和 PKG的存储开销分别为和就离线存储开销方面, 本文的方案展现出了很好的性能。尽管文献[13]的离线存储开销略低于本文方案, 但是其方案引入了对称密钥加密算法(例如： DES、3DES、IDEA、FEAL、BLOWFISH等), 发送方与接收方必须都要获得密钥并保持密钥的安全, 这会产生用户密钥管理的问题。

表4 存储开销比较Table 4 The comparison of storage overhead

因为方案中发送方与接收方在信道传输的为密文CT, 所以密文CT所占空间大小可以被看作用户之间的通信代价。因此, 本方案用户之间的通信代价为4本方案密文CT所占空间更小,这在一定程度上降低了传输密文时所需的通信代价(带宽)。

7 结束语

本文利用椭圆曲线上的双线性对构造了一个安全有效的基于身份的在线/离线加密方案。方案可扩展支持云外包解密, 并且应用可选择公用外包密钥生成中心, 使得用户也可根据对所属PKG的信任程度, 选择是否使用公用OKG来解决密钥托管问题而不需要PKG重新初始化。通过安全和效率分析, 与其他现有的IBOOE研究成果相比, 本文方案是安全和高效的。本文方案使用了椭圆曲线上的双线性对技术, 但是影响双线性对快速实现的因素有很多,所以在提高方案的计算速度方面还有着很大的空间,同时方案在安全性等方面也可继续提升。

致 谢 本文中方案的提出是在北京邮电大学网络技术研究院网络安全中心(国家重点实验室)的大力支持和帮助下完成的, 在此向该中心表示衷心的感谢。