Paper 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.
Note: An erroneous proof in the previous version is fixed, and a discussion of the second scheme is added.
Metadata
- Available format(s)
-
PDF
PS
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- braid groupauthenticationroot problem
- Contact author(s)
- boaz tsaban @ weizmann ac il
- History
- 2009-05-10: revised
- 2005-08-11: received
- See all versions
- Short URL
- https://ia.cr/2005/264
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2005/264,
author = {Boaz Tsaban},
title = {On an authentication scheme based on the Root Problem in the braid group},
howpublished = {Cryptology {ePrint} Archive, Paper 2005/264},
year = {2005},
url = {https://eprint.iacr.org/2005/264}
}
