Pseudorandomness and cryptography: Number theoretic methods

During the last century, number theoretical problems arose in many applications, such as cryptography, communication systems or numerical methods. This project is devoted to the study of number theoretical problems motivated by such applications. Pseudorandom sequences, for example sequences which are generated with deterministic algorithms but which seem to be random, have many applications, for example for cryptography, for wireless communication or for numerical methods. Based on the particular application, many different approaches for pseudorandomness have been given. The first aim of the project is to investigate the connection between different notions of pseudorandomness, namely between the NIST test suite introduced by the National Institute of Standards and Technology (U.S.) and more theoretical measures of pseudorandomness (the so-called well-distribution and correlation measures). In addition, pseudorandom properties of automatic sequences (that is sequences which are generated by a finite automaton) shall be analyzed. In number theory, elliptic curves are especially important objects. They were used in the proof of Fermat`s Last Theorem and they are also applied in cryptography and integer factorization. In this project, the properties of sequences generated by elliptic curve methods shall be studied. It is worth to consider this topic from a dynamical system point of view, as pseudorandom number generators are not the only application in this area. Finally, during the project, highly nonlinear Boolean and vectorial Boolean functions shall be studied. They play an important role in many applications such as pseudorandom sequence generation, design of block ciphers and coding theory. Instead of finding new functions with required nonlinear properties the project mainly focuses on their structural properties.

During the last century, number theoretical problems arose in many applications, such as cryptography, communication systems or numerical methods. This project was devoted to the study of number theoretical problems motivated by such applications. Pseudorandom sequences, for example sequences which are generated with deterministic algorithms but which seem to be random, have many applications, for example for cryptography, for wireless communication or for numerical methods. Based on the particular application, many different approaches for pseudorandomness have been given. The first aim of the project was to investigate the randomness properties of certain sequences. Among others, we studied the properties of sequences generated by hyperelliptic curve methods. In number theory, elliptic and hyperelliptic curves are especially important objects. They were used in the proof of Fermat's Last Theorem and they are also applied in cryptography and integer factorization. We proved that such sequences possess good randomness properties. A natural way to obtain randomly looking sequences is to start with some initial number and iterate certain transformation on this value. Such sequences are called dynamical systems. We investigated structural properties of dynamical systems which are attractive candidates of pseudorandom numbers. During the project, we also investigated digital properties of certain integers. For example, we investigated the distribution of digits of Mersenne numbers. We showed that the least significant digits of such numbers are well-distributed. Finally, during the project, highly nonlinear Boolean and vectorial Boolean functions were studied. They play an important role in many applications such as pseudorandom sequence generation, design of block ciphers and coding theory. Instead of finding new functions with required nonlinear properties the project mainly focused on their structural properties.