New Public Key Cryptosystems from Combinatorial Group Theory

0 IntroductionThe security of most commonly used cryptographicschemesis essentially based onthree families of compu-tational problems :the integer factoring problem(RSAprob-lem) ,the Diffie-Hell man problemand the discrete logarithmproblem,andthe elliptic curve variants thereof .Inthe middleof 1990s , Shor1], Bonehet al2]presented some remarkablequantumalgorithms which can solveinteger factoring problemand discrete logarithmproblemover any group including Ga-lois fields and elliptic curve…

New public key cryptosystems from combinatorial group theory

External direct product of some low layer groups such as braid groups and general Artin groups, with a kind of special group action on it, provides a secure cryptographic computation platform, which can keep secure in the quantum computing epoch. Three hard problems on this new platform, Subgroup Root Problem, Multi-variant Subgroup Root Problem and Subgroup Action Problem are presented and well analyzed, which all have no relations with conjugacy. New secure public key encryption system and key agreement protocol are designed based on these hard problems. The new cryptosystems can be implemented in a general group environment other than in braid or Artin groups.