In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, 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 generator
In theoretical computer science and cryptography, a pseudorandom generator (PRG) for a class of statistical tests is a deterministic procedure that maps a random seed to a longer pseudorandom string such that no statistical test in the class ...
s (PRGs). The guarantee of a PRG is that a ''single'' output appears
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual ra ...
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
Goldwasser ("Gold water from Gdańsk"), pol. Wódka Gdańska, with Goldwasser as the registered tradename, is a strong (40% ABV) root and herbal liqueur which was produced from 1598 to 2009 in Gdańsk. Production now takes place in Germany.
Th ...
, and
Micali. While in practice,
block ciphers are used in most instances where a pseudorandom function is needed, they do not, in general, constitute a pseudorandom function family, as block ciphers such as
AES are defined for only limited numbers of input and key sizes.
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 lookup 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,
, where , and
is pseudorandom if the following conditions are satisfied:
* Given any
and
such that
, there always exists a polynomial-time algorithm to compute
.
* Let
be the distribution of functions
where
is uniformly distributed over
, and let
denote the uniform distribution over the set of all functions from
to
. Then we require
and ''
'' 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
or ''
'', the advantage that she can tell apart which kind of oracle is given to her is negligible.
Oblivious pseudorandom functions
In an oblivious pseudorandom function, abbreviated OPRF, information is concealed from two parties that are involved in a PRF. That is, if Alice cryptographically hashes her secret value,
cryptographically blinds the hash to produce the message she sends to Bob, and Bob mixes in his secret value and gives the result back to Alice, who unblinds it to get the final output, Bob is not able to see either Alice's secret value or the final output, and Alice is not able to see Bob's secret input, but Alice sees the final output which is a PRF of the two inputs -- a PRF of Alice's secret and Bob's secret.
This enables transactions of sensitive cryptographic information to be secure even between untrusted parties.
An OPRF is used in some implementations of
password-authenticated key agreement In cryptography, a password-authenticated key agreement method is an interactive method for two or more parties to establish cryptographic keys based on one or more party's knowledge of a password.
An important property is that an eavesdropper or m ...
.
[
Matthew Green]
"Let’s talk about PAKE"
2018.
An OPRF is used in the Password Monitor functionality in
Microsoft Edge
Microsoft Edge is a proprietary, cross-platform web browser created by Microsoft. It was first released in 2015 as part of Windows 10 and Xbox One and later ported to other platforms as a fork of Google's Chromium open-source project: Android ...
.
Application
PRFs can be used for:
#
dynamic perfect hashing
In computer science, dynamic perfect hashing is a programming technique for resolving collisions in a hash table data structure.Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 3 ...
; even if the adversary can change the key-distribution depending on the values the hashing function has assigned to the previous keys, the adversary can not force collisions.
# Constructing deterministic, memoryless authentication schemes (
message authentication code based) which are provably secure against chosen message attack.
# Distributing unforgable
ID number
For data storage, identification is the capability to find, retrieve, report, change, or delete specific data without ambiguity. This applies especially to information stored in databases. In database normalisation, the process of organizing ...
s, which can be locally verified by stations that contain only a small amount of storage.
# Constructing
identification friend or foe systems.
See also
*
Pseudorandom permutation
Notes
References
*
*
{{Cryptography navbox
Theory of cryptography
Cryptographic primitives
Pseudorandomness