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

点击翻译按钮获取中文摘要

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.