魄 云， 朱双宁， 张兴凯， 王冠男

（1空军电子技术研究所， 北京 100195；296610 部队， 北京 102208 ）

基于辫群的签名方案研究

魄 云1， 朱双宁1， 张兴凯2， 王冠男1

（1空军电子技术研究所， 北京 100195；296610 部队， 北京 102208 ）

辫群是构造抗量子攻击密码方案的新平台。 本文对一个基于辫群上求根问题的签名方案进行分析，指出该方案是不安全的，得到签名的任何人都能计算出签名人的私钥;利用共扼搜索问题的难解性来隐藏用户的密钥信息，构造出新的签名方案，分析表明该方案是可证明安全的。

签名;辫群;共扼搜索问题;求根问题;随机预言模型

0 引言

量子计算[1-2］的快速发展使得安全性假设为整数分解和离散对数难解性的公钥密码体制面临严重威胁。为了抵抗已知量子算法的攻击，大量学者开始设计非基于数论的、基于非交换代数的公钥密码体制。 1947年，Artin[3］首次提出辫群这一代数结构，辫指数大于 2 的辫群具有复杂的非交换结构，为构造抗量子攻击密码体制提供了新的平台。 2000年，Ko 等[4］提出了第一个辫群上的公钥密码体制。 此后，众多学者相继提出了辫群上的密钥交换协议[5-6］、认 证 协 议[7-8］和签名方案[9-18］。 目前大多数基于辫群的签名方案安全性都是基于共扼类问题，属于共扼签名方案，不具有可证明安全性。

2010年，文献[19］首次基于辫群上的求根问题构造了具有可证明安全性的签名方案。本文对该方案的安全性进行分析，得出：任何人都能根据签名计算出签名人的私钥，因此该方案是不安全的。 本文对该方案进行改进，通过共扼作用实现对签名人私钥的保护，得到的签名方案仍然是可证明安全的。……