Pseudorandom Generator - Pseudorandom Generators in Cryptography

Pseudorandom Generators in Cryptography

In cryptography, the class F usually consists of all circuit families of size polynomial in the input with a single bit output, and one is interested in designing pseudorandom generators that are computable by a polynomial-time algorithm and whose bias is negligible in the circuit size. These pseudorandom generators are sometimes called cryptographically secure pseudorandom generators (CSPRGs).

It is not known if cryptographic pseudorandom generators exist. Their existence would imply that P ≠ NP. However, the existence of cryptographic pseudorandom generators is widely believed to be true and their existence is necessary for many applications in cryptography.

The existence of cryptographic pseudorandom generators is equivalent to the existence of one-way functions (see Pseudorandom generator theorem).