第２８卷第９期 计算机应用研究 Ｖ０１．２８ Ｎｏ．９
２０１１年９月 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｍ
Ｓ印．２０１１
辫群上代理签名体制的分析与设计水
隗云 ，张兴凯 ，熊国华。，穆灵
（１．解放军信息工程大学电子技术学院，郑州４５０００４；２．９６６１０部队，北京１ｆ２２０３；３．电子技术研究所，北京１００１９５）
摘要：为了研究抵抗量子分析的密码体制，对两种辫群上的代理签名体制进行分析，指出其不能抵抗已知签
名的存在性伪造攻击；基于匹配共轭搜索问题的难解性构造了新的代理签名体制。分析表明该体制满足代理签
名的各种安全需求，且计算效率高、签名长度短。
关键词：代理签名；辫群；匹配共轭搜索问题；已知签名的存在性伪造
中图分类号：ＴＰ３０９ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１１）０９．３５２２－０２
ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１１．０９．０９０
Ａｎａｌｙｓｉｓ ａｎｄ ｄｅｓｉｇｎ ｏｆ ｐｒｏｘｙ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅｓ ｏｖｅｒ ｂｒａｉｄ ｇｒｏｕｐｓ
ＷＥＩ Ｙｕｎ ，ＺＨＡＮＧ Ｘｉｎｇ．ｋａｉ ，ＸＩＯＮＧ Ｇｕｏ—ｈｕａ ，ＭＵ Ｌｉｎ
（１．Ｉｎｓｔｉｔｕｔｅ ｏｆＥｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ，ＰＬＡ Ｉｎｆｏｒｍａｔｉｏｎ Ｅ ｗ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ ４５０００４，Ｃｈｉｎａ；２．Ｕｎｉｔ ９６６１０，Ｂｅｌｌｉｎｇ １０２２０８，
ｃｈ ３．Ｉｎｓｔｉｔｕｔｅ ｏｆＥｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ，Ｂ曲ｉ １００１９５，ｃｈｔＭ）
Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｒｅｓｅａｒｃｈ ｑｕａｎｔｕｍ ｃｒｙｐｔａｎａｌｙｓｉｓ－ｒｅｓｉｓｔａｎｔ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｓｃｈｅｍｅｓ，ｔｈｉｓ ｐａｐｅｒ ｐｏｉｎｔｅｄ ｔｈｅ ｓｅｃｕｒｉｔｙ ｖｕｌｎｅｒａｂｉｌｉｔｉｅｓ
ｏｆｔｗｏ ｐｒｏｘｙ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｌｎ￣ｓ ｏｖｅｒ ｂｒａｉｄ ｇｒｏｕｐｓ ｔｈａｔ ｔｈｅｙ ｃｏｕｌｄ ｎｏｔ ｒｅｓｉｓｔ ｔｈｅ ｋｎｏｗｎ—ｓｉｇｎａｔｕｒｅ ｅｘｉｓｔｅｎｔｉａｌ ｆｏｒｇｅｒｙ ａｔｔａｃｋ．Ｔｈｅｎ ｐｒｏ－
ｐｏｓｅｄ ａ ｎｅｗ ｐｒｏｘｙ ｓｉｇｎａｔｒｕｅ ｓｃｈｅｍｅ ｂａｓｅｄ ｏｎ ｔｈｅ ｄｉｆｉｃｕｌｔｙ ｏｆｔｈｅ ｍａｔｃｈｉｎｇ ｅｏｎｊｕｇａｃｙ ｓｅａｒｃｈ ｐｒｏｂｌｅｍ．Ａｎａｌｙｓｉｓ ｓｈｏｗｓ ｔｈａｔ ｔｈｅ ｐｒｏ－
ｏｐｓｅｄ ｓｃｈｅｍｅ ｓａｔｉｓｆｉｅｓ ｔｈｅ ｓｅｃｕｒｉｙｔ ｒｅｑｕｉｒｅｍｅｎｔｓ ｏｆ ｐｒｏｘｙ ｓｉｇｎａｔｕｒｅ ａｎｄ ｈａｓ ｈｉ ｇｈ ｃｏｍｐｕｔｉｎｇ ｅｆｉｆｃｉｅｎｃｙ ａｎｄ ａ ｓｈｏｒｔ ｓｉｇｎａｔｕｒｅ．
Ｋｅｙ ｗｏｒｄｓ：ｐｒｏｘｙ ｓｉｇｎａｔｕｒｅ；ｂｒａｉｄ ｇｒｏｕｐ；ｍａｔｃｈｉｎｇ ｃｏｎｊｕｇａｃｙ ｓｅａｒｃｈ ｐｒｏｂｌｅｍ；ｋｎｏｗｎ—ｓｉｎｇａｔｕｒｅ ｅｘｉｓｔｅｎｔｉａｌ ｆｏｒｇｅｒｙ
众所周知，目前公钥密码体制最典型的两类安全性假设为 …
，， 生成的有限表示的无限群。其生成元满足：
整数分解和离散对数的难解性。量子计算 的快速发展使 ｔｒｉｒｏ￣＝ （１ｉ一川≥２）
得目前的公钥密码体制面临严重威胁。为了抵抗已知量子算 ｒｏ ｏｒ ＋】ｏｒ ｏｒ ＋Ｊｏｒｌｏｒ ＋ｌ（１≤ ≤ｎ－２）
法的攻击，大量学者开始设计非基于数论的、基于非交换代数
辫群中的元素称为一个ｎ辫或辫元， 称为辫指数。当ｎ＝
的公钥密码体制。辫群的概念由Ａｒｔｉｎ 于１９４７年首次提出，
２时，Ｂ 为无限循环群，本文不予考虑。令ＬＢ ＲＢ 分别为生成
由于具有结构复杂、运算所需的时间和空间很小的特点，辫群
元ｏｒ１，ｒｏ２，…，ｏｒｌ，以Ｉ一１和ｏｒ【 Ｉ＋ｌ，ｏｒｌ，以ｊ＋２，…， 生成的子群，
成为了构造抗量子攻击公钥密码体制的新平台之一 。２００２
则对任意 ＬＢ ，｜ＢｅＲＢ ，有ｑＢ＝ 。对辫元Ｏ／，卢∈Ｂ ，如果存
年，Ｋｏ等人 首次将辫群用于构造签名体制。
在辫元ｓ使得 ＝ｓ～ＯｂＳ，则称 是共轭的，记做 ￣／３。
代理签名的概念是Ｍａｍｂｏ等人 于１９９６年提出的。在
这种数字签名中，一个被称为原始签名人的用户，可以将其数
定义２共轭判断问题（ＣＤＰ）。给定（ ，３／）∈Ｂ ×Ｂ ，判
字签名权力委托给另外一个被称为代理签名人的用户，使得在
断 一口是否成立。
需要的时候该代理签名人可以代替原始签名人产生有效的数
定义３共轭搜索问题（ＣＳＰ）。给定（ ，卢）∈Ｂ ×Ｂ 若
字签名。２００８年，Ｖｅｒｍａｌ 和张利利等人 分别基于辫群上的
存在ｓ使得ＪＢ＝ｓ～ ，求出至少一个这样的ｓ。
难解问题提出了代理签名体制，但随后的分析表明，Ｖｅｒｍａ体
定义４匹配共轭搜索问题（ＭＣＳＰ）。给定（ａ，卢，７）∈
制不能抵抗原始签名人改变攻击及代理签名人改变攻击 。
Ｂ ×Ｂ ×Ｂ ， ￣／３，求出一个６ＥＢ ，使得 ～６， ～ 。
２０１０年，黄文平等人 指出前面的攻击方法同样适用于文献
定义５求根问题（ＲＥＰ）。给定辫元 ＝ ｅ 及正整
［８］中的体制，并提出了新的代理签名体制。 数ｃ３２，求出满足卢＝ｙ 的辫元７。
本文对文献［８，１０］中的签名体制进行分析，指出这两种
１．２代理签名
体制都不能抵抗已知签名的存在性伪造攻击。针对这一问题，
一本文提出了一种新的代理签名体制。
个安全的代理签名体制应满足以下安全需求 ：
ａ）强不可伪造性。只有指定的代理签名人才能产生有效
１ 预备知识
的代理签名，原始签名人或未被指定为代理签名人的第三方都
不能产生有效的代理签名。
１．１辫群朋
ｂ）可验证性。验证人能够验证代理签名的有效性，并且根
定义１ 对自然数ｎ≥２，辫群曰 是由初等辫子ｏｒ ，
据代理签名的有效性确信原始签名人确实委托了代理人进行
收藕日期：２Ｏｌ１－０ｌ一１ｌ；修回日期：２０１ｌ ２０２—２２ 基金项目：国家自然科学基金资助项目（１０５０１０５３）
作者简介：隗云（１９８２一），女，湖北天门人，博士，ＣＣＦ会员，主要研究方向为密码协议的设计与分析（ｗｅｉｙｕｎ４５６＠ｓｏｈｕ．ｃｏｒｎ）；张兴凯（１９８１．），
男，助理工程师，硕士，主要研究方向为密码协议的设计与分析；熊国华（１９６３一），男，高级工程师，博士后，主要研究方向为密码与编码；穆灵
（１９７９一），女，助理工程师，硕士，主要研究方向为密码协议的设计与分析．
第９期
签名。
隗云，等：辫群上代理签名体制的分析与设计 ・３５２３・
个代理签名（ｔ 。，ｍ ，ＯＬ， ， ），他可以随机选择５∈Ｂ ，计算
＝ｃ）强可识别性。任何人都能根据代理签名确认其相应的
代理签名人身份。
ｄ）强不可否认性。一旦代理签名人代表原始签名人产生
了有效的代理签名，他就不能否认产生该代理签名的事实。
ｅ）防止滥用。代理签名人只能在代理授权范围内进行代
５ ５～，声＝ ～， ＝ ５～，得到一个新的代理签名（￡ 。，
ｍ ， ， ， ），因为声～ ， ～ ， ～ ｈ及 ～ｘｐｈ也成立。因
此，该签名体制不能抵抗已知签名的存在性伪造攻击。
３新的代理签名体制
３．１ 签名体制
理签名，而不能滥用其代理签名的权力。
２两种代理签名体制的分析
原始签名人和代理签名人分别记为Ａｌｉｃｅ和Ｂｏｂ， 。： 一
｛０，１｝ ， ：｛０，１｝ 一曰 为抗碰撞的杂凑函数，ｍ ｛０，１｝
为待签名的消息。
２．１ 文献［８】中签名体制的分析
１）密钥生成 Ａｌｉｃｅ随机选择 ，‰∈Ｂ ，计算ｙ。：
。。 。ｎ ，秘密保存。。作为私钥，（ 。，Ｙ０）为对应的公钥。Ｂｏｂ
的私钥ｏ 和公钥（ ，ｙ ）用类似方法产生。
２）授权Ａｌｉｃｅ计算ｔ。＝Ｏ，０ （ＩＤＰ）ａ０－ 并将ｔ。发送给
Ｂｏｂ，其中，ＩＤ 为Ｂｏｂ的身份信息。Ｂｏｂ验证ｔ。～ （ＩＤ ）及
￡。 ～ （ＩＤＰ） 。是否成立，若成立，接受ｔ。；否则，拒绝。
３）代理签名 Ｂｏｂ随机选择奇素数Ｃ，计算ｙ＝ｔ ，６：
。 Ｈ２（ｍ）ｏ ，则产生的代理签名为（ｃ， ，６）。
４）验证接收签名（ｃ，ｙ，占）后，验证人验证ｙ～ （Ｉ ）。，
ＹＹｏ～ （ＩＤ ） ‰，８～ （ｍ）及 一 （ｍ） 是否成立，若都
成立，接受签名；否则，拒绝。
作者声称该体制满足强不可伪造性，且除Ａｌｉｃｅ外的其他
攻击者要伪造签名面临求解辫群上的求根问题，而事实并非如
此。一旦Ａｌｉｃｅ得到关于消息ｍ的某个代理签名（ｃ， ，６），他
就能按如下方式产生一个新的有效代理签名：选择新的奇素数
ｃ ，并计算 ＝ ，则（ｃ ， ，６）满足 ～ （ＩＤ ） ， Ｙ０～
（ＩＤ ） 。，８～ （ｍ）及 ～ （ｍ） 。
对除Ａｌｉｃｅ外的其他攻击者，只要得到两个有效的代理签
名（ｃ ， ， ）和（ｃ ， ， ），无须计算求根问题就能求解ｔ。：
ｃ】，ｃ２都是素数，则存在整数ｄｌ、ｄ２满足Ｃ１ｄｌ＋Ｃ２ｄ２：１，攻击者
计算ｄ。和ｄ 后即可得到（ ，）ｄｌ（ ：）ｄ２：ｔ。。随后，攻击者也
能进行上述存在性伪造攻击。
２．２文献［１０】中签名体制的分析
１）密钥生成Ａｌｉｃｅ和Ｂｏｂ的私钥０。，０ ∈ＬＢ ，除此之外
其他参数同２．１节。
２）授权Ａｌｉｃｅ选择ｔ∈咫 ，计算 ＝ｔ％ｐｔ 及ｔ０＝００ｍ 口
① ｌ（饥ｚ ），并将（｜ｊ｝，ｔｏ，ｍ ）发送给Ｂｏｂ。Ｂｏｂ计算ｔ ０＝ｔｏ①
（ 。 ）并验证ｔ 。～ 是否成立，若成立，接受ｔ。；否则，
拒绝。
３）代理签名Ｂｏｂ随机选择６∈Ｂ ，计算ｈ＝ （ｍ ｌＩ ｍ），
＝６ ６～，』Ｂ＝ｂｈｂ～， ＝６ｏ ｈａ ｂ～，则产生的代理签名为
（ｔ ０，ｍ ， ，卢，ｙ）。
４）验证验证人计算ｈ＝ （ｍ ｌｌ ｍ），验证￡ ０ ～ｍ 。，
卢～ ， ～ｈ，ｑＢ～ｘｐｈ及 ～ 是否成立，若都成立，接受签
名；否则，拒绝。
从签名体制可知，一旦某个攻击者得到关于消息ｍ的某