Efficient cryptographic hash functions and methods for amplifying the security of hash functions and pseudo-random functions

DETAILED DESCRIPTION These shortcomings as well as other deficiencies and limitations in the art are obviated, in accordance with the present invention, in which the One-Way Hash Function generator, in contrast to the prior art: (1) uses a strong pseudo-random generator--only recently have strong pseudo-random generators become efficient enough to be practical for use in the design of a OWHF; and (2) generates a pseudo-random function from 2n bits to 2n bits given a pseudo-random function from n bits to n bits.
To compute pseudo-random function keys from input data, one may use any universal hash function which (a) has output length larger than the input length by enough margin to rule out two inputs having the same hash value with a good probability (over the choice of hash function parameters) and (b) has the property that given an input and its hash value, the hash value of another input remains largely unpredictable.
Herein is provided an efficient universal hash function which is called the Finite Field Subset Sum (FFSS) hashing.
Both FFSS hashing and the pseudo-random function construction are of separate and independent interest and have applications beyond their use in the OWHF scheme.
For example, the PRF doubling construction has immediate application to increasing the difficulty of attacking existing hash functions like MD5, SHA, or pseudo-random functions like DES using birthday attacks or their generalizations.
For example, doubling the output length of MD5 using the construction of the present random invention from 128 bits to 256 bits increases the number of steps needed for a birthday attack from 2.
sup.
64 to 2.
sup.
128, as long as MD5 is sufficiently pseudo-random.
Broadly, in accordance with the present invention, output bits corresponding to a one-way hash function of input bits are iteratively generated.
Upon each iteration, a current hash function is produced.
The methodology utilizes a butterfly pseudo-random function generator, operative with a set of keys, and a finite field subset-sum generator arrangement