摘要

我们提出了第一个有效的基于身份的加密(IBE)方案，它是完全安全的，没有随机预言。我们首先提出了我们的IBE构造，并将我们的方案的安全性降低到BDH问题。此外，我们证明了我们的技术可以用来建立一个新的签名方案，在没有随机预言下计算DH问题是安全的。

介绍

基于身份的加密允许一方使用接收者的身份作为公钥来加密消息。使用身份作为公钥的避免了需要分发公钥证书。这在电子邮件等应用程序中非常有用，在这些应用程序中，接收者经常离线，并且在发送方加密消息时无法提供公钥证书。

Boneh和富兰克林[4]提出了第一个有效和安全的基于身份的加密方法。他们提出了一种使用有效可计算双线性映射的解决方案，在随机预言模型中被证明是安全的。从那时起，有一些方案被证明没有随机预言是安全的，但在一个较弱的安全模型中如可选择id模型[9,1]。最近，Boneh和Boyen[2]描述了一个方案，该方案在没有随机预言下被证明是完全安全的；这样一个方案的可能性在某个方面来说是一个开放的问题。然而，他们的方案效率太低，无法实际使用。

我们提出了第一个有效的基于身份的加密方案，在没有随机预言下它是完全安全的，。我们的方案的证明利用了由Boneh和Boyen[1]首先使用的代数方法，并且我们的方案的安全性简化为BDH假设。

此外，我们还证明了我们的IBE方案意味着一个安全的签名方案下的计算Diffie-Hellman假设下无需随机预言。以前在标准模型中安全的实际的签名方案依赖于Strong-RSA假设[12,11]或Strong-BDH假设[3]。

1.1 相关工作

Shamir首先提出了IBE加密的想法作为对研究界的挑战，但是，Boneh和Franklin的第一个安全有效的方案并没有出现直到很久以后。作者采用了一种新的方法来利用有效的可计算的双线性映射来实现他们的结果。

Canetti等人描述了一个较弱的基于身份的加密的安全模型，他们称之为选择性id模型。在选择性id模型中，对手必须在生成全局参数之前，首先声明它希望被挑战的哪个身份。作者提供了一个方案，在没有随机预言模型下选择性ID模型是安全的。Boneh和Boyen[1]通过描述一个在选择性id模型中安全的有效方案，改进了这一结果。

最后，Boneh和Boyen[2]描述了一个没有随机预言的完全安全的方案。然而，它们的结构效率太低，无法实际使用。

1.2 总结

我们将论文的其余部分组织如下。在第2节中，我们给出了我们对安全问题的定义。在第3节中，我们描述我们的复杂性假设。在第4节中，我们介绍了我们的IBE方案的构建，并在第5节中提供了安全证明。在第6节中，我们将讨论如何将我们的方案扩展到基于身份的分层加密方案，以及如何使用它来实现cca的安全性。我们将在第7节中讨论到一个签名方案的转换。最后，我们在第8节中进行总结。

2 安全性定义

在本节中，我们将介绍基于身份的加密中针对被动对手的语义安全的定义。这个定义最早是由Boneh和富兰克林·[4]描述的。考虑以下是对手所玩的游戏。这个游戏有四个不同的阶段：

3 复杂性假设

我们简要地回顾了关于具有有效可计算的双线性映射的群的事实。有关更多细节，请参考之前的文献[4]。

设G，g1是素数阶p的s群，g是g1的生成器。我们说G1有一个双线性映射，e：G×G→G1，如果以下两个条件成立，则变为G1映射是双线性的；对于所有的ab，我们有e(gagb)=e(gg)ab。这个映射是非简化的；我们必须有那个e(g，g)=1。

3.1 决定性双线性BDH假设

挑战者随机选择a，b，c，z∈Zp，然后翻转一个公平的两面硬币β。如果β=1，它输出元组(g，A=ga，B=gb，C=gc，Z=e(g，g)abc)。否则，如果β=为0，挑战者将输出元组(g，A=ga，B=gb、C=gc、Z=e(g，g)z)。然后，对手必须输出一个值为β的猜测β’。

