Cryptology ePrint Archive: Report 2005/264
On an authentication scheme based on the Root Problem in the braid group
Abstract: Lal and Chaturvedi proposed two authentication sche\-mes presumably
based on the difficulty of the Root Problem in the braid group.
We describe a deterministic linear time algorithm to crack
the first scheme, and show that
the second scheme is not more secure than schemes based on the
Conjugacy Search Problem, and can therefore be cracked by existing
heuristic attacks with very good success probability, as long as
the parameters are practical.
Category / Keywords: public-key cryptography / braid group, authentication, root problem
Date: received 10 Aug 2005, last revised 10 May 2009
Contact author: boaz tsaban at weizmann ac il
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Note: An erroneous proof in the previous version is fixed, and a discussion of the second scheme is added.
Version: 20090510:111143 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]