Pseudorandom function family

In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish (with significant advantage) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are fixed completely at random). Pseudorandom functions are vital tools in the construction of cryptographic primitives, especially secure encryption schemes.

Pseudorandom functions are not to be confused with pseudorandom generators (PRGs). The guarantee of a PRG is that a single output appears random if the input was chosen at random. On the other hand, the guarantee of a PRF is that all its outputs appear random, regardless of how the corresponding inputs were chosen, as long as the function was drawn at random from the PRF family.

A pseudorandom function family can be constructed from any pseudorandom generator, using, for example, the construction given by Goldreich, Goldwasser, and Micali.[1]

Random functions

A PRF is an efficient (i.e. computable in polynomial time) deterministic function that maps two distinct sets (domain and range).

Essentially a true random function would just be composed of a look-up table filled with random entries. However, in practice a PRF has only one input d (domain) and a hidden random seed (range) which when run multiple times with the same input, always outputs the same value. Nonetheless, given an arbitrary input the output looks random due to the random seed.

A PRF is considered to be good if its behavior is indistinguishable from a true random function. Therefore, given a true random function and a PRF, there should be no efficient method of determining if the output was produced by a true random function or the PRF.

Applications [2]

  1. Dynamic Hashing: even if the adversary can change the key-distribution depending on the values the hashing function has assigned to the previous keys, still he can not force collisions.
  2. Constructing deterministic, memoryless authentication schemes which are provably secure against chosen message attack.
  3. Distributing unforgable ID numbers which can be locally verified by stations which contain only a small amount of storage.
  4. Constructing Identity Friend or Foe systems.

See also

References

  1. ↑ Oded Goldreich, Shafi Goldwasser, Silvio Micali (1986) "How to Construct Random Functions", Journal of the ACM, vol.33, no.4, p.792-807. doi:10.1145/6490.6503; preprint; web page and preprint
  2. ↑ Goldreich, O.; Goldwasser, S.; Micali, S. (1985). "On the Cryptographic Applications of Random Functions (Extended Abstract)". Advances in Cryptology. Lecture Notes in Computer Science 196. p. 276. doi:10.1007/3-540-39568-7_22. ISBN 978-3-540-15658-1.