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

EAGER：辫子统计和辫子组中的难题及其在密码学中的应用

• 批准号: 1551271
• 负责人: Paul Gunnells
• 金额: $ 15万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-15 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1551271&HistoricalAwards=false
• 关键词: EAGER; Braid; Statistics; Hard; Problems

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.

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