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

该研究项目将研究和开发新的公钥密码学数学工具。近年来，这些工具被引入，因为它们适合在计算资源有限的低成本平台上实现；随着“物联网”的出现，消费设备变得“智能”，并连接到大型网络，预计这类平台将变得越来越普遍。每个人每天都要使用数百甚至数千次公钥加密，因为它是蜂窝、ATM和其他计算机网络中使用的主要安全措施。传统的公钥系统是基于数论中的难题，如寻找大数的素数因子。本项目将研究的工具来自抽象代数，即辫子理论。直观地说，辫子就是读者想象中的样子：一团缠在一起的辫子。辫子可以进行符号编码，这导致了计算问题，即识别两个辫子何时相同，或者何时可以通过简单的操作使辫子变得不那么复杂。这样的计算问题已经变成了加密协议，而这项研究的一个中心问题是试图从“暴力”攻击和更复杂的算法的角度来理解这些问题有多困难。本课题研究的问题主要集中在编织群及其在密码系统中的应用。特别是，近年来提出了许多基于辫子组的加密协议，从最初的anshell - anshell - 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.