Cryptology ePrint Archive: Report 2005/264

On an authentication scheme based on the Root Problem in the braid group

Boaz Tsaban

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 format(s): 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)

Short URL: ia.cr/2005/264

Discussion forum: Show discussion | Start new discussion