Cryptology ePrint Archive: Report 2006/244

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

Dima Ruinskiy, Adi Shamir, 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.

Category / Keywords: public-key cryptography / length based attacks, Thompson's group, combinatorial group theory

Date: received 17 Jul 2006

Contact author: boaz tsaban at weizmann ac il

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20060718:192032 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]