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.