Information technology is an established component of the infrastructure of modern societies, and cryptography is a cornerstone of information security. Provable security quantifies the resilience of cryptographic constructions to attacks. This quantification is often relative to the hardness of a handful of reference "intractable" problems like integer factorization. Because of the intrinsic strength of heterogeneity, diversifying the set of intractable problems enhances the robustness of the overall structure. This project responds to the challenge by building a foundation for cryptography from problems in combinatorial group theory.
The project capitalizes on earlier efforts on the algorithmic unsolvability of standard computational problems in combinatorial group theory like the "word problem", but looks at them through the lens of the probabilistic modeling, characteristic of modern cryptography. The research objectives can be grouped into three main categories: 1) identifying efficiently sampleable distributions on which (variants of) the standard computational group-theoretic problems remain _difficult on average_; 2) developing new _hard group-theoretic learning problems_; and 3) exploring the implications of this foundational work to applications with enhanced cryptographic functionality, with the long-term goal of deriving group-theoretic instantiations of public-key cryptography with homomorphic properties.
Results of this project will enrich the theory and practice of cryptography with new tools and alternatives, stimulating for researchers throughout the cryptography and group-theory communities, thus fostering collaborations between the two fields. The undertaking of the research entails significant student participation in research at institutions that serve demographic groups that have been historically underrepresented in computer science and mathematics.
