International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Dima Ruinskiy
Adi Shamir
Boaz Tsaban
Download:
URL: http://eprint.iacr.org/2006/244
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21737,
  title={Length-based cryptanalysis: The case of Thompson's Group},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / length based attacks, Thompson's group, combinatorial group theory},
  url={http://eprint.iacr.org/2006/244},
  note={ boaz.tsaban@weizmann.ac.il 13346 received 17 Jul 2006},
  author={Dima Ruinskiy and Adi Shamir and Boaz Tsaban},
  year=2006
}