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

Dima Ruinskiy; Adi Shamir; Boaz Tsaban

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 attacks Thompson's group combinatorial group theory
Contact author(s): boaz tsaban @ weizmann ac il
History: 2006-07-18: received
Short URL: https://ia.cr/2006/244
License: 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},
      url = {https://eprint.iacr.org/2006/244}
}