Pseudo-random function

A pseudorandom function is a family of efficiently computable functions that are practically indistinguishable from a random oracle . Each block cipher can formally be understood as a pseudo-random function that is parameterized by cryptographic keys .

A family of functions is a mapping between non-empty, finite sets K, X, Y. For each key is therefore given by a mapping . The maximum number of all possible mappings from to is also the upper bound for the maximum number of keys (i.e. ). ${\displaystyle F\colon K\times X\to Y}$ ${\displaystyle k\in K}$ ${\displaystyle F_{k}(x)=F(k,x)}$ ${\displaystyle F_{k}\colon X\to Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle |K|}$

A random oracle is an algorithm that returns a ( uniformly distributed ) randomly drawn output from Y for every input from X , with the restriction that a function value that has been determined once is fixed, i.e. the same answer is given for the same query. Such a function family F is called pseudorandom if every efficient algorithm, for a (uniformly distributed) randomly drawn and unknown k, can distinguish between and a random oracle only negligibly (in k) better than by guessing. ${\displaystyle F_{k}}$

A pseudo-random function can be constructed from a cryptographically secure random number generator using the method of Goldreich, Goldwasser and Micali.

Individual evidence

1. ^ ^{A b} Mihir Bellare and Phillip Rogaway: Introduction to Modern Cryptography . Chapter 3: Pseudorandom functions ( ucsd.edu ).
2. ↑ Oded Goldreich , Shafi Goldwasser , Silvio Micali : How to Construct Random Functions . In: Journal of the ACM . tape  33 , no. 4 , 1986, pp. 792-807 , doi : 10.1145 / 6490.6503 ( weizmann.ac.il ). How to Construct Random Functions ( Memento of the original from September 26, 2007 in the Internet Archive ) Info: The archive link was automatically inserted and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.