Random function

In probability theory and its applications, such as statistics and cryptography, a random function is a function chosen randomly from a family of possible functions. Each realisation of a random function would result in a different function. Thus the concept of a random function is one example of a random element and hence is a generalization of the simpler idea of a random variable.

In probability and statistics, one important type of random function is studied under the name of stochastic processes, for which there are a variety of models describing systems where an observation is a random function of time or space. However, there are other applications where there is a need to describe the uncertainty with which a function is known and where the state of knowledge about the true function can be expressed by saying that it is an unknown realisation of a random function, for example in the Dirichlet process.^[1]

A special case of a random function is a random permutation, where a realisation can be interpreted as being in the form of a function on the set of integers describing the original location of an item, where the value of the function provides the new (permuted) location of the item that was in a given location.

In cryptography, a random function can be a useful building block in enabling cryptographic protocols.

Definition

A random function is a type of random element in which a single outcome is selected from some family of functions, where the family consists some class of all maps from the domain to the codomain. For example the class may be restricted to all continuous functions or to all step functions. The values determined by a random function evaluated at different points from the same realization would not generally be statistically independent but, depending on the model, values determined at the same or different points from different realisations might well be treated as independent.

Applications

Thus, a random function can be considered to map each input independently at random to any one of the possible outputs. Viewed this way it is an idealization of a cryptographic hash function. A random function is a useful building block in enabling cryptographic protocols. However, there are scenarios where it is not possible for mutually distrustful parties to agree on a random function (i.e., coin flipping is impossible). Therefore, cryptographers study models which explicitly allow for the use of a random function or a related object. See random oracle model, common reference string model.

Notes

1. Hjort, Nils Lid; Holmes, Chris; Müller, Peter; Walker, Stephen G. (2010). Bayesian Nonparametrics. Cambridge University Press. ISBN 0-521-51346-4.

External links

• Hazewinkel, Michiel, ed. (2001), "Random function", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4