Cryptographic applications of analytic number theory. Complexity lower bounds and pseudo\-randomness (Q1854908)

This is a greatly expanded and updated version of the author's book ``Number Theoretic Methods in Cryptography'' [Birkhäuser, Basel (1999; Zbl 0912.11057)]. As in the earlier book, the emphasis is on rigorous lower bounds on the complexity of cryptologic problems that are established by means of bounds for character sums and for the number of solutions of equations and congruences. The present book uses also sieve methods and lattice reduction algorithms as additional tools. The first three parts of the book basically follow the lines of the corresponding parts of the earlier book. The remaining parts of the book offer mostly new material. Part IV studies properties such as uniformity of distribution, high linear complexity, and bit security for various cryptographic schemes (RSA, XTR, LUC, NTRU, DSA, ElGamal). Part V on pseudorandom numbers contains results on period length, uniformity of distribution, and linear complexity for pseudorandom number generators such as the power generator, the \(1/M\) generator, the inversive congruential generator, and the subset sum generator. Part VI presents applications to some other algorithmic, cryptographic, and complexity-theoretic problems and, in particular, a proof of the beautiful result that for any nonlinear function modulo a prime either its arithmetic depth or its Boolean depth is large. The book concludes with a long list of open problems and a substantial bibliography. This monograph is essential reading for anybody interested in the rigorous complexity analysis of cryptologic problems. The book is also a treasure trove of powerful technical tools that are bound to lead to further deep complexity results in the future.