标准模型下的基于身份签名的效率型密码.doc

标准模型下安全的基于身份的有效签名Kenneth G. Paterson and Jacob C.N. SchuldtInformation Security Group,Royal Holloway, University of London,Egham, Surrey, TW20 0EX, UKkenny.paterson, jacob.schuldtrhul.ac.uk摘要：唯一已知的基于身份签名的构造方法可以在标准模型下被证明是安全的，这是是基于在非基于身份签名上附加证书的方法。这种传统的构造方法引起了方案的一些非效率型因素或者枝蔓，这便提出了寻找更有效率更直接的构造问题。我们给出了第一个这种构造方案。我们的方案沿袭沃特斯最近提出的基于身份的加密方案的改进方案。它是一种效率的算法并且签名的长度很短。这个方案的安全性在标准模型下得到验证并且依靠了配对群上Diffie-Hellman问题计算的困难程度。1. 简介基于身份的加密（IBE），首次被Shamir 提出Sha84,这使得我们可以给一个对象计算一个公钥，这仅仅需要取得常规的特征方案和一串识别对象的字符串（比如邮件地址，电话号码等）。绝对安全的私钥生成器（PKG）计算出私钥，并且把这些私钥分配给每个对象。这样，就避免了使用在传统公钥加密中使用的证书。尽管Shamir早在1984年就提出了IBE 方案的想法，但直到Boneh和Franklin以及Cocks的论文发表以后才有了既安全又有效的构造方法。这以后，这个领域里出现了大量的论文（查阅BAR可以获得部分这些论文的列表），包括包涵若干直接构造的基于身份签名的方案。大多数这些基于身份的签名方案在随机预言模型中被证实是安全的。但是，事实上当随机预言模型代入一个具体的散列函数时，结果方案可能并不是安全的。为了解决这个问题，进来在建立标准模型下绝对安全的IBE方案上花费了很多努力。Boneh和Boyen最先提出了一个IBE方案，这个方案在使用一个“精心选择的ID”的模型下被验证安全了，这个模型比Boneh和Franklin最初提出的模型条件要弱。同样的作者在随后提出了一个IBE方案，这个方案在所有Boneh-Franklin安全模型和标准模型下都是安全的，但效率却不高。最后，Waters成功的构造出一个简明有效的IBE方案，这个方案同时满足安全和效率两方面的要求。Naccache和Chatterjee-Sarkar独立提出了一个减少Waters的方案中对尺寸要求的技术，这使得这个方案更加适合实际应用。建立IBS方案一个一般的方法就是使用普通签名方案（例如非基于身份的签名方法）并且附加上包含签名人公钥的方法来签名的。这种基于证书的方法似乎很通俗，它的各种不同版本也在过去到现在的各种论文中有所提及。这个技术的简明性表明在某些方面，IBS方案比IBE方案更容易获取。而且，如果使用普通签名方法作为签名的组成部分的方法在标准模型下是安全的，我们就可以得到一个在标准模型下也安全的IBS方法。但是这种构造方法也有缺点。一个缺点是在建立基于身份的签名时我们同时需要公钥（签名人的）和两个普通签名（一个来自签名人另一个来自于证书提供者）。这一点影响签名的长度。另一个缺点是每一个基于身份的签名方案中的验证都要涉及到两个普通签名的验证。这两个不利条件导致了方案的一些没有效率的问题。可不可以找到一个在标准模型下更好的方法？这个问题逐渐浮现出来。一个有趣的现象就是，任何IBE方案都可以应用到构造一个普通的签名方案，这个现象的发现要归功于Boneh和Franklin的Nore。这要靠把IBE的主秘密数作为私钥，并且公布方案的参数作为私钥。对一条名为的信息签名，使用身份私钥为而且验证可以通过选择一个随机信息来执行。使用公钥加密信息，而且验证解密信息可能要用到给出的解密密钥。如果使用的IBE方案是IND-ID-CPA安全，生成的签名在适应选择消息攻击下是存在性不可伪造的。这个技术被Boneh，Lynn和Shancham用来从Boeneh和Franklin的IBE方案建立短签名，类似于Boneh和Boyen从一个IBE方案得到另一种短签名方案都要归功于同一个作者。正如Gentry和Silverberg所阐述的，如果分等级的IBE方案（HIBE）被使用在一个IBE方案中，IBS方案可以用一种十分相似的方法建立出来。事实上这将会导出一个分等级的IBS方案，这个方案身份签名是一个比使用到HIBE方案少一个层次的层次结构 一部分。当身份签名消息，身份作为的一个孩子被插入到层次结构中。综上，一个签名就是的私钥，验证者检查一条通过使用公钥作为身份随机信息是可能的。限制HIBE的等级数为2等级方案就是普通的IBS方案了。我们的构造。这个方案是在提供一个在不适用随机预言时安全的方案的研究的一个自然延伸，我们给出了第一个直接构造IBS的方案，这个方案在标准模型下被证实是安全的。我们的方案是基于对Waters的方案在分等级上的扩展，我们用了上面所描述的一个转化2层HIBE方法到一个IBS方法来构造我们的方案。我们在通过计算Diffie-Hellman问题难度的假设来保证我们的签名方案是安全的。这个假设似乎比现今介绍到基于配对的加密方法中的硬度假设更加自然。就签名的长度和计算的效率上说，我们的新方法在已经存在的基于身份的签名方案中是很有竞争力的（那些是在随机预言模型中被证明是安全的方案）。我们的签名有三组元素构成，签名过程中不需使用配对，验证过程过程需要用到3个配对计算。我们的方案在计算效率和签名长度上较在Waters的方案上附加基于证书的结构的那些方案有更大的优势。对比那些由Boneh和Boyen的签名方案得到的方案，我们的方案大概一半的长度，但验证计算要花费更多的一组配对计算。但是，Boneh和Boyen衍生出来的方案的安全性依赖于q-SDH问题的硬度假设，然而我们的方案的安全性是基于可论证的计算性Diffie-Hellman（CDH）问题硬度假设。我们的方案存在的唯一一个缺陷就是公共参数占据一个相对较大的尺寸。但是，我们展示了 一个如何在方案中使用Naccachehe Chatterjee-Sarkar的技术来减少公共参数尺寸的方法，代价是损失了安全性。2. 基于身份的签名一个基于身份的签名方案可以被描述为以下四个算法步骤初始化. 这个算法在可靠安全实体上执行，输入一个秘密参数，生成一个公共的参数，和一个可靠秘密参数。可靠安全实体公布保留可靠秘密参数。提取. 给定一个身份，可靠秘密参数和，这个算法生成私钥的一个私钥。可靠安全实体将会用这个算法为所有参与方案的实体生成私钥并且通过安全渠道分配这些私钥到每一个所有者。签名. 给定一条消息，一个身份，私钥和，这个算法生成对的一个签名。使用身份的实体将使用这个算法来签名。验证. 给定签名，消息，身份和，如果是对有效签名算法输出，否则输出。2.1 存在的不可伪造性Goldwasser，Micali和Rivest定义了一个存在的不可伪造性在一个有适应能力的选择消息攻击下的安全性模型，这个模型可以自然的延伸到基于身份的方案中。我们将在下面给出的挑战者和对手的游戏中确定基于身份签名的安全性：初始化. 挑战者启动签名方案中的初始化得到公共参数和可靠秘密数字。对手获得但是可靠秘密数字由挑战者保存。提问. 对手有适应性的编造出许多不同的问题交给挑战者。每一个问题可以是一下的其中一个。l 提取问题。对手可以询问到任何一个身份的私钥。挑战者通过执行回答询问，并发送私钥给对手。l 签名问题。对手可以询问任意身份对消息的签名。挑战者通过运行得到的私钥，然后运行得到签名，签名有挑战者发送给对手。伪造. 对手输出一条消息，一个身份和一串签名。以下内容有效的话表明对手伪造成功：a)b) 对手没有对做出抽取提问.c) 对手没有对做签名提问.以上游戏中对手的有利因素定义为其中，这个概率是挑战者和对手游戏中所有成功事件都发生的概率。定义 1. 在一个基于身份的签名方案中一个对手被认为是一个伪造者如果在上述游戏中有至少存在、最长运行时间为，分别制造出最多为和个抽取问题和签名问题。一个方案被认为是安全的如果伪造者不存在。以上的游戏可以很容易的延伸覆盖强不可伪造性，这要在伪造这一步骤中改变第三个要求为“不是作为一个签名响应而得到”。但是，我们确定的方案在这种强条件下并不安全，因为敌手可以轻易的更改一个已经存在对某信息的签名是指成为一条同样信息的新签名。3. 复杂性假设我们的签名方案的安全性在签名被建立以后将被规约为计算性Diffie-Hellman问题的解决困难性。我们简要的回顾一下CDH问题的定义：定义 2. 给出一个阶为群并含有生成元和元素，其中是从均匀随机选择出的两个数。则中的CDH问题就是计算。定义3. 我们说中的假设成立，如果没有算法在时间内解决CDH问题的可能性至少为。4. 构造我们新的基于身份的签名方案是建立于Waters提出的基于身份加密方案分等级延伸。但是，如第5节指出的，我们的安全性减少到CDH问题的困难性，而Waters的方案依托于强双线性Diffie-Hellman假设。我们的方案是基于双线性映射。现在简要的介绍这个映射的一些基本性质。令和为一个阶为的群，令为的一个生成元。映射被认为是合格映射如果满足一下三条条件：a) 是双线性映射，即对所有都成立.b) 是非退化性的，即.c) 是有效可计算的.查阅Gal05以便了解更多关于这个映射的信息。在第7节中，我们简略阐述了需求的改变，以便于允许我们的方案在更加普遍的状态下操作，即其中.以下所有身份和消息将被假设为长度分别为和比特流。建立一个满足任意长度的身份和消息的更加灵活的方案就需要定义冲突抵制的散列函数，和，这两个散列函数用来创建指定长度的身份和消息。我们将用记号作为从集合中随机选择出的简称。我们新的签名方案由以下算法定义出来：初始化. 选择阶为的群和，一个合格的配对运算：，构造的一个发生器。现在，选择一个秘密数字，计算，选取。并且选择长度分别为和的元素，向量，向量的分量从中随机选取。公共参数即，秘密数字为。提取. 令为一串长度为的比特流，它表示一个身份，令为的第位上的比特字。定义为所有满足的指数的集合。构造私钥身份为的实体的私钥，选取并计算：注意用户可以很容易的在从绝对安全实体上获得私钥以后把私钥随机化。签名. 令为一串长度为的比特流，它表示一个身份，令为一串表示消息的比特流。类似于在提取算法中定义为所有满足的指数的集合，定义为所有满足的指数的集合。提取并计算即为对消息的签名。验证. 给定待验证的签名为身份对消息的签名。如果满足：则验证者接受消息。显然签名算法得出的签名可以被验证者接受。因此这个方案是正确的。4.1 方案效率方案中私钥和签名的尺寸大小分别是2和3组元素。但是要注意签名元组的第2个值将在给定相同用户的情况下保持不变。因此，如果单一用户要对多条消息进行签名，或者单一验证者要验证多条同一个用户签名的多条消息时，只要包含在其中一条信息的签名中。公共参数包括，对群的描述信息，配对和组的元素。在实际的方案中，公共参数的大小与具体执行有关系，我们在第6节中讨论了怎样减少中群元素的需求数量。为了构造一个签名，签名者需要计算最多次上的乘法（平均次），并且执行2次上的乘幂运算。验证过程最多需要次上的乘法运算（平均次）和四次配对运算。但是，可以预先计算出来并暂时存储，这样可以减少验证过程中配对运算的花销。如果一个验证者验证同一签名人的多个消息签名，更进一步的配对运算也可以省略了。因此，我们的方案就稍微比目前的IBS方案的花销要大些（查阅Hes02中的表格可以获得更多例子），但是，正如下一节要展示的，我们的方案在标准模型下是安全的，而那些方案是在随机预言模型中被证实是安全的。我们也已经在简介在应用于标准模型下安全方案时比较了我们这个方案和源于基于证书的IBS方案。5. 安全性证明我们将在标准模型下证明我们的方案在选择性消息攻击下是存在性不可伪造的。这个结论是建立在计算性Diffie-Hellman问题难以解决的基础之上的。定理1. 假设假设在中成立，且则第4节的基于身份签名方案是安全的，其中分别是中进行乘法和乘幂运算的时间。证明：假设方案中存在一个伪造者。由这个伪造者，我们可以建立算法，该算法可以在最多的时间内以大于的概率解决CDH问题，这与假设相悖。我们的方法是基于Wat05中所言。算法需要被给出群，一个生成元和元素。如果要使得能够计算出，那么必须能够模仿的一个挑战者。这个模仿过程如下所示：开始. 置，随机选取两个整数，。给定和时我们假设。模拟器则选择一个整数和一个长度为向量，其中对于任意。类似的选择另一个整数，长度为的向量，。最后选择两个整数，再分别选择长度分别为和的向量，其中。为了表达式的简洁，分别对于身份和消息定义下面两对函数：现在完成下面的任务来建立IBE方案中的公共参数集合：注意这些公共参数与挑战者和的游戏是同分布的。并且，这些步骤表示主密钥将是，对于任意，等式成立。所有的公共参数传递给。询问. 对手算法运行时，抽取问询和签名问询都有可能发生。按照如下方式回答问询l 抽取问询。假设提问是为了得到身份的私钥。不知道主密钥，但是假设可以通过选取并计算而建立私钥。记，可以验证以这种方式产生的是一个有效的私钥。因为：并且因此对于对手来说，所有由计算得到的私钥和真正挑战者生成的私钥是难以区分的。另一方面，假如说，则以上的计算不能进行，模拟器将因此被抑制。为了简化分析模拟，一旦我们强制抑制模拟器。假设，则必有且。很显然可以推出，因此，推出。所以以上的情况必定保证的私钥可以被建立。l 签名询问。考察对的一次问询（不失一般性，可以假设还没有对做抽取问询）。若，就可以在一次抽取问询中建立的私钥，并使用算法得到对的签名。如果，将尝试用与在抽取问询中构造私钥类似的方法建立签名。假设。同上面结论，这表示。不妨设。选取计算对的签名：其中。这个等式表示回应的签名问询是分散的，因为他们要与真正的挑战者配合。如果，模拟器被抑制。伪造. 如果在以上每个问询中都没有被抑制，会以至少的可能性返回身份，消息和对有效伪造签名。如果或那么将被抑制。另一方面，如果且，计算并输出这是给定CDH问题的解。下面完成对模拟过程的描述。我们还需要分析的就是不被抑制的概率。为了使模拟过程不被抑制，必须使所有的抽取问询中对身份有，所有签名询问中要么满足，要么满足，并且。但为了简化分析，我们要给出这个事件的子事件的概率范围。更确切的说，我们要把签名询问分成两类涉及的询问和涉及的提问。然后我们考察所有身份满足，排除签名询问中满足且也会应答的情况。这样，我们将给出不被抑制的一个削弱的概率范围。令是抽取问询和签名问询中出现的非挑战身份，令签名问询中不涉及挑战身份的消息。显然，且。定义事件和为从以上的分析中得出，不被抑制的概率是容易看出事件和是相互独立的。本质上是因为函数和确定了这些事件是选择性独立的而且对于敌手是隐藏起来的。由以上可以看出，假设可以推出。而且，这个假设给出如果，则存在唯一的满足，其中。因为和时随机选取的，我们有也可以得到置模拟过程中得到类似的分析签名询问得到如下结论也可以得到如果模拟过程没有被抑制，就能够以至少产生一个有效的伪造签名。算法可以从以上结果中计算出。算法的时间复杂度受到抽取和签名询问中乘幂运算，和的大小，乘法运算的影响。因为在抽取和签名询问中分别存在和的乘法运算和和的乘幂运算，所以时间复杂度为因此，定理证明完毕。6. 用安全性换取效率在一个实际的方案中，的身份和的消息大部分是由可抵抗冲突的散列函数产生的。这使得和最小为160，也就是说我们方案中的公共参数将包含最少325个中群元素。当选定的使得其上的CDH问题被认作是困难的，那么公共参数的大小将上升到不适合环境存储容量的大小。但是，Naccache Nac05和Chatterjee-Sarkar SC05独立提出了一个对Waters的方案改进，这个改进将减少公共参数的大小。这个改进也适合我们的签名方案。.. Naccache和Chatterjee-Sarkar的技术在我们的方案中，当一个实体签名了某条消息，他便计算产物其中是满足第位为1的指数的集合。这个技术的想法就是把消息认作是连接在一起的整数集合而不是连串的二进制位集合。例如：其中且，则以此代替上面的产物得到这将以因子减少的大小并且公共参数中包含的群元素的个数将变小到。类似的，一个身份被人做是一连串的整数，并用上面类似的方法替换中的元素。的大小将以因子减小。同时使用两种改进，公共参数将被减小到6.2. 改进方案的安全性如果使用上述改进，我们方案的安全性分析与第5节十分类似。但是，需要对函数和改进以保证这些函数还具有在第5节中需要的性质。我们可以假设与第5节同样的开始步骤，集中考察对我们改进方案的安全性分析有效的更改。如前面所叙述的，我们将分别假设由和的整数组成的身份和消息。第一个更改是模拟过程中开始缓解和的选择范围，范围扩张到和模拟过程开始阶段的其他所有选择值和步骤都与原方案一样。我们假设且重新定义和为：其中和指示的 位和位的整数分别组成了和。显然这些更改使得以下结论成立：l 且l 推出且推出。l 若，那么存在一个唯一的，使得。类似的，若，那么存在唯一使得，。有了这些性质，模拟过程其他的阶段就和第5节叙述的内容一样的进行了。对模拟过程成功概率的分析与第5节分析的基本一致，因为只有和值的变化范围（例如上面列出的最后一条性质）影响了对应概率。这改变了事件和在更新的函数和，我们可以得到因为事件和的概率不因为函数的改变而改变，成功的概率是成功的概率大约以因子低于第5节中模拟过程成功概率。时间复杂度保持为其中是敌手花费的时间，是中一次乘法运算花费的时间，是中一次乘幂运算花费的时间。6.3. 在大小，计算量和安全性之间权衡以上的结果表明我们可以减少公共参数中的元素个数到，但相比原方案安全性丧失了比特。对一个较小的和，以安全性交换更高的执行效率是可以接受的。这就是Naccache提出的方法。但是，用提高方案的计算性花费来阻止损失安全性是可能的。这个想法是由Chatterjee-Sarkar提出的，他提出可以通过提高的大小从而提高其上CDH问题的困难度的方法，这个方法可以弥补因为给定和的选择值来引起的安全性丢失。但是，当这个方法使用时有多个因数需要考虑。第一，上的CDH问题所提供的安全性需要顾及。目前，最有名的解决CDH问题的方法是靠解决离散对数问题（DLP）。上的DLP问题可以很容易的被规约到上的DLP问题，因此解决和上的DLP问题最熟知的方法要在选择群的时候被考虑到。第二，需要考虑选择适当的椭圆曲线类的可行性，合适的椭圆曲线要满足能够建立一个的配对其中和满足上述要求。我们注意到SC05的作者没有注意到这一点。最后，和增大将导致单个群元素的存储空间增大，而且算法复杂度也相应的提高。所有的论文中都很重视在公共参数减少的情况下评价方案的效率和安全性。但我们没有对这个细节的分析。7. 应用常规曲线的方案构造目前，唯一已知的建立双线性映射的方法是在椭圆曲线上使用一个Weil或者Tate配对。此外，若我们的方案中假设，那么我们就必须选择超奇异椭圆曲线，这是一类限制很强的曲线。但是，我们的方案可以很容易推广到使用形如的双线性映射，允许使用更加一般的椭圆曲线。这个灵活性遇到特定明确的安全级别时实施和选择参数时很重要。对广义的方案的安全性证明，我们要求存在一个有效可计算的同构映射，而且满足的生成元对应的生成元。这个同构映射只是在安全性证明中用到，并不是方案的一部分。而且，方案的安全性也将被减小到上的co-Diffie-Hellman问题BLS04。PS02中可以找到完整细节。8. 结论我们给出了第一个直接建立基于身份的签名方案，而且在标准模型下被验证是安全的。我们基本的方案计算效率高，而且我们给出了改进提高空间需求和提高参数的选定范围的技术。很容易看出我们方案可以推广到产生一个分等级的IBS（HIBS）方案。但是，建立一个效率高而且在便准模型下安全的HIBS方案依然是个开放性问题，这个方案必须有一个牢靠的安全规约。致谢我们感谢Jonathan Katz，Eike Kiltz和一个不知名的评论者点出了传统基于证书的方案应用于基于身份的签名。参考文献ADR02 J. H. An, Y. Dodis, and T. Rabin. On the security of joint signatureand encryption. In L. R. Knudsen, editor, EUROCRYPT, volume 2332 ofLNCS, pages 83107. Springer, 2002.Bar P. S. L. M. Barreto. The pairing-based crypto lounge..br/informatica/paulobarreto/pblounge.html.BB04a D. Boneh and X. Boyen. Efficient selective-ID secure identity-based encryptionwithout random oracles. In Cachin and Camenisch CC04, pages223238.BB04b D. Boneh and X. Boyen. Secure identity based encryption without randomoracles. In M. K. Franklin, editor, CRYPTO 2004, volume 3152 of LNCS,pages 443459. Springer, 2004.BB04c D. Boneh and X. Boyen. Short signatures without random oracles. InCachin and Camenisch CC04, pages 5673.BBP04 M. Bellare, A. Boldyreva, and A. Palacio. An uninstantiable randomoracle-model scheme for a hybrid-encryption problem. In Cachin andCamenisch CC04, pages 171188.BF01 D. Boneh and M. K. Franklin. Identity-based encryption from the Weilpairing. In J. Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages213229. Springer, 2001.BLMQ05 P. S. L. M. Barreto, B. Libert, N. McCullagh, and J. Quisquater. Efficientand provably-secure identity-based signatures and signcryption frombilinear maps. In B. Roy, editor, ASIACRYPT, volume 3788 of LNCS,pages 515532. Springer, 2005.BLS04 D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weilpairing. J. Cryptology, 17(4):297319, 2004.BNN04 M. Bellare, C. Namprempre, and G. Neven. Security proofs for identitybasedidentification and signature schemes. In Cachin and CamenischCC04, pages 268286.BR93 M. Bellare and P. Rogaway. Random oracles are practical: a paradigm fordesigning efficient protocols. In Proc. of CCS 1993, pages 6273. ACMPress 1993.CC03 J. C. Cha and J. H. Cheon. An identity-based signature from gap Diffie-Hellman groups. In Desmedt Des02, pages 1830.CC04 C. Cachin and J. Camenisch, editors. Proc. of EUROCRYPT 2004, volume3027 of LNCS. Springer, 2004.CGH98 R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology,revisited (preliminary version). In STOC, pages 209218, 1998.Coc01 C. Cocks. An identity based encryption scheme based on quadraticresidues. In B. Honary, editor, IMA Int. Conf., volume 2260 of LNCS,pages 360363. Springer, 2001.Des02 Y. Desmedt, editor. Proc. of PKC 2003, volume 2567 of LNCS. Springer,2003.DKXY03 Y. Dodis, J. Katz, S. Xu, and M. Yung. Strong key-insulated signatureschemes. In Desmedt Des02, pages 130144.Gal05 S. D. Galbraith. Pairings. In G. Seroussi I.F. Blake and N.P. Smart, editors,Advances in Elliptic Curve Cryptography, pages 183212. CambridgeUniversity Press, 2005.GMR88 S. Goldwasser, S. Micali, and R.L. Rivest. A digital signature schemesecure against adaptive chosen-message attacks. SIAM J. Comput.,17(2):281308, 1988.GS02 C. Gentry and A. Silverberg. Hierarchical ID-based cryptography. In Y.Zheng, editor, ASIACRYPT 2002, volume 2501 of LNCS, pages 548566.Springer, 2002.Hes02 F. Hess. Efficient identity based signature schemes based on pairings.In K. Nyberg and H. M. Heys, editors, Selected Areas in Cryptography,volume 2595 of LN