PRF and deterministic polytime function implie PRG 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&lt;= m &lt;= 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:

(Expansion:) For every $n$ it holds that $\ell(n) &gt; n$.
(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...

Expansion holds because $l(r) &gt; 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.
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.
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!
For your points:

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

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?)

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 &quot;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&quot;. This is the &quot;general template&quot; of proofs by reduction within cryptography, so you would do well to internalize this &quot;strategy&quot;.