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

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

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.