A practical attack on a braid group based cryptographic protocol

Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

36 Scopus citations

Abstract

In this paper we present a practical heuristic attack on the Ko, Lee et al. key exchange protocol introduced at Crypto 2000 [11]. Using this attack, we were able to break the protocol in about 150 minutes with over 95% success rate for typical parameters. One of the ideas behind our attack is using Dehornoy's handle reduction method as a counter measure to diffusion provided by the Garside normal form, and as a tool for simplifying braid words. Another idea employed in our attack is solving the decomposition problem in a braid group rather than the conjugacy search problem.

Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2005 - 25th Annual International Cryptology Conference, Proceedings
Pages86-96
Number of pages11
StatePublished - 2006
Event25th Annual International Cryptology Conference, CRYPTO 2005 - Santa Barbara, CA, United States
Duration: 14 Aug 200518 Aug 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3621 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th Annual International Cryptology Conference, CRYPTO 2005
Country/TerritoryUnited States
CitySanta Barbara, CA
Period14/08/0518/08/05

Fingerprint

Dive into the research topics of 'A practical attack on a braid group based cryptographic protocol'. Together they form a unique fingerprint.

Cite this