Domingo Gómez-Pérez

The shrinking generator is a pseudorandom bit generator based on the combination of two linear feedback shift registers of maximum period. These registers are synchronized with a common clock and produce binary sequences with good statistical properties. Due to its simplicity and efficient implementation, the shrinking generator is particularly suitable for stream cipher cryptographic schemes and most proposed attacks rely on the properties of the generator. Furthermore, its analysis serves as the foundation for other interleave constructions. In our work, we present a new algorithm which allows to compute the linear complexity for shrunken sequences in an efficient way together with a closed formula for the linear complexity of its output in certain conditions. Additionally, we establish the first bound on its linear complexity profile and a conjecture about the values of the linear complexity of these sequences. Our techniques involve two-dimensional arrays and their interleave structure, which could prove valuable for other pseudorandom bit generators.

Gaussian random number generators attract a widespread interest due to their applications in several fields. Important requirements include easy implementation, tail accuracy, and, finally, a flat spectrum. In this work, we study the applicability of uniform pseudorandom binary generators in combination with the Central Limit Theorem to propose an easy to implement, efficient and flexible algorithm that leverages the properties of the pseudorandom binary generator used as an input, specially with respect to the correlation measure of higher order, to guarantee the quality of the generated samples. Our main result provides a relationship between the pseudorandomness of the input and the statistical moments of the output. We propose a design based on the combination of pseudonoise sequences commonly used on wireless communications with known hardware implementation, which can generate sequences with guaranteed statistical distribution properties sufficient for many real life applications and simple machinery. Initial computer simulations on this construction show promising results in the quality of the output and the computational resources in terms of required memory and complexity.