TY - GEN
T1 - A practical attack on a braid group based cryptographic protocol
AU - Myasnikov, Alexei
AU - Shpilrain, Vladimir
AU - Ushakov, Alexander
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33745146187&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33745146187&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:33745146187
SN - 3540281142
SN - 9783540281146
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 86
EP - 96
BT - Advances in Cryptology - CRYPTO 2005 - 25th Annual International Cryptology Conference, Proceedings
T2 - 25th Annual International Cryptology Conference, CRYPTO 2005
Y2 - 14 August 2005 through 18 August 2005
ER -