The subset sum pseudorandom generator

Speaker: Prof. Joachim von zur Gathen , Bonn-Aachen International Center for Information Technology.


I present several results concerning a pseudorandom generator introduced by Rueppel and Massey in 1985. It is a streamed version of the NP-complete subset sum problem, where the stream is given by a linearly recurrent sequence. I start with several attacks on this generator, some of which are rigorously proven while others are heuristic. They work when one “half” of the secret is given, either the linearly recurrent stream or the summands in the problem. In a typical setting, this reduces the security from the previously assumed n^2 bit to n bits. It is conjectured that the generator is secure at this level.
Next come improved implementations of the generator. Some special choices of the secret parameters speed up the naive usage of this generator without losing the property of uniform distribution. These results confirm that the generator can be useful for both cryptographic and Quasi Monte Carlo applications.