CAREER: Non-Commutative Cryptography from Hard Learning Problems: Theory and Practice

现代信息技术生态系统的许多弹性是基于其核心的加密结构的强度。发现适合于密码系统设计的新的棘手问题，提高了整个基础设施对诸如量子计算机的发展或针对任何特定计算问题的不可预见的密码分析进步等突破的稳健性。这个项目发展了一种新的密码学方法的理论和实践，该方法基于一类非交换群上的学习问题，统称为带噪声的学习同态(LHN)。非交换群作为密码困难的来源的吸引力早已被认识到，这部分是由于在这种情况下缺乏重要的量子算法，但分离出合适的难易假设是难以捉摸的。该项目探索了四个主要线索：(1)基于LHN的难易程度设计有效的密码构造；(2)建立基本学习问题的难解的证据，特别是针对量子计算；(3)建立软件库来有效地操作这些学习问题的实例，并评估基于学习的非交换密码学的性能；以及(4)探索额外的LHN变体以克服在其他线程的执行中遇到的任何限制。通过使密码学所依据的前提多样化，并为未来的劳动力创造信息安全方面的培训机会，该项目将加强现代信息技术基础设施的关键部分。

The resiliency of much of the modern information technology ecosystem is predicated on the strength of the cryptographic constructions at its core. Uncovering new intractable problems suitable for cryptosystem design enhances the robustness of the overall infrastructure to breakthroughs like the development of quantum computers or unforeseen cryptanalytic advances against any specific computational problem. This project develops the theory and practice of a novel approach to cryptography based on a class of learning problems over non-commutative groups, known collectively as Learning Homomorphisms with Noise (LHN). The appeal of non-commutative groups as a source of cryptographic hardness, due in part to the absence of significant quantum algorithms for this setting, has long been recognized, but isolating suitable intractability assumptions has proven elusive.The project explores four main threads: (1) designing efficient cryptographic constructions based on the hardness of LHN; (2) establishing evidence of the intractability of the underlying learning problems, especially against quantum computing; (3) building a software library to manipulate instances of these learning problems efficiently, and evaluating the performance of learning-based non-commutative cryptography; and (4) exploring additional LHN variants to overcome any limitation encountered in the execution of the other threads. By diversifying the premises on which to base cryptography and creating training opportunities in information security for tomorrow's workforce, this project will strengthen a critical part of the modern information technology infrastructure.