|
#REDIRECT [[Stochastic process]]
<!---- Previous article before merging with article [[Stochastic process]]
{{for|creating random numbers|Random number generation}}
{{refimprove|date=February 2012}}
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 process]]es, 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]].<ref>{{cite book
| title = Bayesian Nonparametrics
| isbn = 0-521-51346-4
| publisher = Cambridge University Press
| authorlink1 =Nils Lid Hjort|first1=Nils Lid |last1=Hjort| first2= Chris|last2= Holmes|first3= Peter |last3= Müller|first4= Stephen G.|last4= Walker
| year = 2010 }}</ref>
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 protocol]]s.
==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 of a function|___domain]] to the [[codomain]].{{Clarify|date=June 2011}} For example the class may be restricted to all [[continuous function]]s or to all [[step function]]s. 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.{{clarify|date=February 2012}} Viewed this way it is an idealization of a [[cryptographic hash function]].
A random function is a useful building block in enabling [[cryptographic protocol]]s. 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).<ref>{{cite book|last1=(ed.)|first1=Mihir Bellare|title=Advances in cryptology-CRYPTO 2000 : 20th annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2000 : proceedings|date=2000|publisher=Springer|___location=New York|isbn=978-3-540-67907-3|page=112-130|edition=[Elektronische Ressource]}}</ref> 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==
{{reflist}}
==External links==
* {{springer|title=Random function|id=p/r077330}}
[[Category:Theory of cryptography]]
[[Category:Stochastic processes]]
{{crypto-stub}}
{{probability-stub}}
--->
| 