SaTC: CORE: Small: Markoff Triples, Cryptography, and Arithmetic of Thin Groups

University Of California-Davis, Davis CA

Investigators

Abstract

This project seeks to find new applications of classical number theory to cryptographic hash functions, which are vital to password protection, digital signatures, and more. The investigator aims to construct new algorithms for finding paths between vertices of graphs whose structure underlies certain number theoretic questions, as well as algorithms for finding short cycles in these graphs. Advances will have implications for both the security of hash functions and number theory itself. The project is multidisciplinary and will bring together experts from number theory and cryptography. It is also seeking to involve younger scientists at both the undergraduate and graduate level. Recent work has shed light on the so-called Markoff mod-p graphs that underly many arithmetic questions about Markoff triples. This family of graphs, conjectured to be an expander family, is the basis of a cryptographic hash function introduced by the investigator and collaborators. Many questions remain about the security of this hash function and about graphs connected to generalizations of the Markoff surface, which may be even better candidates for a hash. One such question concerns lifts of mod-p Markoff triples to integer Markoff triples, and the investigator plans to prove results on the average sizes of these lifts. Such results would feed into understanding the run time of an attack. The investigator will also work to compare the security of the new hash functions to hash functions that are accepted as secure today by equating and drawing parallels between path finding in the Markoff mod-p graphs and questions that are known to be difficult. A new quick path finding algorithm, while unfortunate from the cryptographic point of view, would have important consequences from the number-theoretic viewpoint. Finally, the investigator will continue her number theoretic work on thin groups, such as the one lurking behind Markoff triples. She aims to extend results on local to global principles in various circle packings; currently such a principle is known to exist when the symmetry group connected to the packing contains certain nice groups, and she plans to relax this restriction. Another goal of the project is to establish results on thickened prime components in Apollonian packings. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.