Paper 2006/244

Length-based cryptanalysis: The case of Thompson's Group

Dima Ruinskiy, Adi Shamir, and Boaz Tsaban

Abstract

The length-based approach is a heuristic for solving randomly generated equations in groups which possess a reasonably behaved length function. We describe several improvements of the previously suggested length-based algorithms, that make them applicable to Thompson's group with significant success rates. In particular, this shows that the Shpilrain-Ushakov public key cryptosystem based on Thompson's group is insecure, and suggests that no practical public key cryptosystem based on this group can be secure.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
length based attacksThompson's groupcombinatorial group theory
Contact author(s)
boaz tsaban @ weizmann ac il
History
2006-07-18: received
Short URL
https://ia.cr/2006/244
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/244,
      author = {Dima Ruinskiy and Adi Shamir and Boaz Tsaban},
      title = {Length-based cryptanalysis: The case of Thompson's Group},
      howpublished = {Cryptology ePrint Archive, Paper 2006/244},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/244}},
      url = {https://eprint.iacr.org/2006/244}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.