２０１２年５月 计算机工程与设计 Ｍａｖ ２Ｏ１２ 第３３卷第５期 ＣＯＭＰＵＴＥＲ ＥＮＧＩＮＥＥＲＩＮＧ ＡＮＤ ＤＥＳＩＧＮ ＶｏＬ ３３ Ｎｏ．５ 基于身份的可验证门限数字签名方案 李 曦，王晓明，程娜 （西华大学数学与计算机学院，四川成都６１Ｏ０３９） 摘要：在分析现有门限签名和可验证秘密共享的基础上，提出了一种基于身份的可验证秘密共享方法。并针对目前基于 离散对数和椭圆曲线的门限签名系统安全性不高、且实现效率低、难以应用到拥有大规模成员的系统中的问题，利用基于 身份的可验证秘密共享方法，提出了一种基于身份的可验证门限签名方案。该签名方案充分考虑了门限签名的实现效率， 避免了复杂计算，并能有效抵抗密钥恢复攻击、方程攻击、合谋攻击、假冒攻击等常见的攻击。 关键词：公钥密码；基于身份的密码体制；门限数字签名；可验证秘密共享；双线性配对 中图法分类号：ＴＰ３０９ 文献标识号：Ａ 文章编号：１０００—７０２４（２０１２）０５—１７４２—０４ Ｓｅｃｕｒｅ ｔｈｒｅｓｈｏｌｄ ｖｅｒｉｆｉａｂｌｅ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ ｂａｓｅｄ ｏｎ ｉｄｅｎｔｉｔｙ ＬＩ Ｘｉ，ＷＡＮＧ Ｘｉａｏ－ｍｉｎｇ，ＣＨＥＮＧ Ｎａ （Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉｈｕａ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ ６１００３９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｆｔｅｒ ａｎａｌｙｚｉｎｇ ｔｈｅ ｐｒｅｓｅｎｔ ｔｈｒｅｓｈｏｌｄ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅｓ ａｎｄ ｖｅｒｉｆｉａｂｌｅ ｓｅｃｒｅｔ ｓｈａｒｉｎｇ（ＶＳＳ）ｍｅｔｈｏｄｓ，ａｎ ｉｄｅｎｔｉｔｙ ｂａｓｅｄ ｏｎ ＶＳＳ ｍｅｔｈｏｄ ｉｓ ｐｒｏｐｏｓｅｄ．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｏｓｅ ｐｒｏｂｌｅｍ ｔｈａｔ ｍｏｓｔ ｏｆ ｐｒｅｓｅｎｔ ｔｈｒｅｓｈｏｌｄ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅｓ ｂａｓｅｄ ｏｎ ｄｉｓ— ｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ ａｎｄ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｄｉｆｆｉｃｕｌｔ ｔＯ ａｐｐｌｙ ｔＯ ｔｈｅ ｓｙｓｔｅｍ ｗｉｔｈ ｌａｒｇｅ－ｓｃａｌｅ ｍｅｍｂｅｒｓ ｂｅｃａｕｓｅ ｏｆ ｌｏｗ ｅｆｆｉｃｉｅｎｃｙ ａｎｄ ｓｅｃｕｒｉｔｙ， ａ ｎｅｗ ｉｄｅｎｔｉｔｙ－ｂａｓｅｄ ｔｈｒｅｓｈｏｌｄ ｖｅｒｉｆｉａｂｌｅ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ ｕｓｉｎｇ ＶＳＳ ｉｓ．ｐｒｏｐｏｓｅｄ．Ｔｈｅ ｎｅｗ ｓｃｈｅｍｅ ａｖｏｉｄｓ ｔｈｅ ｃｏｍｐｌｅｘ ｍａｔｈｅ— ｍａｔｉｃａｌ ｃｏｍｐｕｔａｔｉｏｎｓ ａｎｄ ｉｓ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔ．Ｔｈｅ ｓｃｈｅｍｅ ｉｓ ｐｒｏｖｅｄ ｔｏ ｂｅ ｅｆｆｅｃｔｉｖｅ ａｇａｉｎｓｔ ｓｏｍｅ ｃｏｍｍｏｎ ａｔｔａｃｋｓ ｓｕｃｈ ａｓ ｋｅｙ ｒｅｃｏｖｅｒｙ ａｔｔａｃｋｓ，ｅｑｕａｔｉｏｎ ａｔｔａｃｋｓ，ｃｏｌｌｕｓｉｏｎ ａｔｔａｃｋｓ，ｉｍｐｅｒｓｏｎａｔｉｏｎ ａｔｔａｃｋｓ ａｎｄ ＳＯ ｏｎ． Ｋｅｙ ｗｏｒｄｓ：ｐｕｂｌｉｃ ｃｒｙｐｔｏｇｒａｐｈｙ；ｉｄｅｎｔｉｔｙ－ｂａｓｅｄ ｃｒｙｐｔｏｇｒａｐｈｙ；ｔｈｒｅｓｈｏｌｄ ｓｉｇｎａｔｕｒｅ；ＶＳＳ；ｂｉｌｉｎｅａｒ ｐａｉｒｉｎｇｓ ０引 言 种门限签名，组成员各自选择私钥并协商产生公钥。文献 Ｅ６３主要针对在门限签名中如何安全的进行秘密共享以及 门限签名采用秘密共享的方法来实现。当各个成员出 分布式产生密钥等问题，采用分布式密钥产生协议提出了 示子密钥后用一定的方法可以恢复出签名密钥，而其它成 双线性配对门限签名方案。随后，文献ＥＴ］在文献［６］ 员无法从计算上恢复出该密钥。密钥共享协议将秘密信息 的基础上，提出了一种基于身份的无密钥托管门限签名方 进行分散管理，极大的减小了成员受到攻击而导致秘密信 案，由多个签名成员分布式产生部分签名，然后集中产生 息泄露的概率，减少了持有秘密信息的成员的责任，同时 完整签名。上述门限签名方案在性能方面未作充分考虑， 还降低了攻击者破译秘密信息的成功率¨１］。 无论签名产生、还是签名校验，都需要大量计算，很难应 学者们对门限数字签名进行了不断的深入研究，使之 用到具有大规模成员的系统中。文献Ｅ８］提出一种基于身 得到发展和应用。文献Ｅ２］提出了一种分布式门限签名方 份的门限签名方案，但该方案没有考虑秘密共享的可 案，其中包括基于离散对数提出分布式密钥生成、校验、 验证性。 更新协议，但该方案无法抵抗合谋攻击和内部伪造攻击Ｅ 。 本文在基于身份的密码体制基础上提出了一种可验证 基于秘密共享协议，文献Ｅ３３通过改进文献Ｅ４３中的离 （ｔ，ｎ）门限签名方案，该方案满足可验证秘密共享的要 散对数门限签名方案，利用重构哈希码进行签名校验，使 求：每个成员即可以对密钥分发者及所分发的子密钥进行 之能够抵抗上述攻击。文献Ｅｓ］基于Ｅｌｇａｍａｌ系统提出一 验证，同时任意构造完整门限签名的成员也可以对每个成 收稿日期：２０１１－０５—０６；修订日期：２０１１－０７—２５ 基金项目：ｌ￣Ｊｌ［省教育厅青年基金项目（１０ＺＢ０８２）；西华大学校重点科研基金项目（Ｚ１０２２６１５）；四Ｊｉｌ省计算机软件与理论重点学科基金 项目（ＳＺＤ０８０２—０９—１） 作者简介：李曦（１９８１一），女，湖北应城人，博士，讲师，研究方向为网络与信息安全；王晓明（１９７７一），男，四川简阳人，博士，讲 师，研究方向为人工智能与模式识别；程娜（１９８２一），女，四川双流人，博士，讲师，研究方向为泛函分析。Ｅ－ｍａｉｌ：ｌｉｘｉｌ３＠ｇｍａｉｌ．ｃｏｉｎ 第３３卷第５期 李曦，王晓明，程娜：基于身份的可验证门限数字签名方案 Ｑ —Ｈ１（ Ｄ）为成员Ｐ９的公钥。Ｐｆ，收到ｓ 的值后， 验证式（３）是否成立 员的子密钥进行验证。此外，列举了本方案抵抗以下几 种常见的攻击的情况：密钥恢复攻击、方程攻击、合谋 攻击、假冒攻击。本方案在保证安全性的前提下，极大的 降低了门限签名的计算量，提高了签名生成、签名校验 的效率。 ８（Ｐ，ｓ毒 ）一Ｐ（Ｐ ，Ｑ。） ．（３） 若式（３）成立，则成员Ｐ ，的私钥即为ｓ ；否则， 成员Ｐ．向ＫＧＣ返回错误信息。密钥分发之后，ＫＧＣ不再 １基于身份的可验证（ｔ， ）门限数字签名方案 定义１（双线性配对）Ｇ１、Ｇ２分别为 阶加法群、乘 参与方案的密码过程。 验证成员私钥的式（３）证明如下 ｅ（Ｐ，ｓ ）一ｅ（Ｐ，ｆ（ｉｊ）ＱＤ） 法群， 为大素数，Ｐ是Ｇ 的一个生成元。双线性对ｅ： Ｇ１×Ｇ１一Ｇ２满足条件： （１）双线性性：Ｖ Ｐ ，Ｐｚ，Ｐ，Ｑ１，Ｑ，Ｑ∈Ｇ１，有 ｅ（Ｐ１＋Ｐ２，Ｑ）一ｅ（Ｐ１，Ｑ）ｅ（Ｐ２，Ｑ） ｅ（Ｐ，Ｑ１＋Ｑ）一ｅ（Ｐ，Ｑ１）ｅ（Ｐ，Ｑ２） Ｖａ，ｂＥＺ ，Ｖ Ｐ，Ｑ∈Ｇ１，有 ｅ（口Ｐ，ｂＱ）一ｅ（Ｐ，Ｑ） ｅ（一Ｐ，Ｑ）一ｅ（Ｐ，～Ｑ）一ｅ（Ｐ，Ｑ）＿１ （２）非退化性：ｊ Ｐ，Ｑ∈Ｇ１，满足ｅ（Ｐ，Ｑ）≠１， 其中１为Ｇ２的单位元。 （３）可计算性：对于ＶＰ，Ｑ∈Ｇｌ，存在高效的算法能 计算出ｅ（Ｐ，Ｑ）。 １．１系统建立 设Ｅ是定义在有限域 上的椭圆曲线，密钥生成中心 ＫＧＣ（ｋｅｙ ｇｅｎｅｒａｔｉｏｎ ｃｅｎｔｅｒ）在Ｅ（Ｆ０）中选择一个加法 群Ｇ１和一个乘法群Ｇ２，阶均为大素数，ｚ，其中Ｐ为Ｇ 的 生成元。令ｅ：Ｇｌ×Ｇｌ—Ｇ２为一个双线性配对。 ＫＧＣ随机选择一个组数ａ０，＆１，ａ２…．，ａＨ∈ ， 计算Ｐ脚＝ａ。Ｐ。建立￡一１次多项式方程 厂（ｚ）一（以ｏ＋口１ｚ＋口２Ｉｚ。＋…＋吼一１ｚ ）ｍｏｄｑ 对于 一１，２…．，ｎ，１≤￡≤ ，１≤ ≤ ，设Ａ表示多 个发送者的集合，其中Ａ一｛Ｐ１，Ｐ２…．，Ｐ ）。Ｂ∈Ａ是 发送者集合中的一个签名组成员集合，其中Ｂ一｛Ｐ Ｐｆ２，…Ｐ ）。ＫＧＣ计算Ｐ 一ｆ（ｉｉ）Ｐ，并向成员ｐ，广 播，其中ＩＤ为成员组的公开身份码。每个Ｐ，．成员收到广 播信息后验证式（１）是否成立。 ∑Ｌ Ｐ ’一 （１） ＝１ 式中：Ｌ ——拉格朗日系数。若式（１）不成立，则成员 Ｐ拒绝来自ＫＧＣ的消息，并返回错误信息。 １．２密钥生成和分发 令组成员 的系统私钥为ｆ（Ｏ）一ａｏ，组成员Ｐ 的 系统公钥则为 —ｆ（Ｏ）Ｐ—ａ。Ｐ。ＫＧＣ选择两个公开的 单向抗强碰撞Ｈａｓｈ函数：Ｈ ：｛０，１） 一Ｇ】和Ｈ２：｛０， １） 一Ｚ０。ＫＧＣ作为可信任的分发者，计算成员私钥 ｓ 一ｆ（ ）ＱＩＤ （２） 并通过安全的通道分发给每个组成员Ｐ，，其中， 一ｅ（ｆ（ｉｊ）Ｐ，ＱＤ）一Ｐ（Ｐ ，Ｑ皿） 上述参数如表１所示。 表１本方案中的参数 １．３部分签名生成 设签名成员组Ｂ一｛Ｐｉ ，Ｐ …Ｐｉ，）中是参与数字签名 的ｔ个成员。每个签名成员Ｐ （１≤ ≤￡）随机的选取ｋ ∈ ，并计算 和ｒＪ的值，其中 Ｍ｜一ｋｉＰ幽 ｒｊ＝ｋｉＹｉ 每个签名成员Ｐｔ通过安全的通道，向其他（￡一１）个 签名成员发送（ ， ）。当签名成员Ｐ ．收到所有其他成 员发送来的（ ，ｒＪ）后，计算 “一∑ （４） Ｊ＝ｉ ｒ一∑ （５） Ｊ １ 一Ｈ２（“，ｒ， （６） 一Ｌ。（Ｐ ＋ ’）ｍｏｄｑ （７） 签名成员Ｐｆ对消息Ｍ产生的部分数字签名为 一 （ ， ）。 １．４完整门限签名生成 签名组Ｂ一｛Ｐ Ｐ …Ｐ ）中任意一个成员均可以 构造完整的门限签名。这名构造完整门限签名的成员收到 所有签名成员的部分签名后，首先验证每个部分签名的有 效性 ８（ ，Ｐ）一ｅ（Ｐ＋ｈＱ￣Ｄ，Ｐ ） ， （８） 若式（８）成立，则 一（ ， ）作为成员Ｐ． 的有 效签名被接受。设所有成员的部分签名均被验证有效，则 构造完整门限签名的成员计算 “一∑ ； 一∑ 一（“， ）即为消息Ｍ的完整门限数字签名。 计算机工程与设计 １．５门限签名校验 ２０１２往 未知的参数数量也成倍数增加；未知参数的数量总是远远 大于攻击者所获得的有效方程的数量，因此本方案能抵抗 方程恢复攻击。 （９） 接收者收到 一（ ， ）后，对门限数字签名进行校 验，验证式是否成立 ｅ（ ，Ｐ）一ｅ（Ｐ＋＾ＱＤ，Ｐ脚） ２．３合谋攻击 其中，ｈ＝Ｈ （Ｍ， ）。若式（９）成立，则门限数字签名 正确，否则门限数字签名不正确。 验证部分签名的式（８）证明如下 Ｂ集合中任意不大于（ｔ一１）名的成员合谋，试图通 过重构多项式ｆ（ｚ）来获取系统密钥ｆ（ｏ）和其他成员的 私钥ｓ 是困难的。根据拉格朗日插值多项式定理，若已 知ｔ个或更多签名成员的秘密参数厂（ＩＤ），那么（ｔ一１） 次多项式ｆ（ｚ）则由下式唯一确定 ｇ（ ，Ｐ）一ｅ（Ｌｉｊ（Ｐ ＋ ｓ≥ ），Ｐ） 一ｅ（Ｌ，ｐ （ｉｊ），Ｐ）ｔ（Ｌ ， ｓ≥ ，Ｐ） 一ｅ（Ｌｉｊｆ（ＩＤｉｊ）Ｐ，Ｐ）ｅ（Ｌｉ￣ｈｆ（ＩＤｉｊ）Ｑ皿，Ｐ） 一ｅ（Ｌ￣ｉＰ，ｆ（ＩＤｉｉ）Ｐ）ｅ（ＬｉｊｈＱｍ，ｆ（ＩＤ￣ｊ）Ｐ） 一ｇ（Ｌ，Ｐ，Ｐ ）ｅ（Ｌ ｈＱ∞，Ｐ ’） 一 ）一￣ｓ（ＩＶ ， Ｘ－１Ｅｌｌｋ 因此不大于（ｔ一１）名的成员合谋无法重构多项式， （ｚ），故而无法得到系统密钥和其他成员的私钥。该方案能 抵抗合谋攻击。 ２．４假冒攻击 （Ｌ。Ｐ＋Ｌ＿ｈＱ。，Ｐ （ｉｊ ）一８（Ｐ＋ｈＱｍ，Ｐ ’） 。 验证门限签名的式（９）证明如下 一∑ 一∑（Ｌ ，（Ｐ ＋ ≥’）） Ｊ一１ Ｊ一１ 假冒攻击可能有以下３种情形： （１）攻击者试图假冒某签名成员Ｐ．。即使攻击者截 获了其他签名成员发送给Ｐ，的消息，从中获取了 和ｒ 值，其中１≤点≤ ，是≠ ，但由于签名成员Ｐ 。的私钥ｓ 未知，因此攻击者无法通过方程（７）生成Ｐ．的签名（ ， ｒ，）。故攻击者假冒某签名成员ＰＩ 是不可行的。 （２）攻击者试图通过选择性明文消息Ｍ，伪造一个满 足方程（９）的有效门限签名（“， ）。要构造一个满足方 一Ｌ。Ｐ ＋Ｅ Ｌ￣ｊｈＳ（Ｉ 一Ｐ脚＋ 皿 Ｌｉｔｆ（ＩＤｉ￣） Ｊ一１ Ｐ（ｚＪ，Ｐ）一 （Ｐ ＋ ∞∑Ｌ５ｆ（６），Ｐ） 一ｇ（Ｐ ，Ｐ）ｅ（ ｍ∑Ｌ ，厂（ ），Ｐ） Ｊ一１ 一Ｐ（Ｐ ，Ｐ）Ｐ（ｈＱ肋，∑Ｌｉｉｆ（ｉ ）Ｐ） Ｊ＝ｌ 程（９）的有效门限签名，攻击者随机选择“和ｒ，需要找 到一个使方程（９）的成立的 ，是困难的；或者攻击者随 —ｅ（ＰＭ，Ｐ） （ｈＱｆＤ，∑Ｌ Ｐ２ ） Ｊ—ｌ —Ｐ（Ｐｐ．ｂ，Ｐ）Ｐ（五ＱＤ，Ｐ ）一 （Ｐ＋ ＱⅢ，Ｐ ） 机选择Ｕ和 ，需要找到一个使方程（９）的成立的ｒ，同 样是困难的。因为若采用上述方法，攻击者面临破解单向 Ｈａｓｈ函数问题（虽然已有方法在一定条件下破解Ｈａｓｈ函 数，但本方案基于随机预言模型，假设Ｈａｓｈ函数无法破 ２安全性分析 ２．１密钥－ｌ荻复攻击 攻击者试图通过某签名成员的ｍ 及其公钥Ｑ毋，获 解）。故攻击者伪造门限签名（“， ）是不可行的。 （３）攻击者试图利用两个有效的门限签名来获取系统 取该成员的私钥ｓ 是困难的。因为系统多项式－厂（ｚ）是 秘密的，攻击者无法通过式（２）得到签名成员的私钥。同 密钥ｆ（Ｏ）。若攻击者已知系统密钥ｆ（Ｏ），那么攻击者能 够伪造任意消息的门限签名。令（蚴，Ｖ ）和（“。， ）是 分别是对应消息Ｍ 和Ｍ２的两个有效签名。此时，攻击者 需要获得上述两个门限签名中的ｎ和ｒ２两个参数的值 一理，攻击者试图通过签名组的公钥 恢复出系统私钥厂 （Ｏ）是困难的。 ２．２方程攻击 攻击者试图通过某签名成员产生的部分签名ｖ，，由方 程（７）得到该成员的私钥ｓ 是困难的。若给定一个消 息Ｍ，以及某签名成员对此消息的部分签名ｖ，，攻击者无 法从方程（７）计算获得私钥ｓ ，因为方程（７）还有两 Ｌ Ｐ ＋Ｈ２（ Ｍ１）・∑ ｓ ｍｏｄｑ ＬｚＰ ４－Ｈｚ（Ｕ２￣ｔ＂２ ）’ ｓ ｍ。ｄｑ 一由上述两个式子得到方程 ｆ１ 个参数未知： 一Ｈｚ（“，ｒ，Ｍ）中的“和ｒ。攻击者虽然 可以获得某个已攻破签名成员的“ 和ｒ，值，但无法获得其 他所有签名成员的 和 值，其中１≤愚≤ｔ，忌≠ 。由式 （４）和式（５）知，攻击者无法获得参数Ｕ和ｒ的值，因此 研一 一Ｈ （“ ，ｎ，Ｍ）・∑Ｌ ｓ ’＋ ｆ２ Ｈ （Ｕ２￣ｒ２ Ｍ２）‘ ｓ （１Ｏ） 攻击者无法计算出成员的私钥ｓ 。而且，随着攻击者用 来破解私钥的消息和部分签名数量的增加，那么攻击者所 方程（１０）中有４个未知参数：ｒ 、ｒ２、参与消息Ｍ１ 签名的所有成员的私钥ｓ （１≤ ≤ ）、参与消息 签 第３３卷第５期 名的所有成员的私钥５ 李曦，王晓明，程娜：基于身份的可验证门限数字签名方案 （１≤ ≤ｆ２），求解方程（１ｏ）是 的运算。本文所提方案在部分签名产生、部分签名校验、 门限签名产生、门限签名校验４个阶段均避免了幂指 数运算。 （３）在门限签名产生阶段，在保证安全性的基础上， 困难的。而且，随着攻击者用来破解密钥的消息和签名数 量的增加，攻击者所未知的参数数量也成倍数增加；未知 参数的数量总是远远大于攻击者所获得的有效方程的数量。 故攻击者利用有效门限签名来获取系统密钥是不可行的。 本文所提方案仅用加法产生门限签名，避免了计算量很大 将这种情况扩展，容易证明本方案能抵抗明文攻击。 综上所述，本方案能抵抗假冒攻击。 ３性能分析 本方案中签名所涉及的主要运算包括：幂指数、乘法、 求逆、哈希、异或、加法、取模、配对。由于哈希、异或、 加法、取模这３种运算的运算速度比其他运算的速度快得 多，因此，在作性能比较时，元素的上述运算均忽略不计， 仅考虑幂指数、乘法、配对、求逆４种计算量较大的运算。 本文所提出的门限签名方案将分别与文献［６］、文献［９］、 文献［１Ｏ］、文献［１１］、文献Ｅ１２］中所提出的几种典型 的门限签名方案进行比较，如表２所示。其中，Ｐ表示配 对运算；Ｅｘｐ表示幂指数运算；Ｍｕｌ表示乘法运算；Ｉｎｖ表 ㈣ ㈣咖９ ８ ７ ６示求逆运算；ｒｔ表示成员总数；ｔ表示 个成员中的门 限个数。 表２门限签名方案性能比较 本文所提出的基于身份的可验证（ｔ，”）门限数字签 名方案在性能上有以下优点： （１）在一个（ ， ）门限数字签名方案中，要在ｔ个成 员中分布式的产生部分签名，这个一个比较耗时的过程。 而在所有的运算当中，双线性配对运算是最耗费计算资源 和计算时间的。本文所提方案避免了在每个签名成员产生 部分签名这个阶段的配对运算，大大减少了签名成员的 计算量。 （２）在有限域中，幂指数运算也是一个耗时、耗资源 的幂指数、乘法、配对、求逆计算。 （４）在保证安全性的基础上，无论在门限签名的每个 阶段中，还是在签名总计算量上，本文尽量减少复杂运算、 提高签名效率来设计门限签名方案。 与其它几种典型的门限签名方案相比，本文所提方案 的门限签名总计算量随着门限成员数ｔ的增加优势越明显， 如图１所示。本文以国际通常约定的换算标准，将其它运 算换算成乘法运算来衡量总计算量ｌ＿１ 。 蜮 ㈣ ５ ４ 划 ３ ２ 咖０ 门限成员数ｔ 二妻禁 一文献［９］—文献】＝妻藤［ １ 。１ｊ 二紊嬖 １一本文 图１ 门限签名总计算量比较 在上述的性能分析中，若采用预计算，将与被签名消 息无关的数据预先计算，则可以进一步提高签名效率。 ４结束语 本文提出了一种基于身份的可验证门限（ｔ， ）签名 方案，该方案满足可验证秘密共享的要求，既能对密钥分 发者及所分发的子密钥进行验证，同时也能对每个成员的 子密钥进行验证。在保证安全性的基础上，所提方案避免 了在每个签名成员产生部分签名这个阶段的配对运算，大 大减少了签名成员的计算量；在部分签名产生、部分签名 校验、门限签名产生、门限签名校验４个阶段均避免了幂 指数运算；仅用加法产生门限签名，避免了计算量很大的 幂指数、乘法、配对、求逆计算；无论在门限签名的每个 阶段中，还是在签名总计算量上，设计时尽量减少复杂运 算。通过理论及数据分析，本文所提出的方案与其它几种 典型的门限签名方案相比，性能更优。 参考文献： ［１］ＨＡＲＮ Ｌ，ＬＩＮ Ｃ．Ａｕｔｈｅｎｔｉｃａｔｅｄ ｇｒｏｕｐ ｋｅｙ ｔｒａｎｓｆｅｒ ｐｒｏｔｏｃｏｌ ｂａｓｅｄ ｏｎ ｓｅｃｒｅｔ ｓｈａｒｉｎｇ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ， ２０１０，５９（６）：８４２－８４６． （下转第１８５６页） ・ １８５６ ・ 计算机系统，２００９，３０（８）：１６６３—１６６７．］ 计算机工程与设计 ２０１２正 付青，等．一种改进的人工鱼群算法［Ｊ］．计算机工程， ２００８，３４（１ｏ）：１９２—１９４．Ｊ ［７］Ｑｕ ＬＤ，ＨＥ ＤＸ．Ｎｏｖｅｌ ａｒｔｉｆｉｃｉａｌ ｆｉｓｈ－ｓｃｈｏｏｌ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｈａｏｓ ｓｅａｒｃｈ［Ｉ３．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１０，４６（２２）：４０—４２（ｉｎ Ｃｈｉｎｅｓｅ）．［曲良东，何登旭．一种 混沌人工鱼群优化算法［Ｊ］．计算机工程与应用，２０１０，４６ ［ｕ］ＦＡＮ ＹＪ，ＷＡＮＧ ＤＤ，ＳＵＮ ＭＭ．Ｉｍｐｒｏｖｅｄ ａｒｔｉｆｉｃｉａｌ ｆｉｓｈ－ ｓｃｈｏｏｌ ａｌｇｏｒｉｔｈｍ口］．Ｊｏｕｒｎａｌ ｏｆ Ｃｈｏｎｇｑｉｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉ— ｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ），２００７，２４（３）：２３—２６（ｉｎ Ｃｈｉ— （２２）：４０—４２．］ Ｅ８］ＷＡＮＧ ＭＷ，ＴＡＯ ＨＬ，ＸＩＯＮＧ ＸＹ．Ａ Ｃｏｌｌａｂｏｒａｔｉｖｅ ｆｉｌｔｅ— ｒｉｎｇ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｉｔｅｒａｔｉｖｅ ｂｉｄｉｒｅｃｔｉｏｎａｌ ｎｅｓｅ）． ［范玉军，王冬冬，孙明明．改进的人工鱼群算法 ＿Ｊ］．重庆师范大学学报（自然科版），２００７，２４（３）： ２３—２６．］ Ｂｅ］ＬＩ ＤＹ，ＤＵ Ｙ．Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ ｗｉｔｈ ｕｎｃｅｒｔａｉｎｔｙ［Ｍ］． Ｃｈａｐｍａｎ＆Ｈａｌｌ／ＣＲＣ Ｔａｙｌｏｒ＆Ｆｒａｎｃｉｓ Ｇｒｏｕｐ，２００８． ｃｌｕｓｔｅｒｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ， ２００８，２２（４）：６１—７４（ｉｎ Ｃｈｉｎｅｓｅ）．［王明文，陶红亮，熊小 勇．双向聚类迭代的协同过滤推荐算法［Ｊ］．中文信息学报， ２００８，２２（４）：６１—７４．Ｊ Ｅ１３］Ｌｅｅ Ｊ Ｓ，Ｊｕｎ Ｃ Ｈ，Ｌｅｅ Ｊ，ｅｔ ａ１．Ｃｌａｓｓｉｉｆｃａｔｉｏｎ－ｂａｓｅｄ ｃｏｌｌａｂｏ— ｒａｔｉｖｅ ｆｉｌｔｅｒｉｎｇ ｕｓｉｎｇ ｍａｒｋｅｔ ｂａｓｋｅｔ ｄａｔａ＿Ｊ］．Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ，２００５，２９（３）：７００—７０４． Ｅ９］ＷＡＮＧ ＨＹ，ＺＨＡＮＧ ＹＧ．Ａｎ ｉｍｐｒｏｖｅｄ ａｒｔｉｆｉｃｉａｌ ｆｉｓｈ－ｓｗａｒＩｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｓｏｌｖｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｎａｌｙｓｉｓ ｐｒｏｂｌｅｍ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ，２０１０，２０（３）：８４—９１（ｉｎ Ｃｈｉ— ［１４］Ｐａｐａｇｅｌｉｓ Ｍ，Ｐｌｅｘｏｕｓａｋｉｓ ｎ Ｑｕａｌｉｔａｔｉｖｅ ａｎａｌｙｓｉｓ ｏｆ ｕｓｅｒ ｂａｓｅｄ ａｎｄ ｉｔｅｍ－ｂａｓｅｄ ｐｒｅｄｉｃｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ｎｅｓｔ）．［王会颖，章义刚．求解聚类问题的改进人工鱼群算法 ［Ｊ］．计算机技术与发展，２０１０，２Ｏ（３）：８４—９１．］ Ｅ１ｏ］ｗＡＮＧ ＬＧ，ＨＯＮＧ Ｙｉ，ＺＨＡＯ ＦＱ，ｅｔ ａ１．Ｉｍｐｒｏｖｅｄ Ａｒｔｉｆｉ— ａｇｅｎｔｓ［Ｊ］．Ｅｎｇｉｎｅｅｒｉｎｇ Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉ— ｇｅｎｃｅ，２００５，１８（７）：７８１—７８９． ［１５］Ｍｉｎ Ｓ Ｈ，Ｈａｎ Ｉ．Ｄｙｎａｍｉｃ ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ｆｏｒ ｒｅｃｏｍｍｅｎｄｅｒ ｃｉａｌ Ｆｉｓｈ Ｓｗａｒｍ Ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００８，３４（１０）：１９２—１９４（ｉｎ Ｃｈｉｎｅｓｅ）．［王联国，洪毅，赵 ｓｙｓｔｅｍｓ［ｃ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ａｄｖａｎｃｅｓ ｉｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ，２００５：４８０ ４８５． （上接第１７４５页） ［２］Ｍｅｒｖｅ Ｊ Ｖ，Ｄａｗｏｕｄ Ｄ Ｓ，ＭｃＤｏｎａｌｄ Ｓ Ａ ｆｕｌｌｙ ｄｉｓｔｒｉｂｕｔｅｄ ｐｒｏａｃ— ｔｉｖｅｌｙ ｓｅｃｕｒｅ ｔｈｒｅｓｈｏｌｄ－ｍｕｌｔｉｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃ— ｔｉｏｎｓ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｄ Ｓｙｓｔｅｍｓ，２００７，１８（４）：４７—５１．ｅ ［８］ＺＨＯＵ Ｈｏｎｇ，ＬＩ Ｘｉ．Ａ ｓｅｃｕｒｅ ｉｄｅｎｔｉｔｙ－ｂａｓｅｄ ｔｈｒｅｓｈｏｌｄ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ ｆｒｏｍ Ｔａｔｅ ｐａｉｒｉｎｇ，ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ａｄｖａｎｃｅｄ Ｉｎｆｏ ｃｏｌｎｎｌ ｔｃｈｎｏｌｅｏｇｙ［Ｃ］．ＮｅｗＹｏｒｋ：ＡＣＭ，２００８：１－５． ［９］ＣＨＥＮＧ Ｘ，ＬＩＵ Ｊ，ＷＡＮＧ Ｘ．Ａｎ ｉｄｅｎｔｉｔｙ－ｂａｓｅｄ ｓｉｇｎａｔｕｒｅ ａｎｄ ｉｔｓ ｔｈｒｅｓｈｏｌｄ ｖｅｒｓｉｏｎ ｒＣ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｄ— ｖａｎｃｅｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｎｅｔｗｏｒｋｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ．Ｔａｉｗａｎ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００５：９７３—９７７． ［３］Ｊｏｓｈｉ Ｓ Ｄ，Ｇａｎｅｓｈ Ｍａｎｔｅ．Ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ ｂａｓｅｄ（ｔ，ｎ） ｔｈｒｅｓｈｏｌｄ ｇｒｏｕｐ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ，２０１１，２１（２）：２３—２７． ［４］Ｌｉ Ｆ，Ｙｕ Ｊ，Ｊｕ Ｈ＿Ａ ｎｅｗ ｔｈｒｅｓｈｏｌｄ ｇｒｏｕｐ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ ｂａｓｅｄ ｏｎ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ ｐｒｏｂｌｅｍ［Ｃ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ ｏｎｆｅｒｅｎｃｅ ｏｎ ＳｏｆＣｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ，Ａｒｔｉｆｉｃｉａ１ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ［１Ｏ］ＬＩＵ Ｊｅｎｓｈｉｕｈ，ＨＵＡＮＧ Ｓｈａｏｎｏｎｇ．Ｉｄｅｎｔｉｔｙ－ｂａｓｅｄ ｔｈｒｅｓｈｏｌｄ ｐｒｏｘｙ ｓｉｇｎａｔｕｒｅ ｆｒｏｍ ｂｉｌｉｎｅａｒ ｐａｉｒｉｎｇｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｃａ， ２０１０，２１（１）：４１—５６． Ｎｅｔｗｏｒｋｉｎｇ ａｎｄ Ｐａｒａｌｌｅｌ／Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ． Ｑｉｎｇｄａｏ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ ｏｃｉＳｅｔｙ，２００７：１１７６—１１８２． ［１１］ＬＩ Ｆ，Ｙｕ Ｙ｜Ａｎ ｅｆｆｉｃｉｅｎｔ ａｎｄ ｐｒｏｖａｂｌｙ ｓｅｃｕｒｅ ＩＤ－ｂａｓｅｄ ［５］Ｃａｍｅｎｉｓｃｈ Ｊ，Ｇｒｏｔｈ Ｊ．Ｇｒｏｕｐ ｓｉｇｎａｔｕｒｅｓ：Ｂｅｔｔｅｒ ｅｆｆｉｃｉｅｎｃｙ ａｎｄ ｎｅｗ ｔｈｅｏｒｅｔｉｃａｌ ａｓｐｅｃｔｓ［Ｃ］．Ｓｅｃｕｒｉｔｙ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｎｅｔ— ｗｏｒｋｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００５：１２０—１３３． ｔｈｒｅｓｈｏｌｄ Ｓｉｇｎｃｒｙｐｔｉｏｎ ｓｃｈｅｍｅ［ｃ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ．Ｘｉａｍｅｎ：ＩＥＥＥ ｏｍｐｕｔｅｒ ＳＣｏｃｉｅｔｙ，２００８：４８８ ４９２． ［６］Ｂａｃｋ Ｊ，Ｚｈｅｎｇ Ｙ．Ｉｄｅｎｔｉｔｙ－ｂａｓｅｄ ｔｈｒｅｓｈｏｌｄ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ ｆｒｏｍ ｔｈｅ ｂｉｌｉｎｅａｒ ｐａｉｒｉｎｇｓ［Ｃ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎ ｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ：Ｃｏｄｉｎｇ ａｎｄ Ｃｏｍｐｕｔｉｎｇ． Ｂｅｒｌｉｎ： Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００４：１２４ １２８． ［１２］ＰＩＩＮＧ Ｈｕａｘｉ，ＦＥＮＧ Ｄｅｎｇｇｕｏ．Ａ ｆｏｒｗａｒｄ ｓｅｃ￣ｅ ｔｈｒｅｓｈｏｌｄ ｓｉｇｎａ— ｔｕｒｅ ｓｃｈｅｍｅｆｒｏｍｂｉｌｉｎｅａｒｍｉｒｉｇ ＬｎＪ］．Ｊｏｕｒｎａｌ ｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈ ａｎｄＤｅｖｄｏｐｍｅｎｔ，２００７，４４（４）：５７４－５８０（ｉｎ Ｃｈｉｎｅｓｅ）． ［彭华 熹，冯登国．一个基于双线性映射的前向安全门限签名方案 ［７］Ｃｈｅｎ Ｘ，Ｚｈａｎｇ Ｆ，Ｋｏｎｉｄａｌａ Ｄ，ｅｔ ａ１．Ｎｅｗ ＩＤ－ｂａｓｅｄ ｔｈｒｅｓｈｏｌｄ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ ｆｒｏｍ ｂｉｌｉｎｅａｒ ｐａｉｒｉｎｇｓ［Ｃｊ．Ｐｒｏｇｒｅｓｓ ｉｎ Ｃｒｙｐ— ｔｏｌｏｇｙ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００５：３７１—３８３． 口］．计算机研究与发展，２００７，４４（４）：５７４—５８０．］ ［１３］ＳＭＡＲＴ Ｎｉｇｅ１．Ｃｒｙｐｔｏｇｒａｐｈｙ：Ａｎ ｉｎｔｒｏｄｕｃｔｉｏｎ（３ｒｄ ｅｄ） ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｈｄＩ．ｈａｎｄｌｅ．ｎｅｔ／１２３４５６７８９／７８，２０１１．