Research On Braid Group Public Key Cryptosystems And Quantum Cryptanalysis

Public key cryptography is a key technique to make cryptography used widely in network environment. The development of the technology of quantum computer and quantum cryptanalysis is a big challenge to the security of traditional public key cryptographic schemes based on integer factoring, discrete logarithm and discrete logarithm on elliptic curve, which leads public key cryptography to develop towards quantum ages.There are many difficult problems in braid groups which can be used for cryptography, but all recent braid public key cryptosystems are broken to some degree. After analyzing the theory of length-based attack, conjugacy search attack, SSS and USS attack, and linear representation attack, taking advantage of the properties of generic algorithm such like self-organization, self-adaptation, self-learning and parallelism , some braid difficult problems such as conjugacy search problem and root finding problem can be attacked more efficiently than by other statistic algorithms.Because there is some security weakness in conjugacy and p-th root problems in braid grous, base on some basic groups, a new group theory computing platform is constructed; this platform is the (external) direct products of some basic groups, and a special group action is defined over this platform. Two new difficult problems, MSRP and SAP are presented, the security of these two problems are analyzed with respect to general groups and braid groups. In braid groups, these two kinds of problems can resist current all known attacks, especially Burau linear representation attack.Braid DH-like key exchange protocols, BDH and AAG(AAFG), have been proved to be insecure. Some security methods such like combinatorial problems, random braids and multivariate equations system are used to improve AAFG to a new secure protocol. With correct parameters, the new protocol can resist all current attacks suck like length-based attack, linear representation attack, conjugacy search attack and quantum cyrptoanalysis.Base on the difficulty of MSRP and SAP, a new public key exchange protocol and a new public key encryption algorithm in general non-Abelian groups are presented, and the correctness and security of them are proved. Two braid instance for both algorithms are reasonably designed, some security conditions are required with respect to braid group. Because the security of these two algorithms is not based on the difficulty of conjugacy and p-th root problems, the new key exchange protocol and public key encryption algorithm are more secure that others.Base on both kinds of Merkle trees, a new digital signature scheme are constructed with the transitivity of signature. New signature scheme is provably existentially unforgeable under adaptive chosen message attack. Lack of efficiency in the initial key generation process is a serious shortcoming of Merkle tree signature scheme. After researching the algorithms of Merkle tree traversal, the time of initial setup is decentralizing the initial key generation process within each signature process, which improves the efficiency of initial setup and make it possible to build a practical big Merkle tree in several minutes.There is essential difference between quantum bit and classical bit, between quantum logical gate and classical logical gate. Quantum parallelism is the basic character of quantum algorithms. The main methods of quantum cryptanalysis are quantum Fourier transform and Shor quantum factoring algorithm. Some quantum circuitries are designed for Shor factoring algorithm with a small integer using the software QCAD, which presents the general methods to realize a quantum algorithm in a circuitry level. Some common characters of public key cryptographic algorithm secure against quantum cryptanalysis are revealed, i.e. the underlying difficult problems can be proved to be NP-hard or NP-complete, the algorithms often use manifold algebraic structure to resist potential algebraic attacks, and some combinatorial problems which can't be solved by any optimal algorithm are used in the design. Altogether, after researching the basic methods of quantum and traditional cryptoananlysis, the fundamental ideals to designed public key cryptosystem secure against quantum cryptanalysis are presented and researched. New public key exchange protocol, public key encryption algorithm and digital signature algorithm are provided in the fields of general groups, braid groups and Merkle tree. In the three main application forms, some tries are made to approach the aim of resisting quantum cryptanalysis.