Random function

Random function

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 image set. 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.

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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • random function — atsitiktinė funkcija statusas T sritis automatika atitikmenys: angl. random function vok. Zufallsfunktion, f rus. случайная функция, f pranc. fonction aléatoire, f …   Automatikos terminų žodynas

  • random function — noun a) A function whose value is chosen at random from its domain b) A function chosen at random from a set of functions …   Wiktionary

  • Verifiable random function — In cryptography, the concept of a verifiable random function was introduced by Micali, Rabin, and Vadhan. [cite conference | first = Silvio | last = Micali | coauthors = Rabin, Michael O.; Vadhan, Salil P. | title = Verifiable random functions |… …   Wikipedia

  • Random variable — A random variable is a rigorously defined mathematical entity used mainly to describe chance and probability in a mathematical way. The structure of random variables was developed and formalized to simplify the analysis of games of chance,… …   Wikipedia

  • Random element — The term random element was introduced by Maurice Frechet in 1948 to refer to a random variable that takes values in spaces more general than had previously been widely considered. Frechet commented that the development of probability theory and… …   Wikipedia

  • Random phase approximation — (RPA) is one of the most often used methods for describing the dynamic electronic response of systems. In RPA, electrons are assumed to respond only to the total electric potential V (r) which is the sum of the external perturbing potential V… …   Wikipedia

  • Random self-reducibility — (RSR): A good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances.DefinitionIf a function f evaluating any instance x can… …   Wikipedia

  • Random permutation statistics — The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example,… …   Wikipedia

  • Random password generator — A random password generator is software program or hardware device that takes input from a random or pseudo random number generator and automatically generates a password. Random passwords can be generated manually, using simple sources of… …   Wikipedia

  • Random oracle — In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every query with a (truly) random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”