2003/11/04 by Vladimir Shpilrain, Shpilrain, Vladimir
Computer Science · Mathematics · #20F36 #68Q17 #Coding theory and cryptography #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #cs.CC #cs.CR #math.GR #msc:20F36 #msc:68Q17
paper · pdf · doi:10.48550/arxiv.math/0311047
10 pages
arxiv created 2003/11/04 · openalex publication_date 2003/11/04 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One of the possible generalizations of the discrete logarithm problem to arbitrary groups is the so-called conjugacy search problem (sometimes erroneously called just the conjugacy problem): given two elements a, b of a group G and the information that ax=b for some x ∈ G, find at least one particular element x like that. Here ax stands for xax-1. The computational difficulty of this problem in some particular groups has been used in several group based cryptosystems. Recently, a few preprints have been in circulation that suggested various "neighbourhood search" type heuristic attacks on the conjugacy search problem. The goal of the present survey is to stress a (probably well known) fact that these heuristic attacks alone are not a threat to the security of a cryptosystem, and, more importantly, to suggest a more credible approach to assessing security of group based cryptosystems. Such an approach should be necessarily based on the concept of the average case complexity (or expected running time) of an algorithm. These arguments support the following conclusion: although it is generally feasible to base the security of a cryptosystem on the difficulty of the conjugacy search problem, the group G itself (the "platform") has to be chosen very carefully. In particular, experimental as well as theoretical evidence collected so far makes it appear likely that braid groups are not a good choice for the platform. We also reflect on possible replacements.