Cryptographic Applications of Analytic Number Theory

by Shparlinski, A.

• ISBN13: 9783764366544
• ISBN10: 3764366540
• Edition: 2nd
• Format: Hardcover
• Copyright: 2002-12-01
• Publisher: Birkhauser

Summary

The book introduces new ways of using analytic number theory in cryptography and related areas, such as complexity theory and pseudorandom number generation. Cryptographers and number theorists will find this book useful. The former can learn about new number theoretic techniques which have proved to be invaluable cryptographic tools, the latter about new challenging areas of applications of their skills.

Table of Contents

Preface
Acknowledgments
Introduction	p. 1
Preliminaries	p. 15
Basic Notation and Definitions	p. 17
Polynomials and Recurrence Sequences	p. 27
Exponential Sums	p. 37
Distribution and Discrepancy	p. 61
Arithmetic Functions	p. 67
Lattices and the Hidden Number Problem	p. 83
Complexity Theory	p. 103
Approximation Complexity of the Discrete Logarithm	p. 107
Approximation of the Discrete Logarithm Modulo p	p. 109
Approximation of the Discrete Logarithm Modulo p - 1	p. 123
Approximation of the Discrete Logarithm by Boolean Functions	p. 129
Approximation of the Discrete Logarithm by Real Polynomials	p. 143
Approximation and Complexity of the Diffie-Hellman Secret Key	p. 157
Polynomial Approximation and Arithmetic Complexity of the Diffie-Hellman Secret Key	p. 159
Boolean Complexity of the Diffie Hellman Secret Key	p. 179
Bit Security of the Diffie-Hellman Secret Key	p. 189
Other Cryptographic Constructions	p. 195
Security Against the Cycling Attack on the RSA and Timed-release Crypto	p. 197
The Insecurity of the Digital Signature Algorithm with Partially Known Nonces	p. 201
Distribution of the ElGamal Signature	p. 207
Bit Security of the RSA Encryption and the Shamir Message Passing Scheme	p. 211
Bit Security of the XTR and LUC Secret Keys	p. 217
Bit Security of NTRU	p. 223
Distribution of the RSA and Exponential Pairs	p. 231
Exponentiation and Inversion with Precomputation	p. 239
Pseudorandom Number Generators	p. 247
RSA and Blum-Blum-Shub Generators	p. 249
Naor-Reingold Function	p. 271
1/M Generator	p. 279
Inversive, Polynomial and Quadratic Exponential Generators	p. 283
Subset Sum Generators	p. 295
Other Applications	p. 301
Square-Freeness Testing and Other Number-Theoretic Problems	p. 303
Trade-off Between the Boolean and Arithmetic Depths of Modulo p Functions	p. 309
Polynomial Approximation, Permanents and Noisy Exponentiation in Finite Fields	p. 325
Special Polynomials and Boolean Functions	p. 333
Concluding Remarks and Open Questions	p. 341
Bibliography	p. 367
Index	p. 409
Table of Contents provided by Blackwell. All Rights Reserved.