英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
基于ID的具有常数配对计算的聚合签名方案
摘要
聚合签名方案允许来自n个不同用户的n个不同消息上的n个签名来聚合单个签名。 这种方案的主要优点是它们允许带宽和计算节省。 由于Boneh等人的配对的聚合签名方案，存在几个用于构造基于ID的聚合签名方案的尝试。 然而，它们用于配对计算的计算复杂性随着签名者的数量线性增长。 在本文中，我们提出了一个基于ID的有效集合签名方案与常数配对计算。 我们还在计算Diffie-Hellman假设的随机oracle模型中给出其安全证据。
引言
在传统的公钥基础设施（PKI）中，当Bob希望向Alice发送消息时，首先他必须在公共目录中获得她的已认证的公钥。基于身份（ID）的基础设施使部署切实可行;它允许用户的公钥很容易从她已知的身份信息，如电子邮件地址（Shamir，1984）中推导出来。基于ID的基础设施涉及用户和具有主公共/秘密密钥对的私钥生成器（PKG），并且PKG负责为用户生成私钥。这消除了对PKI中使用的证书的需要。这样的密码系统减轻了证书开销，解决了PKI技术的问题：证书管理包括证书验证的存储，分布和计算成本。当考虑具有相同PKG的多个签名者的基于ID的签名时，基于ID的系统的优点变得更加引人注目，因为签名者不需要发送具有证书颁发机构签名的单个公钥和证书。由于Boneh和Franklin基于Weil配对的基于ID的加密方案（Boneh和Franklin，2001），代数曲线的双线性配对已经引起了密码学研究界的相当大的兴趣，使得以前未知或不切实际的加密原语有可能被实现。
许多现实世界的应用程序涉及许多不同用户生成的许多不同消息的签名。例如，在深度n的PKI中，给每个用户一个n个证书链。该链包含n个证书颁发机构在n个不同证书上的n个签名。类似地，在安全BGP协议（SBGP）（Kent等人，2000）中，每个路由器接收证明网络中长度为n的某个路径的n个签名的列表。路由器在路径中签署其自己的段并将得到的n 1个签名的列表转发到下一个路由器。结果，路由消息中的签名的数量在路径的长度上是线性的。两个应用将受益于用于压缩由不同方发出的不同消息上的签名的列表的方法。聚合签名方案使我们能够精确地实现这种类型的压缩。聚合签名（AS）方案是具有 单独签名的序列, . . . , 的附加属性 的数字签名方案---这里是签名，在基础基本签名方案下，一些消息在一些公共密钥下可以被压缩成单个紧凑集合签名，其同时验证在下针对所有i = 1...n签署的事实。有一个相应的聚合验证过程，接受输入(,), . . . , (,),和accepts 或者 rejects。聚合对于减少带宽和存储是有用的，并且对于诸如传感器，蜂窝电话和PDA的移动设备特别有吸引力，其中通信比计算更昂贵，并且显着地有助于减少电池寿命。 Boneh等人（2003）提出了基于BLS短签名方案的AS方案（Boneh等人，2002）。在基于ID的设置中，存在几个用于构造AS方案的试验（Cheon等人，2004; Yoon等人，2005; Xu等人，2005; Cheng等人，2005; Herranz，2006; Gentry和Ramzan，2006）。然而，在上述意义上，方案不是完全基于ID的聚合（IBAS）方案，因为它们需要额外的通信回合来将由多个签名者提供的基于ID的签名的随机部分聚合成单个元素（Cheng等人，2005）或者某种同步用于共享相同的随机串（Gentry和Ramzan，2006），或者它们的签名长度随着签名者的数量线性增长（Cheon等人，2004; Yoon等人，2005; Xu等人，2005 ; Hess，2003）。事实上，在构建IBAS方案中最困难的问题是如何将n个签名者的集合签名长度从减少到。要看到困难，请注意，几乎所有基于ID的签名（IBS）方案不是确定性的不同于BLS短签名方案（Boneh等人，2002），因此如果每个连续签名者以一个简单的方式贡献对聚合签名的随机性，该随机性将导致签名的大小与n线性增长。更精确地，存在两种方式用于将由多个签名者生成的IBS的随机部分聚合到基础组的单个元素中。一个是要求额外的通信回合将每个签名的随机部分聚集成单个元素，如Cheng等人的方案（Cheng等人，2005）。由于在所有签名者贡献之前不能生成其集合签名，所以该方案实际上与基于ID的阈值签名方案具有一些相似性。此外，其安全性证明是在Boneh等人定义的通常的聚合模型中完成的。 （2003），即使它适应交互式协议以获得.为了证明Cheng等人的方案的安全性，需要一种适合于交互式情况的新的安全模型。另一个是要求一定的同步共享相同的随机字符串，如Gentry和Ramzan（2006），即所有签名者必须基于同步时钟共享相同的字符串，因此只有所有签名者同时签名的签名可以聚合成单个签名。如果其同时性从方案中移除，即，具有多个签名者的不同随机串的它们的IBS被聚合，则其签名长度仍然随签名者的数量线性增长。此外，使用上述两种方法的方案（Cheng等人，2005; Gentry和Ramzan，2006）牺牲了获得这种不完全紧密性的灵活性，即，它们不允许签名者的特别收集。最近，Herranz（2006）提出了基于Schnorr签名方案的确定性IBS方案，其允许“部分”聚合，即，只有当聚集的签名来自相同签名者时，它才实现紧凑性。此外，所有现有IBAS方案（Yoon等人，2005; Xu等人，2005; Cheng等人，2005; Herranz，2006）具有随着签名者数量线性增长的配对计算的计算复杂性。
似乎没有将任何IBS方案与聚合技术组合以获得IBAS方案的任何通用方式。这是由于以下原因： IBS方案可以单独是安全的，但是当执行某种聚合技术时可能失去其安全性。实际上，已知当根据现有的IBS方案来构造IBAS方案时，由于Boneh等人（2003）的汇集方式中的Cha和Cheon（2003），Hess（2003）和Paterson（2002）伪造是可能的; Cheon 等人（2004）指出为什么现有的IBS方案（Cha和Cheon，2003; Hess，2003; Paterson，2002）未能建立安全的IBAS方案。我们可以很容易地证明，相同的伪造攻击适用于基于Yi的IBS方案的IBAS方案（Yi，2003）。构建IBS方案的另一种方法是将任何标准签名（SS）方案转换为IBS方案的通用转换。这种方法是使用SS方案并简单地将包含签名者的公钥的证书附加到签名。这种基于认证的方法显然是民间传说。 Bellare 等人（2004）通过从任何安全SS方案提供IBS方案的通用和安全的结构来形式化该想法。最近，Galindo 等人（2006）通过扩展Bellare等人的结构提出了具有附加特性的IBS方案的通用构造。他们的结果包含来自SS方案的允许恒定长度聚合的IBAS方案的一般构造。然而，其所产生的IBAS的长度相对于签名者n的数量是线性的，因为它由来自基本标准签名的集合签名以及附加的n个公钥构成。此外，该技术具有很少的应用，因为只有一个SS方案是恒定长度聚合，即具有BGLS方案的BLS短特征方案（Boneh等人，2002）（Boneh等人，2003）作为其AS方案。在这种情况下，来自Galindo-Herranz-Kiltz基于BLS方案的结构的转换的IBAS方案需要O（n）配对计算。
在同时验证多个签名者长期提供的IBS的实际情况下，验证成本和灵活性将优于通信成本。 我们注意到，配对计算是基于配对的密码系统中最耗时的。 虽然已经有许多工作讨论配对的复杂性以及如何加速配对计算，但是配对的计算仍然是耗时的。 因此，为了构建实际可用的方案，配对计算的数目应当最小化。 在本文中，我们提出了一种IBS方案，其允许具有常数配对计算的IBAS方案。 我们的IBAS方案既不需要额外的通信循环，也不需要用于聚集随机性的某种同步，而它不实现紧凑性。
本文的其余部分安排如下。 在第2节中，我们描述IBS和IBAS方案的定义和安全概念。 在第3节中，我们首先提出一个新的IBS计划，并在计算Diffie-Hellman假设下的随机oracle模型中提供其安全性证明。 在第4节中，我们基于所提出的签名方案构建有效的IBAS方案并提供其安全性证明。 结语在第5节中给出。
准备工作
定义与计算假设
本文中使用的符号和基本定义总结如下：
bull; Cyclic (additive) group G: all elements Q in G have of the form Q = rP, for some P isin;G, in this case, we call P a generator of G, where rP consists of adding together r isin;Z copies of the point P, yielding the point P ·· · P = rP. If G is a group of an elliptic curve, we call rP a scalar multiplication of P.
循环（加性）组G：G中的所有元素Q具有形式Q = rP，对于一些PG，在这种情况下，我们称为P的G的生成器，其中rP包括将risin;Z 点P，产生点P ··· P = rP。 如果G是一组椭圆曲线，我们称rP是一个标量乘法。
Cyclic (multiplicative) group : all elements y in have of the form y = for some g isin;G, where g is a generator of and consists of multiplying together k isin;Z copies of the element g, yielding g· · ·g = . In this case, we call an exponentiation for the base g and the exponent k.
循环（乘法）组：中的所有元素y对于一些gG具有形式y = ，其中g是的生成器，并且包括将元素g的kZ 个副本相乘，产生g ···g = 。 在这种情况下，我们将称为基底g和指数k的求幂。
bull; Order of G, |G|: the number of elements in G.
G的顺序，| G |：G中的元素数
bull; Discrete logarithm problem in G: given (g, gx), to compute x.
G中的离散对数问题：给定（g，），以计算x。
bull; Elliptic curve E defined over a finite field : E/ is given by an equation of the form
y2 a1xy a3y = x3 a2x2 a4x a6, ai
together with the condition the curve has no singular points.
在有限域：E / 上定义的椭圆曲线E由形式的方程给出
y2 a1xy a3y = x3 a2x2 a4x a6, ai
与曲线没有奇异点的条件一起。
bull; Supersingular elliptic curve E/Fp: the order of E(Fp), i.e., |E(Fp)| =p 1, where
and O is an infinity point.
超椭圆曲线E /：E（）的阶，即| E（）| = p 1，
其中 O是无穷点
令G1和G2是大素数阶q的两个循环群。 我们写G1加法和G2乘法。 我们假设G1和G2中的离散对数问题都很难。 我们陈述了一些关于配对的基本事实（参见Boneh和Franklin，2001; Boneh等，2002; Silverman，1986，了解更多信息）。
允许的配对：如果e：G1times;G1→G2是具有以下属性的映射，我们称之为可配对：
1.双线性：对于所有P，Qisin;G1和对于所有a，bZ，e（aP，bQ）=
2.非简并性：存在PG1，使得e（P，P）/ = 1。
3.可计算性：有一个有效的算法来计算任何P，QG1的e（P，Q）。
可以修改与超椭圆椭圆曲线或阿贝尔变种相关联的Weil和Tate配对以创建这样的允许配对，如在Boneh和Franklin（2001，2003）中。
我们考虑以下问题和假设在（G1， ）。
定义2.1 [计算Diffie-Hellman（CDH）问题]。
给定（P，xP，yP），以计算xyP，其中x，y，并且P是G1的生成器。
定义2.2 [计算Diffie-Hellman（CDH）假设]。
令为CDH参数发生器。 我们说算法A在解决的CDH问题时具有优点ε（k），如果对于足够大的k，
我们说G满足CDH假设，如果对于t算法A中的任何随机化多项式时间，我们具有是可忽略的函数。当G满足CDH假设时，我们说CDH问题在由G产生的G1中是困难的 我们说算法A（t，ε） - 如果A在时间t解决CDH问题并且至少为ε，则
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[28482]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
