Design of hashing algorithms (Q1310281)

This book is a very well written survey of hashing algorithms for the purposes of cryptology. Pointing out that many algorithms once believed to be secure have proved to be insecure under more sophisticated attacks, the authors stress principles for the design of hashing algorithms, classifying them according to whether they apply a block cipher as the underlying one-way function or not. The first four chapters are expository and written in a telegraphic, though clear style. They concern various definitions and schemes for the classification of hash functions, methods of attack on has schemes, depending on whether the scheme is random (e.g., the birthday attack) or nonrandom (e.g., differential cryptanalysis), and pseudorandomness of permutation generators (PPGs) (including the Luby-Rackoff construction of a PPG with three rounds of DES-like permutations and three independent pseudorandom function generators). The new material begins in Chapter 5, in which the authors present necessary and sufficient conditions for the construction of super-PPGs (i.e., the block cryptosystem is secure against a chosen plaintext/ciphertext attack), and use this to show that four rounds of DES-like permutations with a single random function is not super- pseudorandom. In Chapter 6 the authors present their improvement of the Luby-Rackoff construction and show that the composition of two Luby-Rackoff structures with four random function generators and two random permutation generators provides a perfect randomizer. They recommend that a structure consisting of super-PPG with a single pseudorandom function generator be used in the design of block ciphers, because it exhibits better cryptographic strength against a chosen plaintext/ciphertext attack. Chapter 7 is concerned with the construction of strong one-way permutations (i.e., with \(n\) hard bits and any \(t<n-O( \log n)\) input bits simultaneously hard) and pseudorandom bit generators with maximum efficiency. In Chapter 8 they extend this to give two ways of constructing a family of strong one-way permutations such that all input bits are hard and any \(t<n-O( \log n)\) input bits are indistinguishable from a random string. Both ways use the structure of polynomials over \(GF(2^ n)\). The author's original contributions have appeared elsewhere in proceedings of various conferences. Having them all together in this book should be useful to anyone interested in data security or in cryptanalysis.