第３８卷 Ｖ０１．３８ 第９期 ＮＯ．９ 计算机工程
Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ２０１２年５月
Ｍａｙ ２０１２
・安全技术・ 文章编号：１０ｏｏ—＿３４２８（２０ｌ２）０９－＿＿０１３ｌ—０３ 文献标识码：Ａ 中圈分类号｛ＴＰ３０９ 门限混合代理多重签名方案 王勇兵 （河北师范大学附属民族学院，石家庄０５００９１）
摘要：混合代理多重签名要求所有签名人共同产生签名，使方案的灵活性和实用性受限。针对该问题，通过引入门限签名，提出一个 （ｔ，ｎ）ｌ＇Ｊ限混合代理多重签名方案，在一个签名人组成的签名群中，只需ｆ个或ｔ个以上的签名人同意就可以完成签名。理论分析结果表明， 该方案满足不可伪造性、不可否认性、可鉴别性、混合代理多重签名性和门限签名性，且效率高于原方案。 关健词：数字签名；代理签名；代理多重签名；多重代理多重签名；混合代理多重签名；门限签名
Ｔｈｒｅｓｈｏｌｄ Ｈｙｂｒｉｄ Ｐｒｏｘｙ Ｍｕｌｔｉ－ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ ＷＡＮＧＹｏｎｇ－ｂｉｎｇ （Ｎａｔｉｏｎａｌｉｔｉｅｓ Ｃｏｌｌｅｇｅ，Ｈｅｂｅｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｉｊｉａｚｈｕａｎｇ ０５００９１，Ｃｈｉｎａ） ［Ａｂｓｔｒａｃｔ］Ｆｌｅｘｉｂｉｌｉｔｙ ａｎｄ ｐｒａｃｔｉｃａｂｉｌｉｔｙ ｏｆ ｈｙｂｒｉｄ ｐｒｏｘｙ ｍｕｌｔｉ—ｓｉｇｎａｔｕｒｅ ａｒｅ ｒｅｓｔｒｉｃｔｅｄ ｂｙｔｈｅ ｐｒｏｐｅｒｔｙ ｔｈａｔ ａｌｌ ｏｆ ｔｈｅ ｓｉｇｎｅｒｓ ｐｒｏｄｕｃｅ ｓｉｇｎａｔｕｒｅ ｔｏｇｅｔｈｅｒ．Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ（ｔ，ｎ）Ｔｈｒｅｓｈｏｌｄ Ｈｙｂｒｉｄ Ｐｒｏｘｙ Ｍｕｌｔｉ—ｓｉｇｎａｔｕｒｅ（ＴＨＰＭ）ｓｃｈｅｍｅ ｃｏｍｂｉｎｇ ｗｉｔｈ ｔｈｅ ｔｈｒｅｓｈｏｌｄ ｓｉｇｎａｔｕｒｅ．Ａ ＴＨＰＭ ｉｓ ｃｏｌｌａｂｏｒａｔｉｖｅｌｙ ｇｅｎｅｒａｔｅｄ ｂｙ ｓｏｍｅ ｏｒｉｇｉｎａｌ ｓｉｇｎｅｒｓ ａｎｄ ｓｏｍｅ ｐｒｏｘｙ ｓｉｇｎｅｒｓ ｏｎ ｂｅｈａｌｆ ｏｆ ｔｈｅｉｒ ｏｒｉｇｉｎａｌ ｓｉｇｎｅｒｓ ｉｎ ｔｈｅ ｓｃｈｅｍｅ．Ｏｎｌｙ ｗｈｅｎ ｔ ｏｒ ｍｏｒｅ ｔｈａｎ ｔ ｓｉｇｎｅｒｓ ａｇｒｅｅ，ｔｈｅ ｔｈｒｅｓｈｏｌｄ ｎｕｍｂｅｒ ｇｒｏｕｐ ｍｅｍｂｅｒｓ ｃａｎ ｐｒｏｄｕｃｅ ａ ｖａｌｉｄ ＴＨＰＭ ｉｎ ｔｈｅ ｓｉｇｎｉｎｇ ｇｒｏｕｐ．Ｔｈｅｏｒｅｔｉｃａｌ ａｎａｌｙｓｉｓ ｐｒｏｖｅｓ ｔｈａｔ ＴＨＰＭ ｎｏｔ ｏｎｌｙ ｈａｓ ｕｎｆｏｒｇｅａｂｉｌｉｔｙ，ｎｏｎｒｅｐｕｄｉａｂｌｉｔｙ，ｄｉｓｔｉｎｇｕｉｓｈａｂｉｌｉｔｙ ａｎｄ ｑｕａｌｉｔｙ ｏｆｈｙｂｒｉｄ ｐｒｏｘｙ ｍｕｌｔｉ—ｓｉｇｎａｔｕｒｅ ａｎｄ ｔｈｒｅｓｈｏｌｄ ｓｉｇｎａｔｕｒｅ，ｂｕｔ ａｌｓｏ ｉｓ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔ ｔｈａｎ ｏｒｉｇｉｎａｌ ｓｃｈｅｍｅ． ！Ｋｅｙ ｗｏｒｄｓ］ｄｉｇｉｔａｌ ｓｉｇｎａｔｕｒｅ；ｐｒｏｘｙ ｓｉｇｎａｔｕｒｅ；ｐｒｏｘｙ ｍｕｌｔｉ－－ｓｉｇｎａｔｕｒｅ；ｍｕｌｔｉ－ｐｒｏｘｙ ｍｕｌｔｉ・－ｓｉｇｎａｔｕｒｅ；ｈｙｂｒｉｄ ｐｒｏｘｙ ｍｕｌｔｉ－－ｓｉｇｎａｔｕｒｅ；ｔｈｒｅｓｈｏｌｄ ｓｉｇｎａｔｕｒｅ ＤＯｈ １０．３９６９／ｊ．ｉｓｓｎ．１０００—３４２８．２０１２．０９．０３９
ｌ概述 代理签名¨Ｊ作为一种特殊的数字签名体制，允许原始签 名人将签名权委托给指定的代理签名人行使，常用于原始签 名人由于某些原因无法行使签名的场合。代理签名广泛应用 于电子现金、电子投票和电子商务等领域，引起了人们极大 的关注。一般的代理签名往往考虑的是一个原始签名人和一 个代理签名人的特殊情形，比较理想化，不适合实际应用。 为了满足实际要求，代理多重签名［２－３］ 多重代理签名ｌ４ Ｊ和
多代理多签名 随即被提出。 在代理多重签名中，代理签名人可以代替多个原始签名 人生成有效的代理签名，它考虑的是所有原始签名人同时委 托签名权的庆幸，在实际生活中，可能只有一部分原始签名 人需要委托签名权，其他原始签名人现场参与签名。为此， 文献［７］提出一种混合代理多重签名方案，其中，每个原始签 名人都有指定的代理签名人，实际签名是由部分原始签名人 和部分代理签名人共同产生的。文献［８】基于双线性对提出了 一个新的混合代理多重签名方案，其中，部分原始签名人将 签名权委托给同一个代理签名人，代理签名由一个代理签名 人和部分原始签名人合作产生。但该方案有以下３个问题： （１）该方案是基于身份密码体制设计的，原始签名人和代理签 名人的密钥由可信中心托管，方案的安全性完全依赖可信中 心的诚实性和安全性，在开放的网络环境中是不可行的。 （２）签名长度与签名人数有关，在签名（ ，ｔｉｐ， ， ， ）中
和 是公开的，可以去掉，即使签名为（Ｕ，ｒ， ，‘尸， ）， 签名长度仍然与原始签名人和代理签名人的人数有关。（３）要 求参与签名的原始签名人和代理签名人一起合作才能产生有
效的代理签名，若有不合作的签名人，则签名将无法正常进 行，方案的灵活性和实用性受到限制。 针对以上问题，本文将门限签名引入混合代理多重签名 中，提出了一个（ｔ，ｎ）门限混合代理多重签名方案。该方案适 用于以下场合：在一个大公司有多个部门，每个部门都设有 部门经理，并且为了协调各部门业务的开展，另设部门协调 经理一名，当一部分部门经理出差时，便可以把签名权委托 给协调经理，文件由协调经理和其他不出差的部门经理共同 签署。由于对文件内容不满意，有些签名人可能拒绝签名， 这样，公司的正常运转必将受到影响。这时只需要一定数量 的签名人参与签名，文件就可以生效。 ２预备知识 ２．１双线性对映射 设ｇ是一个大素数，Ｇ１和Ｇ，分别为引喻加法循环群和乘
法循环群，尸为ｑ的生成元， ，ｂ∈ ｚ 。双线性对是一个映 射ｅ：ｑ ｘｑ ，具有如下性质： （１）双线性性：对任意的 ， ， ，Ｑ２∈Ｇｌ，有： Ｐ（ ＋ ， ）＝ （ ， ）Ｐ（ ， ） ｅ（ ， 十 ）＝ｅ（ ， ） （ ， ） （口 ，ｂＱ，）＝ （ ， ） （２）非退化性：存在尸，９∈ ，使得 （尸１Ｑ）≠１。
基金项目：河北省教育厅科研基金资助项目（Ｚ２０１１１５５）；河北师范 大学科研基金资助项目（Ｌ２０１０Ｑ１５） 作者倚介：王勇兵（１９８１一），男，讲师、硕士，主研方向：密码学 牧稿日期：２０１１－０８－３１ Ｅ—ｍａｉｌ：ｗｙｂ７２３＠ｙａｈｏｏ．ｃｏｒｎ．ｃｎ １３２ 计算机工程 ２０１２年５月５日 （３）可计算性：对所有的Ｐ，Ｑｅ ＧＩ，存在计算ｅ（Ｐ，Ｑ）的有 效算法。 ２．２复杂性假设 （１）离散对数问题（ＤＬＰ）：给定Ｐ，Ｑ∈Ｇｉ，找到一个整数 ｎ∈月ｚ：，满足Ｏ：ｎＰ。 （２）判定Ｄｉｆｉｅ—Ｈｅｌｌｍａｎ问题（ＤＤＨＰ）：对于口，ｂ，ｃＥ Ｚ：， 给定Ｐ，ａＰ，ｂＰ，ｃＰｅ ＧＩ，判定ｃ＝ａｂ是否成立。 （３）计算Ｄｉｆｆｉｅ・Ｈｅｌｌｍａｎ问题（ＣＤＨＰ）：对于ａ，ｂ∈月ｚ ， 给定Ｐ，ａＰ，ｂＰ∈ＧＩ，计算ａｂＰ。 ２．３ Ｓｈａｍｉｒ（ｔ，ｎ）门限秘密分享方案 一个（ｔ，ｎ）ｔ＇３限秘密分享方案是指把密钥 按照某种方式 分配给 个用户保存，使得一个用户中的ｔ个或ｔ个以上用户 一起合作可以恢复密钥５，而少于ｔ个用户不能得到密钥 的任何信息。方案过程如下： （１）选择大素数ｑ和一个ｔ－１次多项式： 厂（ ）＝ ＋ａｌｘ＋ａ２ｘ ＋…＋ａｔ一１ｘ卜 ｍｏｄｑ 其中，ｆ（Ｏ）＝ ；ａｉ∈Ｒ ｚ：（ｆ＝ｌ，２，…，ｔ一１）。 （２）分享密钥 ：设ｎ个用户的身份为ｘｉ（ｉ＝ｌ，２，…，ｔ一１）， 则每个用户的秘密份额为ｓ ＝ｆ（ｘｉ）ｍｏｄｑ。 （３）恢复密钥 ：ｔ个或ｔ个以上用户一起合作，就可以 利用Ｌａｇｒａｎｇｅ插值公式恢复 ：
， ｆ 一 ＝∑厂（ｔ）ｎ——Ｌｍｏｄｑ
， ’， ≠ ｔ一
３门限混合代理多重签名方案 本文方案的参与方包括：Ｇ ＝｛４， ，…，４＋ ｝为ｌ＋ｍ个 原始签名人组成的集合，Ｇ ：｛ＡＩ， ，…，４｝为，个需要委托 授权的原始签名人集合，ＧＡ ＝｛４ ，…， ）为ｍ个实际 参与签名的原始签名人集合，曰为Ｇ 的代理签名人， 为 签名验证人。整个方案由系统初始化阶段、代理授权阶段、 签名密钥生成阶段、签名生成阶段和签名验证阶段。 ３．１系统初始化阶段 设群Ｇｌ是阶为大素数ｑ、生成元为Ｐ的循环加群。群
是阶为ｑ的循环乘法群。定义双线性对映射ｅ：ＧｌｘＧｌ Ｇ２。 Ｈ ：｛０，１｝ ＇÷Ｇ１是一个安全的单向ｈａｓｈ函数。原始签名人４ ：ｌ，２，…，ｌ＋ｍ）选择私钥 ｚ；，并计算公钥 ＝ Ｐ， 其身份信息为 ；代理签名人Ｂ选择私钥ｘ ∈ ｚ：，并计算 公钥 ＝ｘＢＰ，其身份信息为 。 ３．２代理授权阶段 假设ｗｉ（ｉ＝１，２，…，ｚ）是原始签名人４（ｊ．＝１７２，…，ｚ）给代理 签名人 的授权证书，其中包括４（ １７２，…，，）和 的身份信 息、代理权限和代理期限等信息。授权协议如下： （１）原始签名人４（ｉ＝ｌ，２，…，，）随机选择Ｉ∈ｚ：，计算
Ｒｉ：ｒｉＰ，ＳＡ，＝
（Ｉ＋ ）日 （ ），公开 和Ｒｉ，并通过安全信
道将Ｓ 发送给代理签名人Ｂ。 （２）代理签名人Ｂ收到 后验证： Ｐ（ ，Ｐ）＝ｅ（ ， （ ） Ｐ（Ｈ１（ ， ）） 是否成立，若等式成立，则通过验证，然后计算代理密钥：
＝∑ Ｈｉ（ ｌＪ．．・ｆ ） ＿一 公开代理公钥 ＝卯。
３．３签名密钥生成阶段 记 ＝ｍ＋ｌ，设ｍ个实际参与签名的原始签名人 和 代理签名人 组成的签名群为Ｓ：｛ ， ，…， ｝。并记 ：ｘ４．】， ＝ ∥…， 一 ＝ ＝ 。签名密钥生成的具体 步骤如下： （１）签名人 随机选择 ∈ｚ：，计算并广播 Ｊｐ。
（２） 计算屈＝ ＋ ，并随机选择ｔ－１次多项式： （ ）＝ ＋ａｉ１ ＋ｑ２ ＋・・・＋ａｉｔ—ｌｘ卜 ｍｏｄｑ 其中，ａｉｌ∈ ｚ：（，＝１，２，…，ｔ－１）。然后计算并公开Ａｕ＝ａｕＰ。 （３） 计算 （ ，）并通过安全信道发送给Ｄ，（ ≠ｉ）。 （４） 收到ｆｊ（ＩＤｉ）后，验证ｆｊ（ＩＤ￣）Ｐ＝ ，若验证 通过，则计算签名密钥ｃｉ＝羔ｆｊ（，Ｄ），并公开签名公钥 ＝ｃｉＰ。 ３．４签名生成阶段 设待签的消息为ｍ，签名群Ｓ＝ ， ，…，Ｓ ）中任意ｆ个 签名人对消息ｍ进行签名的过程如下：
（１）签名人 计算 ＝， － ＩＤｊ ，并计算部分签名