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

SaTC：核心：小：马可夫三元组、密码学和薄群算术

• 批准号: 2154624
• 负责人: Elena Fuchs
• 金额: $ 25.86万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2154624&HistoricalAwards=false
• 关键词: SaTC; CORE; Small; Markoff; Triples

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.

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