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.

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