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

这项建议的目的是解决群论中的各种搜索问题。群论中的决策问题研究已有100多年的历史，自20世纪初Dehn提出三个著名的决策问题以来，这三个著名的决策问题现在通常被称为Dehn问题：字问题、共轭问题和同构问题。一般而言，决策问题是如下性质的问题：给定属性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.