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

该项目致力于寻找经典数论在密码散列函数中的新应用，这些散列函数对于密码保护、数字签名等至关重要。研究人员的目标是构造新的算法来寻找图的顶点之间的路，以及在这些图中寻找短圈的算法。图的结构是某些数论问题的基础。这一进展将对散列函数的安全性和数论本身产生影响。该项目是多学科的，将汇集数论和密码学的专家。它还在寻求让本科生和研究生中的年轻科学家参与进来。最近的工作揭示了所谓的Markoff mod-p图，它低于许多关于Markoff三元组的算术问题。这一图族被认为是一个扩展器族，是由研究人员和合作者引入的密码散列函数的基础。关于这个散列函数的安全性以及与Markoff曲面的推广有关的图仍然存在许多问题，它可能是更好的散列候选者。其中一个问题涉及mod-p Markoff三元组到整数Markoff三元组的提升，调查者计划证明这些提升的平均大小的结果。这样的结果将有助于理解攻击的运行时间。研究人员还将通过将Markoff mod-p图中的路径查找与已知困难的问题等同并进行类比，将新散列函数的安全性与目前公认的安全散列函数进行比较。一种新的快速寻路算法，虽然从密码学的观点来看是不幸的，但从数论的观点来看将会产生重要的后果。最后，研究人员将继续她关于薄群的数论工作，例如潜伏在马尔科夫三元组后面的那个。她的目标是将局部到全局原理的结果推广到各种圆填充中；目前已知当与填充相连的对称群包含某些NICE群时，这样的原理是存在的，她计划放松这一限制。该项目的另一个目标是建立关于阿波罗包装中增厚的主要成分的结果。这一奖项反映了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.