摘要

基于身份的加密(IBE)是一种特殊的非对称加密方法，其中公钥可以是任意标识符，并且对应的私钥是由标识符和系统主密钥绑定生成的。2003年，Sakai和Kasahara提出了一项新的IBE方案，具有提高性能的可能。然而，据我们所知，他们方案的安全性并没有被正确的验证过。这项工作旨在建立Sakai-Kasahara IBE方案的安全性提供可靠的依据。在本文中，我们首先提出了一个有效的IBE方案，采用了一个简单版本的Sakai-Kasahara方案和Fujisaki-Okamoto变换，我们称之为SK-IBE。然后我们证明SK-IBE在随机预言模型中基于合理有效探索可靠的假设具有选择密文安全。

1 介绍

Shamir在1984年[33]首先制定了基于身份的密码学(IBC)的概念，公钥和私钥对是以一种特殊的方式设置，即公钥是一个实体的标识符（任意字符串），相应的私钥是通过基于身份的密钥提取算法生成的，将标识符与可信权威的主密钥绑定。在同一篇论文中，Shamir提供了第一个基于RSA问题的密钥提取算法，并提出了一种基于身份的签名方案。通过使用不同的Shamir密钥提取算法，提出了更多的基于身份的签名方案和密钥协商方案（如[22,23]）。然而，构建一个实际的基于身份的加密(IBE)方案多年来一直是一个开放的问题。

近20年后，Boneh和富兰克林[4]，Cocks[15]和Sakai等人[30]在2001年提出了三种IBE解决方案。Cocks的解是基于二次剩余问题的。Boneh和富兰克林以及Sakai等人的解决方案都是基于椭圆曲线[34]上的双线性对，其方案的安全性是基于(BDH)问题[4]。他们的方案在实际应用中是有效的。Boneh和富兰克林在[4]中为IBE定义了一个制定完善的安全模型。Boneh-富兰克林方案(简称BF-IBE)由于它是第一个在适当的模型中具有安全性证明的IBE方案，因此受到了广泛的关注。

BF-IBE和Sakai等人。IBE解决方案有一个非常相似的私钥提取算法，其中一个标识字符串被映射到椭圆曲线上的一个点，然后通过将映射点与主私钥相乘来计算相应的私钥。该密钥提取算法首次出现在Sakai等人在2000年的工作[29]中，作为一个基于身份的密钥建立协议的准备步骤。除了BF-IBE和Sakai等人。IBE方案[30]、许多其他基于身份的密码原型都利用了这种密钥提取思想，如签名方案[10,21]、认证密钥协议方案[11,35]和签名加密方案[7,12]。这些方案的安全性受到了仔细验证（尽管最近指出了一些削减中的一些错误，但也得到了修正，例如，[14,18]）。

基于相同的工具，双线配对，Sakai和Kasahara在2003年提出了一种新的IBE方案，使用另一种基于身份的密钥提取算法。这个算法的思想可以追溯到2002年[27]的工作。该算法需要更简单的哈希，因此提高了性能。更具体地说，它将一个标识映射到一个元素h∈Z∗q，而不是一个椭圆曲线上的一个点。相应的私钥生成如下：首先，计算主密钥（Z*q中的一个随机整数）和映射的h的倒数；其次，将椭圆曲线的一个点(曲线的点组成的群上q阶子群的生成元)与倒数（第一步得到的数）相乘。在最初的论文发表后，许多基于这个密钥提取思想的其他基于身份的方案已经发表，例如[25,26]。

然而，这些方案要么是未经验证的，要么是它们的安全证明是有问题的（例如，[13]）。在现代密码学中，任何密码学方案都需要经过仔细证明的，将正式的安全模型简化为硬度假设。为此，这项工作旨在建立Sakai和Kasahara IBE方案的安全性信心。

论文的其余部分组织如下。在下一节中，我们将回顾现有的原型、一些相关的假设和IBE安全模型。在第3节中，我们首先使用来自[28]的Sakai和Kasahara IBE方案的简单版本和Fujisaki-Okamoto变换[16]来提出一个有效的IBE方案(我们称之为SK-IBE)。然后证明了SK-IBE在随机预测模型中选择密文安全。我们的证明是基于一个合理的、经过充分探索的硬度假设。在第4节中，我们展示了SK-IBE在安全性和性能方面的一些可能的改进。在第5节中，我们比较了SK-IBE和BF-IBE。我们在第6节中总结了论文。

2 预备知识

在本节中，我们回顾了现有的原型，包括双线性配对、一些相关的假设和IBE的安全模型。

假设4

定理1

DH和1-DHI时间复杂度是相等的，即如果存在一个多项式时间算法来解决DH，那么就存在一个1-DHI的多项式时间算法，如果存在一个多项式时间算法来解决1-DHI，那么就存在一个DH的多项式时间算法。

假设5

定理2

如果存在一个多项式时间算法来求解(k-1)-DHI，那么就存在一个针对k-CAA1的多项式时间算法。如果存在一个多项式时间算法来求解(k-1)-CAA1，则存在一个针对k-DHI的多项式时间算法。

假设6

Mitsunari等人建立了[27]中k-CAA2和k-DHI(也称为k-wDHA)之间的关系，而在k-CAA2的定义中，没有将值h0作为输入。然而，当查阅他们对定理3.5[27]的证明时，我们注意到h0必须作为问题的一部分给出。

定理3

当且仅当对于k-CAA2存在一个多项式时间算法，那么就会有一个多项式时间算法解决（k-1）-DHI

假设7

