International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Combinatorial group theory and public key cryptography

Authors:
Vladimir Shpilrain
Gabriel Zapata
Download:
URL: http://eprint.iacr.org/2004/242
Search ePrint
Search Google
Abstract: After some excitement generated by recently suggested public key exchange protocols due to Anshel-Anshel-Goldfeld and Ko-Lee et al., it is a prevalent opinion now that the conjugacy search problem is unlikely to provide sufficient level of security if a braid group is used as the platform. In this paper we address the following questions: (1) whether choosing a different group, or a class of groups, can remedy the situation; (2) whether some other ``hard" problem from combinatorial group theory can be used, instead of the conjugacy search problem, in a public key exchange protocol. Another question that we address here, although somewhat vague, is likely to become a focus of the future research in public key cryptography based on symbolic computation: (3) whether one can efficiently disguise an element of a given group (or a semigroup) by using defining relations.
BibTeX
@misc{eprint-2004-12211,
  title={Combinatorial group theory and public key cryptography},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / public-key cryptography, combinatorial cryptography},
  url={http://eprint.iacr.org/2004/242},
  note={ shpil@groups.sci.ccny.cuny.edu 12678 received 17 Sep 2004},
  author={Vladimir Shpilrain and Gabriel Zapata},
  year=2004
}