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.

该提案的目的是解决小组理论中的各种搜索问题。自20世纪初，自从Dehn提出以来，已经研究了群体理论中的决策问题已有100多年了，现在三个著名的决策问题通常被称为Dehn的问题：问题问题，共轭问题和同构问题。 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科学，与解决相应决策问题所引起的截然不同的科学。拟议的研究的潜在更广泛的影响是广泛的。可以挑出对信息安全的一般领域的影响。几个经过深思熟虑的问题的困难，例如整数分解和离散对数问题是现实应用程序中使用的大多数当前公用密钥密码协议的基础。 根据其他搜索问题制定公钥协议，例如从鲁棒性的角度来看，群体理论家对困难进行了很好的研究的共轭搜索问题是谨慎的，特别是如果分解或相关发展威胁到当前协议的安全性。非亚伯式无限群体的复杂性是新方案的有前途的肥沃基础，并且需要大量的初步工作，例如此处提出的工作。