Number Theoretic Methods in Cryptography Complexity lower bounds
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. I...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Basel
Birkhäuser
1999, 1999
|
| Edition: | 1st ed. 1999 |
| Series: | Progress in Computer Science and Applied Logic
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- I Preliminaries
- 1 Introduction
- 2 Basic Notation and Definitions
- 3 Auxiliary Results
- II Approximation and Complexity of the Discrete Logarithm
- 4 Approximation of the Discrete Logarithm Modulo p
- 5 Approximation of the Discrete Logarithm Modulo p — 1
- 6 Approximation of the Discrete Logarithm by Boolean Functions
- 7 Approximation of the Discrete Logarithm by Real and Complex Polynomials
- III Complexity of Breaking the Diffie-Hellman Cryptosystem
- 8 Polynomial Approximation and Arithmetic Complexity of the Diffie-Hellman Key
- 9 Boolean Complexity of the Diffie-Hellman Key
- IV Other Applications
- 10 Trade-off between the Boolean and Arithmetic Depths of Modulo p Functions
- 11 Special Polynomials and Boolean Functions
- 12 RSA and Blum-Blum-Shub Generators of Pseudo-Random Numbers
- V Concluding Remarks
- 13 Generalizations and Open Questions
- 14 Further Directions