基于辫子群的密码体制研究及进展.doc

第5期朱萍等：基于辫子群的密码体制研究及进展113基于辫子群的密码体制研究及进展朱萍1,2，温巧燕2（1. 北京邮电大学 理学院，北京 100876；2. 北京邮电大学 网络与交换技术国家重点实验室，北京100876）摘 要：综述了基于辫子群的密码体制的研究成果和发展状况：介绍了现有的基于辫子群的一些密码体制，包括密钥交换协议，加密解密方案和身分认证方案，同时也概述了相关的密码分析方法，如解共轭问题、基于长度和线性表示的攻击等。指出了目前基于辫子群的密码体制所存在的问题，并对其研究前景进行了展望。关键词：密码体制；辫子群；共轭搜索问题；密钥交换中图分类号：TP309 文献标识码：A 文章编号：1000-436X(2009)05-0105-09Survey of braid-based cryptographyZHU Ping1,2, WEN Qiao-yan2(1. School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China;2. State Key Laboratory of Networking and Switching, Beijing University of Posts and Telecommunications, Beijing 100876, China)Abstract: The achievements of braid-based cryptography were surveyed: some recently developed cryptographic schemes were introduced, including key exchange protocols enciphering-deciphering and authentication schemes. The attacks against these schemes were reviewed, such as solutions to conjugacy problems, length-based attacks, and linear representation-based attacks. Some problems in the study of this field were discussed, and several hints for future work were pointed out as well.Key words: cryptographic scheme; braid group; conjugacy search problem; key exchange1 引言收稿日期：2007-12-26；修回日期：2009-03-17基金项目：国家自然科学基金资助项目(60873191, 60821001)；北京市自然科学基金资助项目(4072020)Foundation Items: The National Natural Science Foundation of China (60873191,60821001); The Natural Science Foundation of Beijing (4072020)在过去的30多年里，公钥密码作为现代密码学的核心得到了长足发展，许多优秀的公钥密码体制被建立并逐渐完善。值得注意的是，目前广泛使用的公钥密码体制，都是利用了数学中的某些难解问题，如大整数分解问题、离散对数问题等，特别是利用特殊代数结构上的离散对数问题的难解性构造了一些非常好的公钥算法，椭圆曲线密码体制就是一个典型的代表。事实上，它建立在有限域上的一个特殊的交换群结构上。然而，随着现代计算机速度的不断提高，与交换群相关的问题逐渐变得容易处理了。量子计算的最新研究也表明，基于有限域特性的某些难解问题都有量子的多项式时间算法，因此在量子计算机时代，这些体制将不再是安全的。于是，人们开始积极寻求新的密码体制。从代数学角度，密码算法似乎应该更多地依靠非交换代数结构，如非交换群、非交换半群、非交换环等。基于辫子群（braid group）的公钥密码体制13便是其中最具有代表性的一类。辫子群是一类无限非交换群，但它可以由有限的生成子和关系生成。这些生成子和关系有优美的几何刻画，群中的元素可以由这些生成子表出，因而群运算容易实现，并且存在判断群中2个元素是否相同的有效算法4。另一方面，辫子群中又存在共轭搜索、求根等难解问题2,5,6。这些因素最终使得辫子群成为公钥密码体制设计的工具。这方面的研究起源于1999年Anshel1和2000年Ko2等人的工作。自此，基于辫子群的密码体制引起了许多学者的研究兴趣，一些新的密码体制不断被提出5,79。同时，也出现了与这些体制相关的密码分析1017。这些分析对辫子群密码体制的某些基础假设（如共轭搜索难解问题）提出了质疑，但并未形成任何定论，一些围绕这些质疑的工作正在展开。另外，伴随着辫子群密码体制的研究，人们逐渐展开了对其他非交换代数结构的考察1827，以寻求新的适合构造密码体制的数学工具。目前，基于辫子群密码体制的研究仍然是公钥密码体制研究领域中比较活跃的课题。在密码学领域的一些重要国际会议和期刊上陆续发表了许多关于辫子群密码体制的论文（如文献15, 716等）。相对而言，国内对本领域的研究较少。汤学明等人在文献28中结合辫子群上非共轭变换和多变量方程组构造了新的难解问题，在此基础上设计了新的公钥密码算法。王励成在他的博士学位论文29中对几种典型的共轭搜索问题的算法复杂性进行了分析，研究了基于辫子群的比特承诺协议和数字签名方案。曹珍富等人提出了基于非交换环的公钥密码系统，给出了Diffie-Hellman型的密钥协商协议和ElGamal型的加密方案24。本文对基于辫子群的密码体制和密码分析的研究进行了综述，力图反映该领域的发展过程和对基于其他非交换代数结构密码体制研究的启示。论文其余部分的组织如下：第2节介绍辫子群的定义及其上的难解问题，第3节介绍几种基于辫子群的公钥密码体制，第4节介绍一些典型的密码分析，第5节为结束语。2 辫子群本节介绍辫子群的定义、几何表示及其上的难解问题。2.1 定义辫子群是E. Artin于1926年引入的一类无限、非交换群，它有很好的代数性质和几何刻画，在数学、物理、化学及分子生物学等领域中都有重要应用。对任意，辫子群由生成子及2类关系所生成。这些生成子称为Artin生成子。中的每个元素称为一个辫子。下面的几何表示将帮助研究者理解辫子这个术语，关于辫子群的更多知识可参考文献30,31。对的每个Artin生成子，本文结合一个如图1所示的条线的辫子图。辫子图中的线是互不相交的，这些线可以作所谓的同伦形变（粗略地说，就是在保持每条线的端点固定时，可以将这些线任意拉伸或收缩）。注意对应的辫子图中的第条线在第条线之下。 图1 Artin生成子及其逆对应的辫子图中的群运算乘法对应于辫子图的一种粘接操作，即将乘积中第1个因子对应的辫子图的下排端点与第2个因子对应的辫子图的上排端点一一连接，然后作同伦形变即可，如图2所示。可以证明，这样的几何表示给出的定义和上面基于Artin生成子和关系的定义是等价的。图2 B4中2个辫子之积上的字指的是Artin生成子及其逆构成的一个有限串，如，它们仍然属于。显然，这种表示不是唯一的，表面上不同的字可能代表着中的同一个元素，如前面的字就等于。为了方便判断2个字是否相等，人们如下介绍了标准型的概念。设是中元素生成的子半群，令。如果是的左因子，即存在使得，那么称为单辫子。设是一些不等于或的单辫子，如果每个均是的极大单左因子，那么称序列是标准的，这里是一个整数。可以证明，中每个元素都可唯一表示成，其中构成一个标准序列。因此，称是的标准型，称参数为的典范长度。辫子群中的任何辫子都可以在多项式时间内有效地表示成标准型。2.2 辫子群上的难解问题辫子群引起密码学者兴趣的一个主要原因是由于其上有许多“难解”的数学问题，这些问题有的可用于构造新的密码体制。现在介绍后文将要涉及到的几类2,5,32。辫子群上的许多“难解”问题都是与共轭有关的33。中2个元素称作共轭的，如果存在，使得。1) 共轭判断问题（CDP）。给定，判断是否共轭。2) 共轭搜索问题（CSP）。已知是共轭的，给出一个，使得。3) 同时共轭搜索问题（SCSP）。已知存在使得对所有，给出一个使得对所有。4) Diffie-Hellman型共轭问题（DHCP）。已知，其中属于的不同子群，且满足，求解。5) 根问题。根问题是利用了辫子群是无扭群的事实，即对任意，如果（的单位元），那么对任意自然数。与共轭问题类似，根问题可分为根判断问题和根搜索问题。根判断问题是判断一个辫子是否存在次根，而根搜索问题是已知一个辫子存在次根，给出一个具体的解。6) 移位共轭搜索问题。对任意，定义运算，其中是在中的移位，即是上将映射为的单射。移位共轭搜索问题是：已知，发现辫子使得。3 基于辫子群的密码体制本节将分别介绍基于辫子群的密钥交换协议、加密解密方案和身份认证方案。尽管还有一些文献研究了基于辫子群的其他密码体制，但由于尚未正式发表，所以在此不作介绍。3.1 密钥交换协议利用密钥交换协议，通信双方Alice和Bob通过公开信道建立一个共享的秘钥，而任何窃听者都不能得到这个秘钥的有用信息。下面介绍2种基于辫子群的密钥交换协议。3.1.1 AAG协议AAG协议的一般形式由I. Anshel, M. Anshel和Goldfeld等人在文献1中提出，文献3将该协议应用于辫子群。事实上，下面介绍的协议适用于共轭搜索问题困难的任何群，而不局限于辫子群。AAG协议如下。1) 公钥：中的2组公开辫子及。2) 私钥：Alice的私钥是个文字及其逆上的字，Bob的私钥是个文字及其逆上的字。3) Alice：计算，发送共轭给Bob。4) Bob：计算，发送共轭给Alice。5) Alice计算，Bob计算，共享密钥是。可以看出AAG协议的安全性是基于同时共轭搜索问题（SCSP）的，它是CSP的一个变种。SCSP与CSP的不同之处在于攻击者试图从一族辫子对而不是一个辫子对出发来搜索共同的共轭辫子。显然，SCSP可能比CSP要容易。在文献3中，建议的参数，公钥辫子和的长度分别是5个和10个Artin生成子。3.1.2 Diffie-Hellman型协议尽管辫子群自身是非交换的，但它包含一些大的子群，使得来自不同子群的元素是可以交换的。受Diffie-Hellman密钥协议中交换思想的启发，利用辫子群中一些元素乘积的交换性，Ko等人提出了一个基于辫子群的Diffie-Hellman型密钥交换协议2。令为中的辫子生成的子群，而为辫子生成的子群，这里。显然，中元素与中的元素可交换。Ko等人的Diffie-Hellman型密钥交换协议如下。1) 公钥：中的一个辫子。2) 私钥：Alice的私钥，Bob的私钥。3) Alice：计算并发送共轭给Bob。4) Bob：计算并发送共轭给Alice。5) Alice计算，Bob计算，共享密钥是。因为和是可交换的，可以得到。该协议的安全性是基于中Diffie-Hellman型共轭问题（DHCP）困难性的，DHCP也是CSP的一个变种问题。在文献4中，建议的参数，公钥辫子的长度为12个Artin生成子。值得一提的是，文献34对一般的非交换半群也给出了类似的协议，但那里没明确提到辫子群的概念。3.2 加密解密方案加密解密问题描述的是Bob通过公开信道给Alice发送一个秘密消息，他使用Alice的公钥对该消息进行加密，Alice收到加密的消息后使用她自己的私钥解密。继续使用3.1.2节的符号，并假设是一个从到的无冲突的(collision- free)单向散列函数，即一个可计算的函数，使得对任意，的概率可以忽略不计，并且从找回原像是不可行的。下面的基于辫子群的加密解密方案是Ko等人提出的2。1) 私钥：Alice的私钥。2) 公钥：共轭的辫子对，其中，。3) Bob：要发送的消息是，为了发送该消息，Bob在中随机选取一个辫子，计算密文（这里表示中的加法）及，并将和一同发给Alice。4) Alice：计算，而，即Alice得到了Bob发送的消息。事实上，因为和是可交换的，所以有。进一步该加密解密方案的安全性也是基于DHCP的困难性假设的。一个更一般的版本可参见Cha等人的工作4。最近，汤学明等人基于通过增加变量数目来增加问题难度的思想提出了下面的加密解密方案28。1) 选择正整数使得 。2) 私钥：Alice随机选取中个辫子作为私钥。3) 公钥：随机选取中个辫子，计算，将这个辫子作为公钥。4) Bob：要发送的消息是，为了发送该消息，Bob在中随机选取个辫子，计算密文（这里仍是中的加法）及，并将和所有一同发给Alice。5) Alice：计算，而，即Alice得到了Bob发送的消息。3.3 身份认证方案Sibert、Dehornoy和Girault在文献8,33中介绍了3种基于辫子群的身份认证方案。与这些方案不同，Dehornoy利用移位共轭搜索问题困难性假设给出了另外一种身份认证方案32。下面逐一介绍。3.3.1 Diffie-Hellman型方案该方案的思想直接来源于文献2中的加密解密方案，因而也是建立在DHCP困难性假设基础之上的。其协议如下。1) 私钥：Alice的私钥。2) 公钥：共轭的辫子对，其中，。3) Bob：在中随机选取一个辫子，计算，并将发给Alice。4) Alice：给Bob发送回复。5) Bob：检查是否。如果等式成立，那么Bob可以相信Alice的身份。事实上，因为和是可交换的，所以有，从而可以据此判断Alice的身份。根据函数的性质，Alice只有知道的值才能给出正确的回复，即从出发求，这是DHCP的一个实例。最近，Chowdhury利用Diffie-Hellman分解问题的困难性，将基于辫子群的Diffie-Hellman型认证方案推广到了一般非交换群25。3.3.2 Fiat-Shamir型方案I前面的Diffie-Hellman型方案是一个二阶段式的问答模式，下面介绍的2种Fiat-Shamir型方案都是反复多次的三阶段式的问答模式。第1种方案仅仅基于CSP的困难性假设，事实上对CSP困难性假设成立的任何非交换群均适用。其协议内容如下。1) 私钥：Alice的私钥（不要求在中）。2) 公钥：共轭的辫子对，其中，。下面的三阶段式的问答模式被重复次。3) Alice：在中随机选取一个辫子，计算，并将发送给Bob。4) Bob：随机选取一个比特，发送给Alice。5) 如果，Alice发送给Bob，Bob检查是否。6) 如果，Alice发送给Bob，Bob检查是否。如果Alice知道且正确回答，那么她将被Bob认可。事实上，如果，那么直接可得；如果，那么，因此。如果Alice不诚实，那么经过分析可知她被Bob认可的概率不超过，因此，重复次后她被认可的概率至多是。3.3.3 Fiat-Shamir型方案Fiat-Shamir型身份认证方案与前面这种类似，不同之处在于除了基于CSP难解性外，它还涉及根问题的难解性。关于根搜索问题的密码分析可参见文献35。Fiat-Shamir型身份认证方案的协议如下。1) 私钥：Alice的私钥。2) 公钥：辫子，这里是个取定的大于的正整数。下面的三阶段式的问答模式被重复次。3) Alice：在中随机选取一个辫子，计算，并将发送给Bob。4) Bob：随机选取一个比特，发送给Alice。5) 如果，Alice发送给Bob，Bob检查是否。6) 如果，Alice发送给Bob，Bob检查是否。3.3.4 Fiat-Shamir型方案Fiat-Shamir型身份认证方案32与前面的Fiat-Shamir型身份认证方案、均不同，它是建立在移位共轭搜索问题困难性假设基础之上的。在介绍该协议前，引入一个记号。设是一族到自身的满足下列条件的函数：Dehornoy的协议适用于包含辫子群在内的更一般的代数结构，下面是基于辫子群的版本。1) 私钥：的私钥。2) 公钥：共轭的辫子对，其中，。下面的三阶段式的问答模式被重复次。3) Alice：在中随机选取一个辫子，计算，并将和发送给Bob。4) Bob：随机选取一个比特，发送给Alice。5) 如果，Alice发送给Bob，Bob检查是否。6) 如果，Alice发送给Bob，Bob检查是否。4 基于辫子群的密码体制的分析基于辫子群的密码体制一经提出，便引起了很多学者的兴趣，一些方案很快被发现是不安全的。因为这些方案大多建立在中的CSP及其变种上，因而攻击也围绕这些问题展开。本节将介绍几种主要的攻击方式。4.1节里的2种方法可以完全解决共轭判定问题和共轭搜索问题，但算法复杂度很高（或未知），随后几节的方法都只能部分解决这些问题。4.1 解共轭判定和共轭搜索问题解共轭判定问题和共轭搜索问题6,3638的基本思想是对中的每个元，计算出的共轭类的一个特殊子集，该子集要求满足下列性质。1) 对任意，是有限非空集，且满足共轭当且仅当。2) 对任意，可以有效计算出中的一个代表元及，使得。3) 对任意代表元，存在构造整个集合的有限算法。如果有算法实现上面的步骤，那么就可以很容易地解决CDP和CSP。该思想来源于Garside1969年的工作36，那里集合是的所谓顶点集。下面是基于该思想的2种改进的算法。4.1.1 超级顶点集方法El-Rifai和Morton改进了Garside的方法，用较小的超级顶点集（super summit set）代替了顶点集，这里是由具有最小典范长度且与共轭的所有元素组成的39。为了计算出，El-Rifai和Morton定义了下面2种操作。假设的标准型是，那么的循环操作和去循环操作分别定义为：其中是将对应为的映射。由定义，和均与共轭。因此，如果一个辫子，那么经过至多次循环或去循环操作，一定可以找到一个比典范长度小且与共轭的辫子39,40。这样，重复该操作，在有限步内可以找到的某个共轭。他们证明了，从出发，相继考虑所有的共轭（跑遍所有个单辫子），将与同样典范长度的共轭添入该集合，直到没有新元素产生为止，最后得到的集合就是。这样，判断2个辫子是否共轭可以采取下面的步骤：首先通过循环或去循环操作找到，然后通过上面的算法找到，最后判断是否。因为共轭当且仅当，所以上面的步骤解决了CDP。另外，如果共轭，那么只要在寻找的过程中保留所有的过渡辫子，就可以给出导致共轭的辫子，这样就解决了CSP。关于上面算法的复杂性，在中，目前所有已知的中元素个数的上界都是关于的指数。Franco和Gonzales-Meneses6证明了在从出发求的过程中，不需要考虑所有的个单辫子，而只需考虑个Artin生成子即可，因而改进了上面的算法。尽管如此，中元素数目还是很大。下面的方法试图进一步减少中元素个数。4.1.2 极端顶点集方法最近，Gebhardt发现的一类小子集仍然满足所期望的性质，其思想是利用循环操作的周期性38。具体地，对任意，定义极端顶点集。因此，是一个有限集，由所有在循环操作下封闭的轨道组成，这些轨道互不相交。集合中元素个数通常比少很多。Gebhardt给出的解决CDP和CSP的算法与超级顶点集方法中的类似，只需用代替即可。尽管在实际应用中极端顶点集方法比较好，但理论上还没有此算法复杂性的一般结论。4.2 基于长度的分析基于辫子长度分析10,11,41的原理是：给定一个辫子和它的一个共轭，有可能通过反复使用较短的辫子作用，使得比要短。如果和是随机选取的，那么这种方法经常是有效的。然而如果选取和使得和具有同样的典范长度，那么这种方法将不再有效。文献10, 41中采用的方法是简单地检查是否碰巧就是。这种攻击对基于SCSP困难性假设的密钥交换协议很有效，因为在这种情形下，攻击者知道一族与共轭的辫子。Hofheinz和Steinwandt11介绍了一种攻击CSP的启发式算法，该算法的思想与上面的方法类似，但却多了一步改进措施，因而其攻击更加有效。它不是检查是否碰巧就是，而是检查它们之间是否只相差一个单辫子。发现可能的单辫子是很容易的，因为这等价于解决对称群中的CSP。实证表明这种方法对AAG和Diffie-Hellman型密钥交换协议都有比较高的成功率。尽管这种方法不能给出共轭问题的一般解，但它证实目前各种基于辫子群的密码体制中提出的密钥参数都不是足够安全的。4.3 基于线性表示的分析的线性表示是一个从到一般线性群（环上的所有可逆矩阵构成的群）的同态。因为一般线性群中的共轭问题是很容易的，所以可以通过表示方法反过来研究中的共轭问题。4.3.1 Burau表示方法辫子群的Burau表示对应的基环取作洛仑兹多项式环，它是辫子群的诸多表示中被深入研究的一种。Artin生成子在该表示下的像是单位阵中将对角上的子阵用代换得到的矩阵。当时，这个表示不是忠实的42-44，即不是一个单同态，但它的核一般都非常小45。换言之，2个不同的辫子映为同一个矩阵的概率很小。文献10中使用Burau表示对文献3中的方案进行了密码学分析，其攻击方法是：从一个或几个同时共轭的辫子对出发，计算它们在Burau表示下的像，解决这些像在一般线性群中的CSP。通常，这还不足以解决中的CSP，因为找出的共轭可能并不属于Burau表示的像，即使属于像，也没法找出它们在里的原像。因此，Hughes介绍了一种寻找原像的启发式算法12。Lee和Park对这个算法提出了2种改进，用于解决CSP和DHCP13。4.3.2 Lawrence-Krammer表示方法Lawrence-Krammer表示是辫子群的另外一种线性表示，它是从到一般线性群的同态，这个表示对任意都是忠实的46,47。Cheon、Jun14及Kalka48等利用Lawrence-Krammer表示对文献2中的方案进行了分析，与Burau表示情形类似，困难仍然在于如何将一般线性群里的解提升为中的解。和前面类似，他们没能给出一个完全的解，但他们对所谓的导出Diffie-Hellman共轭问题（即知道、，其中，求解）给出了一个解。利用Lawrence-Krammer表示下的像包含很多零的特征，他们给出了一个多项式的算法。4.4 基于排除冗余的分析下面简单提及2种利用随机生成CSP或DHCP实例冗余信息的分析方法。对DHCP，Myasnikov等人提出了一种实用的启发式解决办法49。对典型的密钥参数，在150min内该方法可以的概率成功破译Diffie-Hellman型密钥交换协议。不过他们的方法解决的是辫子群中的分解问题，而不是共轭问题。Maffre介绍了一种确定性的、约化辫子群中共轭搜索问题的多项式算法50,51。该算法将辫子分解成典范因子的乘积，给出了密钥的一个部分因子分解：约数和倍数。这个算法的有效性依赖于密钥的选取方式。当密钥是随机选取时，这个算法还是很有效的。5 结束语从前面基于辫子群的密码协议及分析可以看出，大多数基于辫子群的密码体制似乎都是不安全的。其实，仔细检查就会发现，这些攻击方法主要是利用了密钥的随机生成方式，即利用了公钥和私钥之间的产生关系。这些攻击都是针对最基本的、问题困难性假设的，还没有用到选择消息攻击、中间人攻击和已知密钥攻击等密码学分析方法。因此，基于辫子群的密码体制还有许多值得研究的问题。将最近文献中提出的以及作者认为值得研究的方向罗列如下。1) 生成安全的密钥。既然目前的攻击都是利用了随机生成的密钥产生的实例不够难的弱点，那么一个自然的问题就是寻求一种可以构造出足够困难的问题实例方法。最近，Ko等人提出了几种针对共轭问题生成困难实例的可能方式52，但这些方式都还有待严格论证。2) 利用其他难解问题。寻找与辫子群有关的其他难解问题也是一个好的增强密码体制安全性的途径。Dehornoy建议利用辫子的最短字问题作为困难性问题假设5，因为辫子群的最短字问题被证明是Co-NP完全的53，所以这个问题被认为是困难的。基于移位共轭搜索问题32困难性假设的密码体制也刚刚开始研究，这方面的研究还有待深入。3) 辫子的随机生成。为了抵抗某些攻击，可以试着改变生成子的分布。例如，可以要求当生成子出现时，下一个位置以比较大的概率出现或，这样使得它们的位置难以交换。如何引入概率测度以及以什么方式更好地随机生成一个辫子是个有趣的问题。4) 考虑其他非交换群或代数结构。目前，一些学者开始研究基于具有其他特殊性质的非交换群、非交换半群，甚至非交换环的密码体制，如基于Thompson群18和Miller群54,55等。尽管这些工作还有待检验，但至少可以通过不同代数结构上密码体制的研究来理解和改进基于辫子群的密码体制。目前尚未发现基于结合代数（一类特殊的环）的密码体制。由于域上的某些结合代数（如Brauer代数56，Temperley-Lieb代数57,58等）具有很多与辫子群类似的性质，同时也能体现基域的特征，因此，研究基于这些代数结构上的密码体制可能会产生更深刻的结果。参考文献：1ANSHEL I, ANSHEL M, GOLDFELD D. An algebraic method for public-key cryptographyJ. Math Res Letters, 1999, 6: 287-291.2KO K H, LEE S J, CHEON J H, et al. New public-key cryptosystem using braid groupsA. Crypto 2000C. Springer-Verlag, 2000. 166-184.3ANSHEL I, ANSHEL M, FISHER B, et al. New key agreement protocols in braid group cryptographyA. CT-RSA 2001C. San Francisco, USA, Springer-Verlag, 2001. 1-15.4CHA J C, KO K H, LEE S J, et al. An efficient implementation of braid groupsA. Proc ASIACRYPT 2001C. Springer-Verlag, 2001. 144-156.5DEHORNOY P. Braid-based cryptographyJ. Contemp Math, 2004, 360: 5-33.6FRANCO N, GONZALES-MENESES J. Conjugacy problem for braid groups and Garside groupsJ. J Algebra, 2003, 266: 112-132.7LEE E K, LEE S J, HAHN S G. Pseudorandomness from braid groupsA. Crypto 2001C. Springer-Verlag, 2001. 486-502.8DEHORNOY P, GIRAULT M, SIBERT H. Entity authentication schemes using braid word reductionA. Proc Internat Workshop Coding CryptC. Versailles, 2003. 153-164.9LEE E K. Braid groups in cryptologyJ. IEICE Trans Fundamentals, 2004, E 87A(5): 986-992.10LEE S J, LEE E K. Potential weakness of the commutator key agreement protocol based on braid groupsA. Proc EUROCRYPT 2002C. Springer-Verlag, 2002. 14-28.11HOFHEINZ D, STEINWANDT R. A practical attack on some braid group based cryptographic primitivesA. Proc PKC 2003C. Springer- Verlag, 2002. 187-198.12HUGHES J. A linear algebraic attack on the AAFG1 braid group cryptosystemA. ACISP 2002C. Springer-Verlag, 2002. 176-189.13LEE E K, PARK J H. Cryptanalysis of the public-key encryption based on braid groupsA. Proc EUROCRYPT 2003C. Springer- Verlag, 2003. 477-490.14CHEON J H, JUN B. A polynomial time algorithm for the braid Dife-Hellman conjugacy problemA. Proc CRYPTO 2003C. Springer-Verlag, 2003. 212-225.15SHPILRAIN V. Assessing security of some group based cryptosystemsJ. Contemp Math, 2004, 360: 167-177.16MYASNIKOV A G, SHPILRAIN V, USHAKOV A. A practical attack on some braid group based cryptographic protocolsA. Crypto 2005C. Springer-Verlag, 2005. 86-96.17MYASNIKOV A G, SHPILRAIN V, USHAKOV A. Random subgroups of braid groups: an approach to cryptanalysis of a braid group based cryptographic protocolA. PKC 2006C. Springer-Verlag, 2006. 302-314.18SHPILRAIN V, USHAKOV A. Thompsons group and public key cryptographyA. ACNS 2005C. Springer-Verlag, 2005. 151-163.19SHPILRAIN V, USHAKOV A. A new key exchange protocol based on the decomposition problemJ. Contemp Math, 2006, 418: 161-167.20SHPILRAIN V, ZAPATA G. Using the subgroup membership search problem in public key cryptographyJ. Contemp Math, 2006, 418: 169-179.21SHPILRAIN V, ZAPATA G. Combinatorial group theory and public key cryptographyJ. Appl Alg Eng Comm Comp, 2006, 17(3-4): 291-302.22ACKERMANN P, KREUZER M. Grobner basis cryptosystemsJ. Appl Alg Eng Comm Comp, 2006, 17(3-4): 173-194.23BAUMSLAG G, FINE B, XU X W. Cryptosystems using linear groupsJ. Appl Alg Eng Comm Comp, 2006, 17(3-4): 205-217.24CAO Z F, DONG X L, WANG L C. New public key cryptosystems using polynomials over non-commutative ringsEB/OL. http:/eprint.iacr. org/2007/009, 2007.25CHOWDHURY M M. An authentication scheme using non-commutative semigroupsA. Third Internat Symp Inform Assurance SecurityC. 2007. 115-118.26RUINSKIY D, SHAMIRAND A, TSABAN B. Cryptanalysis of group-based key agreement protocols using subgroup distance functionsA. PKC 2007C. Springer-Verlag, 2007. 61-75.27SAKALAUSKAS E, TVARIJONAS P, RAULYNAITIS A. Key agreement protocol (KAP) using conjugacy and discrete logarithm problems in group representation levelJ. Inforatica, 2007, 18(1): 115-124.28汤学明，洪帆，崔国华. 辫子群上的公钥加密算法J. 软件学报，2007, 18(3): 722-729.TANG X M, HONG F, CUI G H. A public key encryption algorithm on braid groupsJ. J Software, 2007, 18(3): 722-729. 29王励成. 基于辫群的密码方案的设计与分析D. 上海交通大学, 2007.WANG L C. Design and Analysis of Cryptographic Schemes Based on Braid GroupsD. Shanghai Jiaotong Univ, 2007.30ARTIN E. Theory of braidsJ. Ann Math, 1947, 48: 101-126.31BIRMAN J S. Braids, Links and Mapping Class GroupsM. Ann Math Study 82, Princeton University Press, 1974.32DEHORNOY P. Using shifted conjugacy in braid-based cryptographyJ. Contemp Math, 2006, 418: 65-73.33SIBERT H, DEHORNOY P, GIRAULT M. Entity authentication schemes using braid word reductionJ. Discrete Applied Math, 2006, 154(2): 420-436.34SIDELNIKOV V M, CHEREPNEV M A, YASHCENKO V Y. Systems of open distribution of keys on the basis of noncommutative semigroupsJ. Russian Acad Sci Dokl Math, 1994, 48(2): 384-386.35GROCH A, HOFHEINZ D, STEINWANDT R. A practical attack on the root problem in braid groupsJ. Contemp Math, 2006, 418: 121-131.36GARSIDE F A. The braid group and other groupsJ. Quart J Math, Oxford Ser, 1969, 20(2): 235-254.37EPSTEIN D, CANNON J, HOLT D, et al. Word Processing in GroupsM. Jones & Bartlett Publ, 1992.38GEBHARDT V. A new approach to the conjugacy problem in Garside groupsJ. J Algebra, 2005, 292(1): 282-302.39EL-RIFAI E A, MORTON H R. Algorithms for positive braidsJ. Quart J Math Oxford Ser, 1994, 45(2): 479-497.40BIRMAN J, KO K, LEE S. The infimum, supremum, and geodesic length of a braid conjugacy classJ. Adv Math, 2001, 164: 41-56.41GARBER D, KAPLAN S, TEICHER M, et al. Length-based conjugacy search in the braid groupJ. Contemp Math, 2006, 418: 75-87.42MOODY J A. The Burau representation of the braid group is unfaithful for large nJ. Bull Amer Math Soc New Ser, 1991, 25(2): 379-384.43MOODY J. The faithfulness question for the Burau representationJ. Proc Amer Math Soc, 1993, 119(2): 671-679.44BIGELOW S. The Burau representation is not faithful for n = 5J. Geom Topol, 1999, 3: 3