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

New Braid Intractable Problems and Cryptographical Applications

作　　者：汤学明[1] 洪帆[1] 崔国华[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机研究与发展》2006年第7期1246-1251,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60403027)

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

关 键 词：辫子群 方根 线性表示 公钥密码 密钥协商协议 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]