PRF and deterministic polytime function implie PRG

Question

I'm struggling while trying to resolve this exercise. I already read all questions about PRG and PRF here and some proofs around the internet but none of them helped me.

let's consider a function $C$ as follow: there exists a polynomial $p$ for every $n$ in natural numbers, $C(1^n)$ is a sequence $\langle s_1,...s_m\rangle $ such that:

• $2<= m <= p(n)$
• for every $i \in \{1,...,m\} , s_i \in \{0,1\}^n$
• $s_i = s_j $ implies $i = j$

Let's consider a length preserving partial function $F: \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^*$ and let's define $F_C$ as a function on binary strings such that $F_C(r) = F(r,s_1) || ... || F(r,s_m)$ where $C(1^{|r|}) = \langle s_1,...s_m\rangle$ and || is string concatenation. Prove that if $F$ is pseudorandom and $C$ is deterministic and polytime $\rightarrow F_C$ is a pseudorandom generator.

Studying from Introduction to modern cryptography, I'm trying to prove that $F_C$ is a PRG following this definition:

Definition 3.14: Let $\ell$ be a polynomial and let $G$ be a deterministic polynomial-time algorithm such that for any $n$ and any input $s\in\{0,1\}^n$, the result $G(s)$ is a string of length $\ell(n)$. We say that $G$ is a $\mathsf{pseudorandom\ generator}$ if the following conditions hold:

1. (Expansion:) For every $n$ it holds that $\ell(n) > n$.
2. (Pseudorandomness:) For any PPT algorithm $D$, there is a negligible function $\mathsf{negl}$ such that: $$\left|\Pr[D(G(s)) = 1] - \Pr[D(r) = 1]\right| \leq \mathsf{negl}(n)$$ Where the first probability is taken over uniform choice of $s\in\{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r\in\{0,1\}^{\ell(n)}$ and the randomness of $D$

and I understood that...

1. Expansion holds because $l(r) > r$ since, looking at how $C$ is defined and remembering that $F$ is length preserving , we can deduce that $l(r)$ is always at least 2 times $r$'s length because $m$ is at least 2 and each $|s_i| = r$ and they're all distinct.
2. Our assumption says that $F$ is a pseundorandom function and $C$ is deterministic and polytime. Concatenation is also polytime so I think $F_C$ is polytime too because it concatenates $r$ with output from $C$ but I don't know how to wirte down a formal proof about it.
3. I have to prove that there's no PPT algorithm $D$ such that its probability to distinguish between a random input $r$ of lenght $l(n)$ and a $F_C$ 's output of the same lenght is larger than a negligible function but I don't really know how to proceed...I read also some reduction proof but I don't know if is the right way for me because all of them proved that a new defined G is a PRG starting from another PRG.

Please can someone help me with this three points?

Thank you a lot for reading my question!

Answer 1

For your points:

1. Your discussion of expansion is correct. In particular, you can show that $\ell(r) = mr \geq 2r > r$, which is essentially what you explain.

2. You can write a formal proof that $F_C$ is poly-time in essentially the same way you would show any algorithm is poly-time. In this case, it is quite obvious that the result is poly-time, so if it feels obvious to you that this is the case that should be normal. That being said, there are some subtleties --- concatenating two things with polynomially-sized representations is poly-time, but what if you have exponentially many things? This would no longer be poly-time. Can you be sure the algorithm is still poly-time in light of this (and if so, why?)

3. You have a definition of pseudorandomness for PRGs (definition 3.14), which likely want to relate to a definition of pseudorandomness for partial function (in particular $F$). I would suggest finding the particular definition you're working with first. Your proof strategy should be reduction to $F$'s pseudorandomness -- some statement along the lines of "Any distinguisher for $F_C$ implies a distinguisher for $F$, which as $F$ is pseudorandom does not exist, so the distinguisher for $F_C$ cannot exist as well". This is the "general template" of proofs by reduction within cryptography, so you would do well to internalize this "strategy".