Pop Quiz #2

If pseudorandom generators exist, then one-way function exist.

If there is a pseudorandom generator with expansion by one bit, there is a pseudorandom generator with expansion by polynomially many bits.

One-Time-Pad encryption is a private-key encryption scheme.

Salsa20 is a pseudorandom generator.

Two infinite sequences of random variables X_n, Y_n are indistinguishable for polynomial time sampling, if there is an algorithm D and two polynomials p and m such that for all sufficiently large n's, we have (see above)

If two sequences of random variables are indistinguishable in poly-time, they are not necessarily indistinguishable by polynomial sampling.

A pseudorandom generator is a deterministic polynomial-time algorithm G satisfying

(1) |G(s)|=l(|s|) for all s ∈ {0,1}* and l(n) > n for all n and

(2) the sequences G(U_1),G(U_2),... and U_{l(1)}, U_{l(1)}, ...are indistinguishable in polynomial time.

(U_n represents a random variable with n uniformly random, independent bits.)

If G is a pseudorandom generator with expansion factor l(n) = 2n, then the function

f : {0,1}* -> {0,1}*, f(x,y) = G(x) for every |x|=|y| is a strongly one-way function.

If an infinite sequence of random variables is unpredictable in polynomial time, then it is pseudorandom.

If an infinite sequence of random variables is not unpredictable in polynomial time, then it is not pseudorandom.

If f : {0,1}^n -> {0,1}^n is a one-way function, then for any fixed s ∈ {0,1}^n,

G(x) = <f(x),s>

is a pseudorandom generator.

If one-way function exist, pseudorandom generators exist.

A single-message private-key encryption scheme (G, E, D) is secure, if and only if

Pr[D(d,E(e,α)) = α] = 1

where α is any plaintext and G(1^n) = (e,d).

An encryption scheme is multi-message secure if and only if it is single-message secure.

For encryption schemes, we have that the "indistinguishable ciphertexts" and "semantic" security notions are equivalent if we are in the private-key settings.