Friday, 9.6. 14:00
Seminar room Altenbergerstrasse 50
Alvar Ibeas Martin
Predicting pseudorandom sequences from partial information.
Pseudorandom number generators are deterministic methods to obtain sequences which apparently behave as choosen at random. They can be used as the key in a symmetric cryptosystem, but for this purpose it is customary for them to be difficult to predict.
A simple scheme consists of a recurrent sequence of elements in a finite field, where each one is obtained by evaluating a polynomial at the previous element. To avoid interpolation attacks, only the most sifnificative bits of each element are employed. However, using lattice reductions techniques, sometimes this is not secure enough.
For instance, it will be shown a lattice attack employed to predict a Pollard generator which succeeds with high probability when it has access to about two thirds of the most significative bits of two consecutive values.