0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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".

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you a lot for your answer. I think that 2. $F_C$ is upper bounded by a polynomial expression in the size of its input because $m$ can be at most $p(r)$. Moreover, we're assuming $F$ is a pseudorandom function so it's efficient and this means there's a polynomial-time algorithm that computes $F$. Since $F_C$ is the concatenation of at most $p(r)$ output computed by a polytime algorithm, $F$ is polytime. (I found the PRF definition as you said and it helped me) $\endgroup$ – Justin Oct 20 at 9:01
  • $\begingroup$ 3. Let's suppose $F_C$ is not a PRG, so there will be a distinguisher such that its probability to distinguish between a random input $r$ and a $F_C$ 's output is greater than a negligible function. Since $F_C$ is defined as the concatenation of $F$ 's output, there will be a distinguisher for $F$ as well. Nevertheless, we supposed $F$ to be pseudorandom so there's no distinguisher for $F$ and this means there's no distinguisher for $F_C$ as well. Is this a correct answer? $\endgroup$ – Justin Oct 20 at 9:09
  • $\begingroup$ A better way? Let's suppose $F_C$ is not a PRG, so there will be a distinguisher such that its probability to distinguish between a random input $r$ and a $F_C$ 's output is greater than a negligible function $negl(n)$. Since $F_C$ depends on $F$, there will be a distinguisher with probability $ > negl(n)$ for $F$ as well. Nevertheless, we supposed $F$ to be pseudorandom so all distinguisher for $F$ will have probability $<= negl(n)$ and this means there's no distinguisher for $F_C$ with a probability $> negl(n)$. So $F_C$ is a PRG. Is this a correct answer? $\endgroup$ – Justin Oct 20 at 9:17
  • $\begingroup$ @Justin it is close to correct --- I cannot say more without knowing the standard of rigor your professor expects. The "standard" way to show the pseudorandomness of $F_C$ is something called a "hybrid argument". If this rings a bell, you should make that form of argument here. If not, it is possible the professor expects something like what you are saying. The benefit of the hybrid argument though is that it allows you to get "explicit" bounds on the distinguishing advantage of an adversary for $F_C$ in terms of the distinguishing advantage of an adversary for $F$, rather just heuristically.. $\endgroup$ – Mark Oct 20 at 16:00
  • 1
    $\begingroup$ I read something about "hybrid argument" on the internet on my own, but my professor didn't explain it at the moment (maybe he'll do it later). Thank you a lot for your answers! $\endgroup$ – Justin Oct 20 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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