敌手B有至少e的优势解决BDH问题

其中概率超过了随机选择的abcz和b消耗的随机位。我们称左边为PBDH，右边为RBDH。

定义2 如果没有t-时间的对手在解决上述博弈中至少有优势，则决策(t，)-BDH假设成立。

3.2 计算DH问题假设

挑战者随机选择a，b∈Zp和输出(g，a=ga，b=gb)。然后，对手试图输出输出gab∈G。一个对手，B，至少有一个优势，如果

其中的概率超过了随机选择的a，b和β所消耗的随机位。

定义3 如果没有t时间的对手在求解上述博弈时至少有优势，则计算(t，)-DH假设成立。

4 构造

我们的建设可以看作是对Boneh-Boyen[1]方案的修改。我们首先提出我们的构造，然后描述它与Boneh-Boyen方案的关系。

设G是一个素数阶群，p，在G1中存在一个有效可计算的双线性映射。另外，设e：G×G→G1表示双线性映射，g为对应的生成元。群的大小由安全参数决定。标识将被表示为长度为n的比特串，这是一个与p无关的单独参数。我们也可以让身份标识是任意长度的比特串，n是一个抗碰撞的哈希函数H：{0,1}∗→{0,1}n的输出长度。我们的构造如下：

设置：

系统参数的生成方法如下。随机选择一个秘密的α∈Zp。我们选择一个随机生成元，g∈G，并设置值g1=gα并在G中随机选择g2.此外，当选择随机值u’∈G和随机n长度的向量U=（ui），其元素是从G中随机选择 的。公开的公共参数g，g1，g2，u’和U。主秘密是g2α。

密钥生成：

设v是一个表示标识的n比特的字符串，vi表示v的第i个比特，V⊆{1，...，n}是vi=1的所有i的集合。(也就是说，v是其比特字符串v被设置为1的索引集。)标识v的私钥生成如下。首先，选择一个随机的r∈Zp。然后将私钥构造为：

4.1 效率

如果e(g1，g2)的值被缓存，那么加密在G中平均需要n/2(最多n)群运算，G需要两个求幂运算，G1需要一个求幂运算和一个G1中的群操作。解密需要两个双线性映射计算，一个在G1中的群操作，g1一个逆运算。

4.2 和Boneh-Boyen的相似处

我们的构造是对Boneh和Boyen的[1]的修改，对于一个身份标识v，我们计算，而在他们的方案中，它们计算，其中v被解释为一个整数。(从技术上讲，我们指的是当只使用了一个层级时BonehBonen-Boyen[1]中提出的第一个方案。虽然，我们的方案可以以类似的方式扩展为一个层次化方案。)在下一节中，我们将展示，值得注意的是，这个小的修改是使方案完全安全所需要的全部。

5 安全性

定理1：

我们的IBE方案(t，q，)是安全的，假设决策(t+O(−2ln（−1）λ−1ln（λ−1）)，32(n+1)q)BDH假设成立，其中λ=1 8(n+1)q。

证明：

假设存在一个(t，q，)对手，a来反对我们的方案。我们构建了一个模拟器B来玩决策BDH游戏。模拟器将接受BDH挑战(g，A=ga，B=gb，C=gc，Z)，并输出一个猜测，β，，关于挑战是否为BDH元组。模拟器将运行A，并执行以下步骤。

5.1 模拟者描述

模拟器首先设置一个整数m=4q，然后在0和n之间均匀随机选择一个整数k。然后选择一个随机的n长向量，−→x=(xi)，其中−→x的元素从0和m−1之间的整数中均匀随机选择，一个值，x，在0和m−1之间均匀随机选择。设X∗表示对(X，−→x)另外，模拟器选择一个随机的y∈Zp和一个n长度向量−→y=(yi)，其中−→y的元素在Zp中随机选择的。这些值都保存在模拟器的内部。