Dorian Goldfeld - NATO Workshop in Israel

Quantum Resistant Group Theoretic Public Key Methods

Dorian Goldfeld

Abstract:

All widely used public-key solutions are based in number theory. This includes RSA, DH, and ECC. Of course once sufficiently large quantum computers get built all of these number-theory-based methods fall to Shor's algorithm. We believe that group theory can provide a strong basis for quantum resistant solution. While researchers have looked somewhat into lattices, we specifically believe that some hard problems in the braid group can be used. To that end we have been developing several group-theoretic public-key solutions based on various hard problems in the braid group.

In 2005 we introduced a group-theoretic one-way function called E-Multiplication that translates from the braid group to permutations and matrices over finite fields. Using E-Multiplication, combined with other hard problems in braid group theory, we have devised several quantum-resistant public-key solutions including a key agreement protocol and a digital signature solution.

Some interesting features of E-Multiplication are that it is rapidly computable, even on the tiniest of devices, its computation scales linearly with the length of the braid making it a perfect antidote to Grover's search algorithm, and because of the infinite, non-abelian, non-cyclic nature of E-Multiplication it is not subject to Shor's algorithm or the hidden subgroup problem.

In this talk we briefly recount E-Multiplication, quickly explain its quantum resistance characteristics, and then show two new public-key methods based upon it, a key agreement protocol we call KayawoodKAP, and a digital signature algorithm we call WalnutDSA. We will also discuss the security of these constructions in light of previous studies.