Random function
Encyclopedia
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 to the codomain
Codomain
In mathematics, the codomain or target set of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation...

. 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
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...

. A special case of a random function is a random permutation
Random permutation
A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and simulation...

.

A random function is a useful building block in enabling cryptographic protocol
Cryptographic protocol
A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...

s. However, there are scenarios where it is not possible for mutually distrustful parties to agree on a random function (i.e., coin flipping
Coin flipping
Coin flipping or coin tossing or heads or tails is the practice of throwing a coin in the air to choose between two alternatives, sometimes to resolve a dispute between two parties...

 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
Common reference string model
In cryptography, the common reference string model captures the assumption that a trusted setup in which all involved parties get access to the same string crs taken from some distribution D exists. Schemes proven secure in the CRS model are secure given that the setup was performed correctly...

.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK