Number theoretic methods in cryptography. Complexity lower bounds

Publication date 23 February 1999

Published in Progress in Computer Science and Applied Logic (Search for Journal in Brave)

algebraic functions Blum-Blum-Schub generator Boolean functions degrees and orders of polynomials Diffie-Hellman cryptosystem discrete logarithm interpolating polynomials linear recurring sequences lower bounds on complexity open problems permutation polynomials polynomial representations of nonlinear pseudo-random number generators prime field primitive root testing RSA generator Zech logarithms

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to number theory (11-02) Exponential sums (11T23) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Cryptography (94A60)

Review text

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.

Recommendations

Cited in

(27)

This page was built for publication: Number theoretic methods in cryptography. Complexity lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1276548)