Pseudorandom function
Encyclopedia
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 primitive
s, 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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle
Random oracle
In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
in the following way: no efficient algorithm can distinguish (with significant advantage
Advantage (cryptography)
In cryptography, an adversary's advantage is a measure of how successfully it can attack a cryptographic algorithm, by distinguishing it from an idealized version of that type of algorithm. Note that in this context, the "adversary" is itself an algorithm and not a person...
) 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 primitive
Cryptographic primitive
Cryptographic primitives are well-established, low-level cryptographic algorithms that are frequently used to build computer security systems. These routines include, but are not limited to, one-way hash functions and encryption functions.- Rationale :...
s, especially secure encryption schemes
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
.
Pseudorandom functions are not to be confused with pseudorandom generators
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
(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
Shafi Goldwasser
Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:...
, and Micali.