Skip to main content
Tweeted twitter.com/#!/StackCrypto/status/273049169776746496
added 32 characters in body
Source Link
D.W.
  • 36.7k
  • 13
  • 105
  • 193

Given $G:\{0,1\}^s \rightarrow \{0, 1\}^n$ a secure PRG, how can one prove that $G'(k_1, k_2) = G(k_1) \cdot G(k_2)$ is secure ($\cdot$ means concatenation).?

So if it's true we canIn other words, I'd like to show that if there is a distinguisher for $G'$ then this implies that there exists a distinguisher for $G$. So

For example, could this distinguisher be:

$A(x) = round(\sum_{y \in \{0^n,\dots,1^n\}} A(y \cdot x) / n)$ as follows?

??$A(x) = \text{round}(\frac{1}{2^n} \sum_{y \in \{0,1\}^n} A(y \cdot x))$

Given $G:\{0,1\}^s \rightarrow \{0, 1\}^n$ a secure PRG, how can one prove that $G'(k_1, k_2) = G(k_1) \cdot G(k_2)$ is secure ($\cdot$ means concatenation).

So if it's true we can show that if there is a distinguisher for $G'$ then this implies that there exists a distinguisher for $G$. So could this distinguisher be:

$A(x) = round(\sum_{y \in \{0^n,\dots,1^n\}} A(y \cdot x) / n)$

??

Given $G:\{0,1\}^s \rightarrow \{0, 1\}^n$ a secure PRG, how can one prove that $G'(k_1, k_2) = G(k_1) \cdot G(k_2)$ is secure ($\cdot$ means concatenation)?

In other words, I'd like to show that if there is a distinguisher for $G'$ then this implies that there exists a distinguisher for $G$.

For example, could this distinguisher be as follows?

$A(x) = \text{round}(\frac{1}{2^n} \sum_{y \in \{0,1\}^n} A(y \cdot x))$

Source Link
Jordi
  • 131
  • 1
  • 3

How to prove that the concatenation of two secure PRG is secure?

Given $G:\{0,1\}^s \rightarrow \{0, 1\}^n$ a secure PRG, how can one prove that $G'(k_1, k_2) = G(k_1) \cdot G(k_2)$ is secure ($\cdot$ means concatenation).

So if it's true we can show that if there is a distinguisher for $G'$ then this implies that there exists a distinguisher for $G$. So could this distinguisher be:

$A(x) = round(\sum_{y \in \{0^n,\dots,1^n\}} A(y \cdot x) / n)$

??