Provable Security from Group Theory and Applications

ABSTRACT

This project builds a foundation for cryptography based on combinatorial group theory. The approach of the project is to develop a framework to formu- late computational problems from combinatorial group theory that are suitable for cryptographic applications. An essential aspect of this framework is its amenability to provable security, the type of security analysis characteristic of modern cryptography. This trait differentiates this research from other propos- als of group-theoretic platforms for cryptographic applications that sought to capitalize on the algorithmic unsolvability of certain group-theoretic problems such as the "word problem."

The objectives of this project are grouped in three categories: (1) identifica- tion of efficiently sampleable distributions on which (variants of) standard com- putational group-theoretic problems remain difficult on average; (2) formula- tion of group-theoretic learning problems, and investigation of their average-case hardness; and (3) exploration of group-theoretic cryptographic constructions with enhanced functionality, with the long-term goal of deriving group-theoretic instantiations of public-key cryptosystem with homomorphic properties.

Award ID: 1117679