Cryptographic Applications of Analytic Number Theory

1. Front Matter

   Pages i-ix

   PDF

2. Introduction

   1. Introduction

      • Igor Shparlinski

      Pages 1-14

3. Preliminaries

   1. Front Matter

      Pages 15-15

      PDF

   2. Basic Notation and Definitions

      • Igor Shparlinski

      Pages 17-26

   3. Polynomials and Recurrence Sequences

      • Igor Shparlinski

      Pages 27-36

   4. Exponential Sums

      • Igor Shparlinski

      Pages 37-60

   5. Distribution and Discrepancy

      • Igor Shparlinski

      Pages 61-65

   6. Arithmetic Functions

      • Igor Shparlinski

      Pages 67-81

   7. Lattices and the Hidden Number Problem

      • Igor Shparlinski

      Pages 83-102

   8. Complexity Theory

      • Igor Shparlinski

      Pages 103-106

4. Approximation and Complexity of the Discrete Logarithm

   1. Front Matter

      Pages 107-107

      PDF

   2. Approximation of the Discrete Logarithm Modulo p

      • Igor Shparlinski

      Pages 109-122

   3. Approximation of the Discrete Logarithm Modulo p — 1

      • Igor Shparlinski

      Pages 123-128

   4. Approximation of the Discrete Logarithm by Boolean Functions

      • Igor Shparlinski

      Pages 129-141

   5. Approximation of the Discrete Logarithm by Real Polynomials

      • Igor Shparlinski

      Pages 143-156

5. Approximation and Complexity of the Diffie—Hellman Secret Key

   1. Front Matter

      Pages 157-157

      PDF

   2. Polynomial Approximation and Arithmetic Complexity of the Diffie-Hellman Secret Key

      • Igor Shparlinski

      Pages 159-177

   3. Boolean Complexity of the Diffie-Hellman Secret Key

      • Igor Shparlinski

      Pages 179-188

   4. Bit Security of the Diffie—Hellman Secret Key

      • Igor Shparlinski

      Pages 189-194

6. Other Cryptographic Constructions

   1. Front Matter

      Pages 195-195

      PDF

The book introduces new techniques that imply rigorous lower bounds on the com­ plexity of some number-theoretic and cryptographic problems. It also establishes certain attractive pseudorandom properties of various cryptographic primitives. These methods and techniques are based on bounds of character sums and num­ bers of solutions of some polynomial equations over finite fields and residue rings. Other number theoretic techniques such as sieve methods and lattice reduction algorithms are used as well. The book also contains a number of open problems and proposals for further research. The emphasis is on obtaining unconditional rigorously proved statements. The bright side of this approach is that the results do not depend on any assumptions or conjectures. On the downside, the results are much weaker than those which are widely believed to be true. We obtain several lower bounds, exponential in terms of logp, on the degrees and orders of o polynomials; o algebraic functions; o Boolean functions; o linear recurrence sequences; coinciding with values of the discrete logarithm modulo a prime p at sufficiently many points (the number of points can be as small as pI/2+O:). 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.

• Cryptography
• Digital Signature Algorithm
• Nonce
• Sage
• complexity
• complexity theory
• computer science
• finite field
• number theory

From the reviews:

“Igor Shparlinski is a very prolific mathematician and computer scientist … . The book is written at a very high level, suitable for graduate students and researchers in computer science and mathematics. … book has a unique perspective, and is not really comparable to other books in the area. … book contains many deep results, and the mathematically-sophisticated reader can find much that is novel. … this is an impressive work that will be of significant interest to researchers in cryptography and algorithmic number theory.” (Jeffrey Shallit, SIGACT News, Vol. 41 (3), September, 2010)

• Department of Computing, Macquarie University, Australia

  Igor Shparlinski

Policies and ethics