On Polymomial Approximation and the Parallel Complexity of the Discrete Logarithm and Breaking the Diffie-Hellman Cryptosystem

Several exponential (in terms of log p) lower bounds are obtained on the degrees and orders of

  • polynomials;
  • a algebraic functions;
  • Boolean functions;
  • linear recurring sequences

coinciding with values of the discrete logarithm modulo a prime p at sufficiently many points (the number of points can be as little as p1/2+). These functions are considered over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1. The case of d = 2 is of special interest since it corresponds to the representation of the rightmost bit of the discrete logarithm and defines whether the argument is a quadratic residue. These results are used to obtain lower bounds on the parallel complexity of computing the discrete logarithm.

The method is based on bounds of character sums and numbers of solutions of some polynomial equations.

Similar results are obtained for breaking the Diffie-Hellman cryptosystern. Several other applications of the method are indicated as well.

By: Don Coppersmith, Igor Shparlinski

Published in: RC20724 in 1997

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

RC20724.pdf

Questions about this service can be mailed to reports@us.ibm.com .