Paper 2003/123

Assessing security of some group based cryptosystems

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.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
braid groupsconjugacy search problem
Contact author(s)
shpil @ groups sci ccny cuny edu
History
2003-06-16: received
Short URL
https://ia.cr/2003/123
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/123,
      author = {Vladimir Shpilrain},
      title = {Assessing security of some group based cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2003/123},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/123}},
      url = {https://eprint.iacr.org/2003/123}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.