Conjugate adjoining problem in braid groups and new design of braid-based signatures  

作　　者：WANG LiCheng WANG LiHua CAO ZhenFu YANG YiXian NIU XinXin 

机构地区：[1]Information Security Center, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China [2]National Institute of Information and Communications Technology, Tokyo 184-8795, Japan [3]Trusted Digital Technology Laboratory, Shanghai Jiao Tong University, Shanghai 200240, China

出　　处：《Science China(Information Sciences)》2010年第3期524-536,共13页中国科学（信息科学）（英文版）

基　　金：supported by the National Natural Science Foundation of China (Grant Nos. 90718001, 60973159,60972034, 60773086, 60821001);the National High-Tech Research & Development Program of China (Grant No.2009AA01Z439);the National Basic Research Program of China (Grant No. 2007CB310704);(Japan) NICT International Exchange Program (Grant No. 2009-002)

摘　　要：The development of quantum computation casts serious threats to the securities of most existing public-key cryptosystems. Braid-based cryptography is one of the alternatives that have potential advantages in resisting quantum attacks. In this paper, the state of the art of braid cryptography is surveyed, and then a new cryptographic problem-conjugate adjoining problem related to braid groups is proposed. Based on this problem, we design a new braid-based signature scheme. This scheme is efficient and provably secure in the random oracle model. Further, we present the comparison between braid-based signatures and RSA-based ones. The signing process of the braid-based schemes is more efficient than that of RSA-based ones, while the verifying process of the braid-based ones is observably slow. Hence, braid-based signatures are suitable for scenarios where the signing process has to be as quick as possible but delays are permitted in the verifying process, for example, in off-line e-cash systems. The key sizes in braid-based schemes are considerably large-about 2K bits in the case of secret keys and 12K bits in the case of public keys. However, braid operations are much simpler and more efficient than modular exponential operations. Therefore, braid-based schemes can be embedded into devices with low computational ability and large memory space. The capability of braid cryptosystems to resist currently known quantum attacks is also discussed from the perspective of hidden subgroup problems.

关 键 词：braid group conjugate adjoining problem digital signature provable security resistance to quantum attack 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术] TS935.5[自动化与计算机技术—计算机科学与技术]