This research project will investigate and develop new mathematical tools in public-key cryptography. Such tools have been introduced in recent years as suitable for implementation on low-cost platforms with constrained computational resources; it is expected that such platforms will become more and prevalent as consumer devices become "smart" and connect to large networks with the emergence of the "Internet of Things." Public-key cryptography is used by each person hundreds and perhaps thousands of times daily, as it is the main security used in cellular, ATM, and other computer networks. Traditional public-key systems are based on hard problems in number theory, such as finding the prime factors of a large number. The tools that will be investigated in this project come from abstract algebra, namely the theory of braids. Intuitively, a braid is exactly what the reader pictures it to be: a tangled weave of strands. Braids can be encoded symbolically, which leads to the computational problems of recognizing when two braids are the same, or when a braid can be made less complicated through simple manipulations. Such computational problems have been turned into cryptographic protocols, and a central problem of this research is to try to understand just how difficult such problems are, from the perspective of both "brute-force" attacks and more sophisticated algorithms. The problems that will be investigated in this project focus on braid groups and their applications to cryptographic systems. In particular, there have been many cryptographic protocols proposed in recent years based on braid groups, from the original Anshel-Anshel-Goldfeld key exchange to the more recent Sibert-Dehornoy-Girault authentication scheme. Today there are various attacks on some of these protocols, but present knowledge of the effectiveness of these attacks is far from complete. The research that will be conducted in this project will help to address this issue. The first part investigates statistics in braid groups and generation of random braids, with the goal of establishing effective security parameters for braid cryptosystems. The second part treats quantitative connections between the geometry of braids (as automorphisms of the punctured disk) and effectiveness of various algorithms relevant to braid group cryptography. The final part investigates the effectiveness of length-based attacks on computational problems in braid groups.
EAGER: Braid Statistics and Hard Problems in Braid Groups with Applications to Cryptography