Cryptanalysis of a Pseudorandom Generator Based on Braid Groups

摘要

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.