TC: Small: Collaborative Research: Provable Security from Group Theory and Applications

信息技术是现代社会基础设施的既定组成部分，而密码学是信息安全的基石。可证明安全性量化了密码结构对攻击的恢复能力。这种量化通常与少数引用“棘手”问题(如整数因式分解)的难度有关。由于异质性的内在力量，使一组棘手的问题多样化，增强了整体结构的稳健性。这个项目通过从组合群论中的问题建立密码学的基础来回应这一挑战。该项目利用了早期关于组合群论中标准计算问题的算法不可解性的努力，但通过现代密码学的特征-概率建模的视角来看待它们。研究目标可分为三大类：1)确定标准计算群论问题的变体在其上仍然是平均困难的有效可抽样分布；2)开发新的硬群论学习问题；3)探索这一基础性工作对具有增强密码功能的应用的影响，长期目标是获得具有同态性质的公钥密码学的群论实例化。该项目的结果将通过新的工具和备选方案丰富密码学的理论和实践，激励密码学和群论社区的研究人员，从而促进这两个领域之间的合作。开展这项研究需要学生大量参与机构的研究，这些机构服务于在计算机科学和数学领域历来代表性不足的人口群体。

Information technology is an established component of the infrastructure of modern societies, and cryptography is a cornerstone of information security. Provable security quantifies the resilience of cryptographic constructions to attacks. This quantification is often relative to the hardness of a handful of reference "intractable" problems like integer factorization. Because of the intrinsic strength of heterogeneity, diversifying the set of intractable problems enhances the robustness of the overall structure. This project responds to the challenge by building a foundation for cryptography from problems in combinatorial group theory.The project capitalizes on earlier efforts on the algorithmic unsolvability of standard computational problems in combinatorial group theory like the "word problem", but looks at them through the lens of the probabilistic modeling, characteristic of modern cryptography. The research objectives can be grouped into three main categories: 1) identifying efficiently sampleable distributions on which (variants of) the standard computational group-theoretic problems remain _difficult on average_; 2) developing new _hard group-theoretic learning problems_; and 3) exploring the implications of this foundational work to applications with enhanced cryptographic functionality, with the long-term goal of deriving group-theoretic instantiations of public-key cryptography with homomorphic properties.Results of this project will enrich the theory and practice of cryptography with new tools and alternatives, stimulating for researchers throughout the cryptography and group-theory communities, thus fostering collaborations between the two fields. The undertaking of the research entails significant student participation in research at institutions that serve demographic groups that have been historically underrepresented in computer science and mathematics.