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

该项目旨在寻找经典数论在加密哈希函数中的新应用，这些哈希函数对密码保护，数字签名等至关重要。研究者的目的是构建新的算法，用于寻找图的顶点之间的路径，其结构是某些数论问题的基础，以及在这些图中寻找短周期的算法。这些进展将对散列函数的安全性和数论本身产生影响。该项目是多学科的，将汇集数论和密码学专家。最近的工作揭示了所谓的马尔可夫模p图，它是许多关于马尔可夫三元组的算术问题的基础。这个图族，被证明是一个扩展族，是研究者和合作者引入的加密哈希函数的基础。关于这个散列函数的安全性以及连接到Markoff曲面的泛化的图仍然存在许多问题，这些泛化的Markoff曲面可能是散列的更好候选。一个这样的问题涉及升降机的模p马尔可夫三元组的整数马尔可夫三元组，调查人员计划证明这些升降机的平均大小的结果。这些结果将有助于理解攻击的运行时间。研究人员还将通过将Markoff mod-p图中的路径查找与已知困难的问题等同起来并绘制它们之间的相似之处，来比较新散列函数的安全性与今天被接受为安全的散列函数。一个新的快速路径查找算法，虽然从密码学的角度来看是不幸的，但从数论的角度来看，它将产生重要的后果。最后，研究人员将继续她的数论工作薄组，如一个潜伏背后的马尔可夫三元组。她的目标是扩大结果的地方全球原则在各种圆包装;目前这样的原则是已知存在时，对称群连接到包装包含某些不错的群体，她计划放宽这一限制。该项目的另一个目标是建立在阿波罗填料的加厚主要成分的结果。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.