张等人。他的短签名证明[40]和Mitsunari等人。他的traitor tracing方案[27]使用了这个假设。然而，Tˆo等人在[37]中打破了traitor tracing方案，因为人们发现它实际上是基于一个“稍微”不同的假设，即不需要输出h的值。显然，如果一个人不需要证明他知道h的值，那么问题并不难。他可以简单地从G1中选择一个在问题中没有显示的随机元素作为应答，因为G1是素数阶q，对于某些h，任意r∈Z∗q满足r=1/h+x  mod  q。

假设8

定理4

如果存在一个多项式时间算法来求解(k-1)-sCAA1，则存在一个针对k-sDH的多项式时间算法。如果存在一个多项式时间算法来求解(k-1)-sDH，则存在一个针对k-sCAA1的多项式时间算法。

这些假设之间的关系如图1所示。在文献中，k-DBDHI假设被用于[1]构造一个没有随机预言的选择身份安全IBE方案（见下一节的定义）[6]和k-sDH是用来构造一个没有随机预言短签名[2]，而k-sCAA1被[40]用来构造一个短签名与随机预言和建立一个traitor tracing方案[27]。

2.2 IBE方案和他们的安全模型

设k为安全参数，M和C分别表示消息空间和密文空间。一个IBE方案由四种多项式时间算法指定：

Canetti等人提出了一个较弱的IBE概念，即选择性身份自适应选择的密文攻击安全方案(简称IND-sID-CCA)，在该方案中，对手必须在看到公共系统参数（主公钥）[8]之前，提交它想要被挑战的身份标识。最新的工作[19]为这个公式提供了一些正式的安全分析。

3 SK-IBE

在本节中，我们将研究SK-IBE的安全性。我们选择Sakai和Kasahara  IBE方案[28]的最简单变体作为SK-IBE的基本版本。Scott在[31]中也描述了这个基本版本。为了达到对自适应选择的密文攻击的安全性，我们使用了在BF-IBE[4]中使用的Fujisaki-Okamoto变换[16]。

SK-IBE由四种多项式时间算法指定：

Setup 给定安全参数k，参数是由一下几步生成的

1.生成三个素数q阶的循环群G1、G2和GT，一个从G2到G1的同构ψ，以及一个双线性配对映射ˆe：G1×G2→GT。随机选择一个生成元P2∈G∗2，并设置P1=ψ(P2)

2.随机选择一个s∈Z∗q，并计算Ppub=sP1。

3.选择四个加密哈希函数H1：{0,1}∗→Z∗q，H2：GT→{0,1}n，H3：{0,1}n×{0,1}n→Z∗q和H4：{0,1}n→{0,1}n对于某些整数n>0。

消息空间为M={0,1}n。密文空间为C=G∗1×{0,1}n×{0,1}n。主公钥为Mpk=(q、G1、G2、GT、ψ、ˆe、n、P1、P2、Ppub、H1、H2、H3、H4)，主密钥为Msk=s。

Remark1

提取算法的结果是在私人签名密钥s下签名的消息IDA上的一个短签名dA。在[40]的定理3中证明，在随机[40]预言模型[6]中，如果k-sCAA1假设是合理的，该签名方案在选择消息攻击[20]下是存在不可抑制的。

Remark2

在加密算法中，配对g=e^(P1，P2)是固定的并且可以被提前计算，能够将它看作是一个系统公共参数，因此，在加密阶段是不需要配对计算的。

3.2 SK-IBE的安全性

现在我们评估了SK-IBE的安全性。我们证明了SK-IBE的安全性可以降低到k-BDHI问题的硬度。还原结果类似于BF-IBE[4]的证明。但是，我们将考虑到由Galindo校正的[4]引理4.6中的误差。

定理8

SK-IBE对IND-ID-CCA敌手是安全的，只要Hi(1≤i≤4)是随机的神谕，并且k-BDHI假设是合理的。特别是，假设存在一个针对SK-IBE的IND-ID-CCA对手A，它具有e(k)的优势和运行时间t(k)的优势。假设在攻击期间，A分别对Hi （1≤i≤4）进行最多qD解密查询和最多qi查询(Hi可以由A直接查询或通过提取查询、解密查询或挑战操作间接查询)。这样就会存在一个算法B在AdvB(k)优势和tB(k)运行时间内解决q1-BDHI问题，其中

X是计算配对的时间，Ti是在Gi中进行乘法运算的时间，q是G1的阶，n是σ的长度，我们假设ψ的计算复杂度是微不足道的。

证明：

这个定理紧接着结合引理1、2和3。有三个步骤的减少可以概述如下。首先我们证明如果存在一个IND-ID-CCA对手，谁能够通过执行自适应选择密文攻击来打破在2.2节中的安全模型定义的SK-IBE方案，然后存在一个IND-CCA敌手自适应选择密文攻击打破引理1定义的BasicPubhy方案。其次，如果存在这样的IND-CCA敌手，那么我们证明（在引理2中）一定有一个IND-CPA敌手，它能通过仅仅启动选择明文攻击来破坏相应的BasicPub方案。最后，在引理3中，我们证明了如果BasicPub方案对IND-CPA对手不安全，那么相应的k-BDHI假设是有缺陷的。

引理1

假设H1是一个随机预言模型，存在一个IND-ID-CCA敌手对SK-IBE有优势² (k) 对H1最多q1不同查询(注意H1可以直接查询或通过间接提取查询，解密查询或挑战操作进行查询)。然后存在一个IND-CCA敌手B对BasicPubhy方案运行在时间O(time(A)+qD·(χ+T1))内，优势至少为²(k)/q1，其中χ是计算配对的时间，T1是G1中乘法运算的时间。

BasicPubhy由三种算法指定：密钥生成、加密和解密。