Crypto-IT

Pseudorandom Functions and Permutations

Pseudorandom functions are efficient and deterministic functions which return pseudorandom output indistinguishable from random sequences. They are made based on pseudorandom generators but contrary to them, in addition to the internal state, they can accept any input data. The input may be arbitrary but the output must always look completely random.

A pseudorandom function, which output is indistinguishable from random sequences, is called a secure one.

Definition The pseudorandom function (PRF) defined over (K, X, Y) is an efficient and deterministic function which returns a pseudorandom output sequence:
F: K x X -> Y

Pseudorandom permutations can be defined in a similar way. They create output data indistinguishable from random sequences.

Definition The pseudorandom permutation (PRP) defined over (K, X) is an efficient and deterministic function which returns a pseudorandom output sequence:
E: K x X -> X

the function E (k, .) in one-to-one
there exists an efficient inversion algorithm D (k, x)

Pseudorandom permutations which produce output sequences that are indistinguishable from random sequences, are called secure PRPs. It can be proved that secure PRP defined over large enough X is also a secure PRF (according to the PRF Switching Lemma).

Creating PRF from PRG

Let G be a secure pseudorandom generator. Having G, it is possible to create a secure pseudorandom function F.

1-bit pseudorandom function

Let G returns two times more bits than it has bits in its internal state:
G: K -> K²

It is possible to define a 1-bit pseudorandom function:
    F: K x {0, 1} -> K
as:
    F(k, b) = G(k)[b]
where:
    b can be equal to either 0 or 1.

The function F returns the first or the second half of generator's output data, based on the received input bit.

If the generator G is secure, then the function F is also secure.

2-bit pseudorandom function

Having the generator G, one can expand it and define a new generator G₁:
G₁: K -> K⁴
as:
G₁(k) = G(G(k)[0]) || G(G(k)[1])

Analogously, it is possible to define an expanded pseudorandom function F₁, which takes 2 bits as its input:
    F₁: K x {0, 1}² -> K
as:
    F₁(k, c) = G₁(k)[c]
where:
    c is any two bits.

N-bit pseudorandom function

The presented procedure can be repeated any number of times and one can receive a pseudorandom function which could be of any size. This method of creating pseudorandom functions is known as Goldreich-Goldwasser-Micali Construction, based on the names of people who invented it.

It can be proved that if the generator G is secure, then a pseudorandom function working on input data of length of n bits and defined in a way described above is also secure.

Date: 2020-03-09