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

Project: Research project

Project Details

Description

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.

StatusFinished
Effective start/end date15/09/0931/08/12

Funding

  • National Science Foundation

Fingerprint

Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.