Cryptanalysis of a pseudorandom generator based on braid groups

Authors: Rosario Gennaro and Daniele Micciancio

Advances in Cryptology - Eurocrypt 2002. Amsterdam, The Netherlands, April 28-May 2, 2002. Lectture Notes in Computer Science 2332, Springer-Verlag, pp. 1-13

[BibTeX] [Postscript] [PDF]

Abstract: We show that the decisional version of the Ko-Lee assumption for braid groups put forward by Lee, Lee and Hahn at Crypto 2001 is false, by giving an efficient algorithm that solves (with high probability) the corresponding decisional problem. Our attack immediately applies to the pseudo-random generator and synthesizer proposed by the same authors based on the decisional Ko-Lee assumption, and shows that neither of them is cryptographically secure.