Number theoretic methods in cryptography. Complexity lower bounds (Q1276548)

From the Preface of the book: ``The book introduces new techniques which imply rigorous lower bounds on the complexity of some number theoretic and cryptographic problems. These methods and techniques are based on bounds of character sums and numbers of solutions of some polynomial equations over finite fields and residue rings. It also contains a number of open problems and proposals for further research.'' Much of the book is concerned with obtaining lower bounds on the degrees and orders of polynomials, algebraic functions, Boolean functions and linear recurring sequences that give the discrete logarithm modulo a prime \(p\) on some subset of indices, where it is recalled that the discrete logarithm of an element \(x =g^u\) of the residues modulo \(p\) for some fixed primitive element \(g\) is \(u\), also referred to as the index of \(x\), \(\text{ind}(x)\) for \(u\) the least non-negative integer. One can ask about a polynomial \(f(X) \in Z[X]\) that represents the discrete logarithm in the sense that: \[ \text{ind} (x)\equiv f(x)\bmod{p},\qquad x=1,2, \dots, p-1. \] It is known that the unique interpolation polynomial for this problem is of degree \(p-2\), the largest polynomial degree. Much of the volume is concerned with determining bounds on the degree of such interpolating polynomials for partial representations such as on small intervals of the form \([N+1, N+H]\), very sparse sets or on random sets, using the four types of approximation functions previously mentioned. While studying the congruences modulo the prime \(p\) is natural, since \(\text{ind} (x)\) is in the residue ring modulo \(p-1\), approximations modulo \(p-1\) are also studied. In addition the functions are considered over the residue ring modulo an arbitrary divisor \(d\) of \(p-1\) since the case of \(d=2\) corresponds to the representation of the right-most bit of the discrete logarithm, and also whether the argument is a quadratic residue of the prime. The book is in five parts (fourteen chapters): Preliminaries, Approximation and complexity of the discrete logarithm, Complexity of breaking the Diffie-Hellman cryptosystem, Other applications and Concluding remarks. After a rather detailed look at lower bounds on the complexity of the discrete logarithm problem, in the various measures mentioned, the same considerations are applied to the Diffie-Hellman cryptosystem where two correspondents A and B choose, respectively, random exponents \(x\) and \(y\), in an arbitrary finite field with primitive element \(g\), and exchange \(g^x\) and \(g^y\) from which common information \(g^{xy}\) can be computed. The Diffie-Hellman problem then is to compute \(g^{xy}\) from knowledge of \(g^x\) and \(g^y\). The relation to the discrete logarithm problem is immediate, and if the discrete logarithm problem is solvable so is the Diffie-Hellman problem. The complexity of this problem is discussed in the spirit of the results on the discrete logarithm problem. Other related questions on permutation polynomials, polynomial representations of non-linear pseudo-random number generators, powers, Zech logarithms and primitive root testing are also considered in a similar manner. Some results are also given on the pseudo-random properties of power generators, including the RSA generator and the Blum-Blum-Schub generator as special cases, which give the first rigorous evidence on this problem. This volume gives a thorough treatment of the complexity of the discrete logarithm problem in a prime field, as well as related problems. The final chapter on further directions gives an interesting selection of problems which, while not related to the finite field problems discussed here, might be amenable to the techniques developed here.