Pseudorandom function family

Pseudorandom function family

In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: No efficient algorithm can distinguish (with significant advantage) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are fixed completely at random). Pseudorandom functions are vital tools in the construction of cryptographic primitives, especially secure encryption schemes.

Pseudorandom functions are not to be confused with pseudorandom generators (PRGs). The guarantee of a PRG is that a "single" output appears random if the input was chosen at random. On the other hand, the guarantee of a PRF is that "all its outputs" appear random, regardless of how the corresponding inputs were chosen, as long as the "function" was drawn at random from the PRF family.

A pseudorandom function family can be constructed from any pseudorandom generator, using, for example, the construction given by Goldreich, Goldwasser, and Micali. [Oded Goldreich, Shafi Goldwasser, Silvio Micali (1986) "How to Construct Random Functions", "Journal of the ACM", vol.33, no.4, p.792-807. doi|10.1145/6490.6503; [ preprint] ; [ web page and preprint] ]

ee also

*Pseudorandom permutation


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Pseudorandom generator — In theoretical computer science, a pseudorandom generator is a deterministic method of generating a large amount of pseudorandom, or apparently random, data, from a small amount of initial random data. The initial data is commonly known as a… …   Wikipedia

  • Pseudorandom permutation — In cryptography, a pseudorandom permutation, abbreviated PRP, is an idealized block cipher. It means the cipher that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the… …   Wikipedia

  • Pseudorandom generator theorem — In computational complexity a distribution is considered pseudorandom if no efficient computation can distinguish it from the true uniform distribution by a non negligible advantage. Formally, a family of distributions Dn is pseudorandom if for… …   Wikipedia

  • Cryptographic hash function — A cryptographic hash function (specifically, SHA 1) at work. Note that even small changes in the source input (here in the word over ) drastically change the resulting output, by the so called avalanche effect. A cryptographic hash function is a… …   Wikipedia

  • SEAL (cipher) — In cryptography, SEAL (Software Optimized Encryption Algorithm) is a very fast stream cipher optimised for machines with a 32 bit word size and plenty of RAM. SEAL is actually a pseudorandom function family in that it can easily generate… …   Wikipedia

  • Salsa20 — The Salsa quarter round function. Four parallel copies make a round. General Related to Rumba20, ChaCha Certification eSTREAM portfolio …   Wikipedia

  • Naor — (Hebrew: נאור‎‎) is a Hebrew name: Given name Naor Gilon Naor Peser (Hebrew: נאור פסר‎‎; born 1985), an Israeli footballer Naor Zion …   Wikipedia

  • CBC-MAC — В криптографии, CBC MAC является технологией построения аутенфикационного кода сообщения из блочного шифра. Сообщение шифруется при помощи некоторого блочного алгоритма шифрования в режиме CBC, для создания цепочки блоков с правилом  каждый… …   Википедия

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Hardware random number generator — This SSL Accelerator computer card uses a hardware random number generator to generate cryptographic keys to encrypt data sent over computer networks. In computing, a hardware random number generator is an apparatus that generates random numbers… …   Wikipedia