Collaborative Research: Theoretical and experimental approaches to search problems in group theory

协作研究：群论中搜索问题的理论和实验方法

• 批准号: 0914778
• 负责人: Vladimir Shpilrain
• 金额: $ 7.35万
• 依托单位: CUNY City College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-15 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914778&HistoricalAwards=false
• 关键词: Collaborative; Research; Theoretical; experimental; approaches

The objective of this proposal is to address various search problems in group theory. Decision problems in group theory have been studied for over 100 years now, since Dehn put forward, in the beginning of the 20th century, the three famous decision problems now often referred to as Dehn's problems: the word problem, the conjugacy problem, and the isomorphism problem. In general, decision problems are problems of the following nature: given a property P and an input O, find out whether or not the input O has the property P. On the other hand, search problems are of the following nature: given a property P and an input O with the property P, find a proof (sometimes called a "witness") of the fact that O has the property P. This is a substantial shift of paradigm, and in fact, studying search problems often gives rise to new research avenues in mathematics or computer science, very different from those prompted by addressing the corresponding decision problems.The potential broader impacts of the proposed research are extensive; the impact on the general area of information security can be singled out. The difficulty of several well-studied problems, e.g. integer factorization and the discrete logarithm problem underlie most current public-key cryptographic protocols used in real-life applications. Developing public-key protocols based upon other search problems, e.g. the conjugacy search problem whose difficulty has been well studied by group theorists, is prudent from the standpoint of robustness, particularly if factorization or related developments threaten the security of current protocols. The complexity of non-abelian infinite groups is a promising fertile ground for new protocols and there is a great deal of preliminary work required such as that proposed here.

这个建议的目的是解决各种搜索问题的群论。自Dehn在世纪初提出三个著名的决策问题--字问题、共轭问题和同构问题以来，群论中的决策问题的研究已有100多年的历史。一般来说，决策问题是具有以下性质的问题：给定一个属性P和一个输入O，找出输入O是否具有属性P。给定属性P和具有属性P的输入O，找到证据（有时称为“见证”）O具有属性P的事实。这是范式的实质性转变，事实上，对搜索问题的研究通常会在数学或计算机科学中产生新的研究途径，与解决相应的决策问题所产生的研究途径截然不同。2所提出的研究的潜在影响是广泛的; 3对信息安全的一般领域的影响可以单独列出。一些研究得很好的问题，如整数分解和离散对数问题的困难是当前大多数公钥密码协议在现实生活中使用的基础。 从鲁棒性的角度来看，基于其他搜索问题（例如，群论学家已经充分研究了其难度的共轭搜索问题）开发公钥协议是谨慎的，特别是如果因子分解或相关发展威胁到当前协议的安全性。非阿贝尔无限群的复杂性是一个有前途的肥沃土壤，新的协议，有大量的前期工作需要，如这里提出的。