辫子群上新的难解问题及其密码学应用研究

利用Shor，Boneh和Lipton等的量子算法不仅可以在多项式时间内分解大整数，还可以有效解决离散对数和椭圆曲线上的离散对数问题，传统的基于这三类难解问题的公钥密码系统在量子计算机时代将变得不再安全．辫子群是一类较适合构造抵抗量子密码分析的计算平台，但目前基于辫子群的公钥密码系统所凭借的难解问题都得到了一定程度的解决．两类新的难解问题是根据P次方根问题的难解性和线性表示攻击提出的．在此基础上构造了一个新的密钥协商协议，分析了协议的安全性，给出了参数选择建议和理由．新的密钥协商协议可以抵抗目前已知的各种攻击．

New Braid Intractable Problems and Cryptographical Applications

By using Shor, Boneh and Lipton's quantum algorithms, quantum computers can solve big integer factorization problems, discrete logarithm problems and discrete logarithm problems on elliptic curves, but public key cryptography systems based on these problems will become insecure in the age of quantum computers. It seems that braid group is a kind of considerable public key cryptography platform in the future. Solutions to the underlying intractable problems make all current braid cryptography systems look vulnerable. Two kinds of new intractable problems related to the p-th root finding problem and linear representation attacks are proposed to design a new key agreement protocol. Following the proposal of the parameter choice, the new protocol can resist all current known attacks.