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

TC：小型：协作研究：从群论和应用中证明安全性

• 批准号: 1117675
• 负责人: Nelly Fazio
• 金额: $ 45.73万
• 依托单位: CUNY City College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-15 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117675&HistoricalAwards=false
• 关键词: TC; Small; Collaborative; Research; Provable

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.

信息技术是现代社会基础设施的组成部分，而密码学是信息安全的基石。可证明安全性量化了密码结构对攻击的弹性。这种量化通常与少数参考“棘手”问题（如整数分解）的硬度有关。由于异质性的内在强度，多样化的棘手问题集增强了整体结构的鲁棒性。这个项目通过从组合群理论的问题中建立密码学的基础来应对这一挑战。该项目利用了早期对组合群理论中标准计算问题（如“词问题”）的算法不可解性的研究成果，但通过概率建模的视角来看待它们，这是现代密码学的特点。研究目标可分为三个主要类别：1)识别有效的可抽样分布，在这些分布上标准计算群论问题的（变体）平均仍然困难；2)提出新的“群论硬学习问题”；3)探索这一基础工作对具有增强加密功能的应用程序的影响，其长期目标是推导具有同态性质的公钥加密的群论实例。该项目的成果将通过新的工具和替代方案丰富密码学的理论和实践，刺激整个密码学和群论社区的研究人员，从而促进两个领域之间的合作。这项研究需要大量的学生参与研究，这些机构的服务对象是历史上在计算机科学和数学领域代表性不足的人口统计学群体。