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.
Cryptography is a source of many techniques and protocols that underpin most defense and control mechanisms for the nation's cyber-infrastructure. But what underpins cryptography? At the heart of the modern approach to cryptography are mathematical guarantees that code-breakers may only succeed if they manage to unravel computational problems (like factoring large numbers) that are believed intractable---too hard to be solved by the most powerful computers even if left to crunch numbers for centuries. Most cryptographic constructs in common usage today rely on a small handful of computational problems from Number Theory that would be easily solved by quantum computers, if (when?) the technological hurdles to their construction will be overcome. To anticipate this eventuality, this project explored the mathematical field of computational group theory as an alternate source of hard problems suitable to sustain cryptography. INTELLECTUAL MERIT Previous work had looked at the intractability of group-theoretic problems, but as it turns out, computational hardness comes in many shapes, not all equally useful for cryptographic applications. While group-theoretic problems considered earlier do in fact feature problem instances that are extremely hard to solve, these "worst cases" are often very rare---too rare for cryptographic protocols, which instead require that hard instances be common and easy to get by, that is, that the underlying computational problem remain hard even in the average case. To discover suitable average-case hard group-theoretic problems, the team of investigators on this project moved from a close analysis of recent advances in the application of techniques from computational learning theory to cryptography. In that context, researchers had discovered that the addition of random perturbations (also known as "noise" or "errors") can turn simple computational tasks like solving simultaneous equations (which can be tackled with high-school algebra methods like row reduction), into intractable problems, known as "learning parity with noise" and "learning with errors". This project led to a generalization of these learning problems that applies to algebraic settings less constrained than the familiar ones of integer numbers. This generalization in turn inspired the design of a cryptosystem based on so-called Burnside groups of exponent 3, which promises to be both very efficient and quantifiably hard to break. In particular, this project has shown that solving a random instance of this problem is not any easier than solving an arbitrary instance. This makes it easy to harvest cryptographic hardness from Burnside groups, since sampling a random instance always yields a "worst case" (for the attacker, that is). BROADER IMPACT The researchers supported by this project disseminated their results in international journals as well as in conferences and seminars held both in the US and abroad (including China, Italy, and South Africa). Highlights of the research were also incorporated in their courses on Cryptography and Information Security. Additionally, the project supported graduate and undergraduate researchers who assisted in the development of a software library for the manipulation of Burnside groups, which is available at: www.cs.stevens.edu/~nicolosi/projects/lcac/Bn_code.tgz
