Tue Mar 31 16:55:21 IDT 1998
Naor and Reingold  have recently introduced two new constructions of very efficient pseudo-random functions, proven to be as secure as the decisional version of the Diffie-Hellman  assumption or the assumption that factoring is hard. In this site we define and exhibit an implementation of the construction which is based on the decisional Diffie-Hellman assumption.
Naor and Reingold define a pseudo-random function as follows: The key of each pseudo-random function is a tuple, , where P is a large prime, Q a large prime divisor of P-1, g an element of order Q in and a uniformly distributed sequence of n+1 elements in . For any n-bit input, , the function is defined by:
This function is the core of our implementation.
The function has domain and range (the subgroup of generated by g). We now show how to adjust in order to get a pseudo-random function. I.e., the input of the function is a bit string of arbitrary length and the output is a pseudo-random bit string of fixed length (instead of a pseudo-random element in ). For every input the function we implement is defined by:
where are two hash functions (defined below) and . In words, the computation of f is as follows: First apply on the input to get . Then compute two pseudo-random elements and in . Finally concatenate these elements and hash the outcome by the second hash function h.
The first step in the computation of f is hashing the input to receive an element s.t. and are in the domain of the pseudo-random function . In order for to be pseudo-random it is enough to require that for any two different inputs the probability of collision, , is negligible. To get this we define as follows:
where R is a 161-bit prime, r (the key of ) is a uniformly distributed element in and the input m is partitioned into a sequence, , of elements in . With this definition the collision probability on any two inputs of length at most 160k is bounded by . The probability of collision for some pair of inputs among arbitrarily chosen inputs is bounded by . For practical values of and k this probability is sufficiently small.
As mentioned above, on input our core function will output a pseudo-random element in the subgroup . Converting this element into a pseudo-random value in is done using a second hash function . The requirement from h is that for any pair of different inputs x,y the collision probability is (or ``extremely close'' to this value). Therefore, we cannot define in the same way we defined . Rather than that we use the following definition:
where R is a 161-bit prime (as above), (the key of ) is a uniformly distributed sequence of elements in and the input is a sequence of elements in .
With this definition of h we can conclude from  that if X is a random variable uniformly distributed over a set of size , then for all but a fraction of the choices of y the random variable is of statistical distance at most from the uniform distribution over . Therefore, if X is a pseudo-random element in such a set then (for all but a fraction of the choices of y) the random variable is a pseudo-random value in . Note that choosing R extremely close to guarantees to be pseudo-random in . In our case, for any the value is pseudo-random in . Thus if we fix (implying the size of to be ) we can define our pseudo-random function as
However, defining Q of size 400 bits seems to be an overkill (in terms of security) and leads to an inefficient implementation. We therefore use the following optimization: We define Q of size 200 bits and on input we compute the element which is pseudo-random in . Since is of size approximately , we define (by the previous analysis) to be
This suggestion is more efficient than the previous one since the exponent of g in the computation of can be derived from the exponent of g in the computation of using a single modular multiplication.
In our discussion so far we assumed that is a pseudo-random function. As shown by Naor and Reingold, this is true as long as the decisional version of the Diffie-Hellman assumption holds. In the current state of knowledge it seems that choosing P of 1000 bits and Q of 200 bits makes this assumption sufficiently safe.
The specific constants used in our implementation are:
For all computations and primality checks involving large numbers we used the NTL package  by V. Shoup.
In this implementation the key was generated as follows:
In order to define , we need two large primes P,Q s.t. and an element of order Q. This task is achieved in three steps. First we find a prime Q of size , then we find a prime P of size such that for some . The density of primes in the natural numbers allows us to find appropriate Q and quite easily. Finally we fix g to be for some such that (the primality of Q ensures that the order of g is exactly Q). Note that we do not insist that P,Q and g be uniform in their range (since it is not clear that such a requirement is essential for the Diffie-Hellman assumption).
In order to implement f a large amount of random (or pseudo-random) keys are needed. These keys can be generated by a pseudo-random generator which is a slight modification of our construction f. Let where , and Id is the identity function. Following the proof in  it can be proven that is pseudo-random on all inputs but 0. Using we implement the pseudo-random function :
This implementation itself uses a seed of 2880 random bits : 800 for the random key and 2080 for the key y. Denoting for we have, by our above analysis, that each is pseudo-random in . Thus is pseudo-random in . Using as a random source we can derive a new pseudo-random key, , with 5 elements by partitioning into chunks of length . Choosing Q such that is negligible guarantees that the elements received remain pseudo-random in . Our new key now allows us to define
Repeating the above procedure grants us with a new pseudo-random allowing us to define
Using directly, all keys needed for our implementation can be manufactured.
As mentioned, the above process uses a random seed of size 2880, this can be improved by replacing the hash function h with a new hash function that has a smaller random key but still fulfills the requirements regarding h stated in the previous section. Therefore we define :
where is the hash function defined in the previous section and is a uniformly distributed sequence of elements in . Note that for any pair of different inputs x,y the collision probability, , is extremely close to (at most ) and the key of is of size 800 bits. This new hash function was not used originally in the implementation of our pseudo-random function f because it is less efficient that h.
All in all the above construction with enables us to generate all random keys for the implementation of f using a random seed of 1600 bits.
In order to compute for |x| = n we need at most n multiplications modulo Q and one exponentiation modulo P.
Computing the value of for as preprocessing improves our efficiency by turning the single modular exponentiation into modular multiplications.
Additional preprocessing can improve the efficiency even further, for example computing the values of for all will turn the single modular exponentiation into modular multiplications, and computing the values of for will turn the n modular multiplications into modular multiplications. For more details see .
In our implementation we preprocessed by computing for all , . The reason for this specific choice is that, for technical reasons, our implementation performs part of its preprocessing on each run (and therefore there was no point in a more extensive preprocessing). In general, the more preprocessing done the faster the implementation will be.
The computation of f consists of two computations of (that are not entirely independent) and two hash executions. All in all computing f with our constants takes about 0.5 seconds. As mentioned above, for technical reasons our implementation performs part of the preprocessing on each run, making our running time about one second per execution.
The construction we implemented is as secure as the decisional version of the Diffie-Hellman  assumption. For this to be true we need the keys to be random and secret. In our implementation we used pseudo-random keys that are as secure as the main construction (of f). Regarding the secrecy of the keys, since we lack the means for secret-'bulletproof' storage it might be feasible to access the keys.
An Implementation of Efficient Pseudo-Random Functions
This document was generated using the LaTeX2HTML translator Version 95.1 (Fri Jan 20 1995) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 pr.tex.
The translation was initiated by Langberg Michael on Tue Mar 31 16:55:04 IDT 1998