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.
