Cryptographic applications of analytic number theory. Complexity lower bounds and pseudo\-randomness
type: Item
instance of: scholarly article
title: Cryptographic applications of analytic number theory. Complexity lower bounds and pseudo\-randomness
zbMATH Open document ID: 1036.94001
author: Igor E. Shparlinski
published in: Progress in Computer Science and Applied Logic
publication date: 2003-01-28T00:00:00Z
review text: This is a greatly expanded and updated version of the author's book ``Number Theoretic Methods in Cryptography'' [Birkhäuser, Basel (1999; Zbl 0912.11057)]. As in the earlier book, the emphasis is on rigorous lower bounds on the complexity of cryptologic problems that are established by means of bounds for character sums and for the number of solutions of equations and congruences. The present book uses also sieve methods and lattice reduction algorithms as additional tools. The first three parts of the book basically follow the lines of the corresponding parts of the earlier book. The remaining parts of the book offer mostly new material. Part IV studies properties such as uniformity of distribution, high linear complexity, and bit security for various cryptographic schemes (RSA, XTR, LUC, NTRU, DSA, ElGamal). Part V on pseudorandom numbers contains results on period length, uniformity of distribution, and linear complexity for pseudorandom number generators such as the power generator, the \(1/M\) generator, the inversive congruential generator, and the subset sum generator. Part VI presents applications to some other algorithmic, cryptographic, and complexity-theoretic problems and, in particular, a proof of the beautiful result that for any nonlinear function modulo a prime either its arithmetic depth or its Boolean depth is large. The book concludes with a long list of open problems and a substantial bibliography. This monograph is essential reading for anybody interested in the rigorous complexity analysis of cryptologic problems. The book is also a treasure trove of powerful technical tools that are bound to lead to further deep complexity results in the future.
Mathematics Subject Classification ID: 94-02
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1860380
zbMATH Keywords: cryptography
zbMATH Keywords: lower bounds on complexity
zbMATH Keywords: sieve methods
zbMATH Keywords: lattice reduction algorithms
zbMATH Keywords: pseudorandom numbers
zbMATH Keywords: uniformity of distribution
zbMATH Keywords: linear complexity
reviewed by: Harald Niederreiter
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1860380