EAGER: Braid Statistics and Hard Problems in Braid Groups with Applications to Cryptography

这项研究项目将研究和开发公钥密码学中的新数学工具。这些工具是近年来推出的，适合在计算资源有限的低成本平台上实施；预计随着消费设备变得“智能”并随着“物联网”的出现而连接到大型网络，此类平台将变得越来越普遍。公钥密码术每天被每个人使用数百次甚至数千次，因为它是蜂窝、ATM和其他计算机网络中使用的主要安全措施。传统的公钥系统基于数论中的难题，例如寻找大数的素因数。本项目将研究的工具来自抽象代数，即辫子理论。从直觉上讲，辫子正是读者所想象的那样：一股纠结的编织。辫子可以用符号编码，这导致了识别两个辫子相同的时候的计算问题，或者当一个辫子可以通过简单的操作变得不那么复杂的时候。这样的计算问题已经变成了密码协议，本研究的一个中心问题是试图从“蛮力”攻击和更复杂的算法的角度来理解这些问题有多难。本项目将研究的问题集中在辫子群及其在密码系统中的应用。特别是，近年来已经提出了许多基于辫子群的密码协议，从最初的Anshel-Anshel-Goldfeld密钥交换到最近的Sibert-Dehornoy-Girault认证方案。今天，这些协议中的一些遭到了各种攻击，但目前对这些攻击的有效性的了解还远远不完整。将在这个项目中进行的研究将有助于解决这个问题。第一部分研究辫子群中的统计和随机辫子的产生，目的是建立辫子密码系统的有效安全参数。第二部分讨论了辫子的几何形状(作为被刺穿的磁盘的自同构)和与辫子群密码学相关的各种算法的有效性之间的定量联系。最后研究了基于长度的攻击对辫子群中计算问题的有效性。

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.