2
$\begingroup$

I want to prove that for every pseudorandom function $F: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ and for every polynomial $p$ such that $p(n) > 1$ for every $n$ it is possible to construct, starting from $F$, a pseudorandom generator $G$ having expansion factor equal to $l(n) = p(n) \cdot n$.

I fixed a PRF $F$ and came up with two constructions for $G$ (where || denotes the concatenation of binary strings), but I am not sure of either:

  1. $G(k) = F_k(0^n) || F_k(F_k(0^n))|| \cdots || F_k(...(F_k(0^n))$.

The idea is to apply $F_k$ to the previous output $p(n)$ times. I'm not sure if this is indeed a PRG, though. I fear that in some cases it could lead to "cyclic" strings, but I am not sure.

  1. $G(k) = F_k(000...000) || F_k(000...001)|| \cdots || F_k(111...111)$

In the second construction all the inputs have length $n$ and the final output has length $n \cdot 2^n$, but for some combination of $n$ and $p$ the output cannot have a length of $p(n)\cdot n$. For instance, if $n = 2$ and $p(n) = n^{100}+1$, then $|G(k)|= 8$ which is less than $2^{100} + 1$.

Could anyone give me a hint to push me in the right direction?

$\endgroup$

2 Answers 2

0
$\begingroup$

A proper construction is one similar to your second one.

Once fixed $l(n)=p(n)\cdot n$ you can construct a PRF $G$ with expansion factor $l(n)$ from a PRF $F:\{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ in the following way:

$G(k) = F_k(1) || F_k(2) || ... || F_k(p(n))$.

You can prove that $G$ is a PRG since if you replace the PRF $F$ with a true random function $f$ and define $G'(k) = f(1) || f(2) || ... || f(p(n))$ an adversary $\mathcal{A}$ that distinguish $G'$ from $G$ can be used to distinguish $F$ from $f$ contradicting the fact that $F$ is a PRF.

$\endgroup$
0
$\begingroup$

Both of your PRG constructions are secure.

  • Your first construction is essentially output feedback mode (OFB). It is the OFB encryption of the all-zeroes plaintext.

  • Similarly, your second construction is essentially a counter mode (CTR) encryption of the all-zeroes plaintext.

Both OFB and CTR modes are CPA-secure. This doesn't exactly guarantee that the PRGs are secure (because the PRGs use these modes with all-zeroes IV), but the proofs of CPA security can be easily adapted to show that both of your PRGs are secure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.