Random function: Difference between revisions

Revision as of 17:02, 28 February 2012

Revision as of 12:11, 29 February 2012

Line 1:

{{for|creating random numbers|Random number generation}}

{{unreferencedrefimprove|date=JuneFebruary 20112012}}

A '''random function''' is a function chosen at random from a finite family of functions. Typically, the family consists of the set of all maps from the [[Domain of a function|___domain]] to the [[codomain]].{{Clarify|date=June 2011}} 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 special case of a random function is a '''[[random permutation]]'''.

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 = 0521513464

| 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 familiy 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]]. 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 deterimined 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).{{cn|date=December 2011}} 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}}

[[Category:Theory of cryptography]]