Welcome to the resource topic for 2003/123
Title:
Assessing security of some group based cryptosystems
Authors: Vladimir Shpilrain
Abstract:One of the possible generalizations of the discrete logarithm
problem to arbitrary groups is the so-called conjugacy search
problem. 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 suggest
various 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 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.
ePrint: https://eprint.iacr.org/2003/123
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .