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 "GGM" construction given by Goldreich, Goldwasser, and Micali.^[1]

Motivations from Random Functions

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

Essentially a truly random function would just be composed of a look-up table filled with uniformly distributed random entries. However, in practice a PRF is given an input string in the domain and a hidden random seed, and runs multiple times with the same input string and seed, always returning the same value. Nonetheless, given an arbitrary input string the output looks random if the seed is taken from a uniform distribution.

A PRF is considered to be good if its behavior is indistinguishable from a truly random function. Therefore, given an output from either the truly random function or a PRF, there should be no efficient method to correctly determine whether the output was produced by the truly random function or the PRF.

Formal Definition

A family of functions,

f_s : {0, 1}^λ(|s|) → {0, 1}^λ(|s|), where s ∈ {0, 1}^*, and λ : ℕ → ℕ,

is pseudorandom if the following conditions are satisfied:

• Given any s and x such that |x| = λ(|s|), there always exists a polynomial-time algorithm to compute f_s(x).
• Let F_n be the distribution of functions f_s where s is uniformly distributed over {0, 1}ⁿ, and let RF_n denote the uniform distribution over the set of all functions from {0, 1}ⁿ to {0, 1}ⁿ. Then we require F_n and RF_n are computationally indistinguishable, where n is the security parameter. That is, for any adversary that can query the oracle of a function sampled from either F_n or RF_n, the advantage that she can tell apart which kind of oracle is given to her is negligible. ^[2]

Oblivious Pseudorandom Functions

In an oblivious pseudorandom function, information is concealed from two parties that are involved in a PRF.^[3] That is, if Alice gives the input for a pseudorandom function to Bob, and Bob computes a PRF and gives the output to Alice, Bob is not able to see either the input or the output, and Alice is not able to see the secret key Bob uses with the pseudorandom function. This enables transactions of sensitive cryptographic information to be secure even between untrusted parties.

Applications ^[4]

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

• Pseudorandom permutation

Notes

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's FoC, vol. 1, def. 3.6.4. Pass's notes, def. 96.2
3. M. Bellare, S. Keelveedhi, and T. Ristenpart, “Dupless: server- aided encryption for deduplicated storage,” in Proceedings of the 22nd USENIX Security Symposium. Washington, DC, USA: USENIX Association, August 2013, pp. 1–16.
4. 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.

References

• Goldreich, Oded (2001), Foundations of cryptography: Basic Tools, Cambridge: Cambridge University Press, ISBN 978-0-511-54689-1
• Pass, Rafael, A Course in Cryptography (PDF), retrieved 22 December 2015