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

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

-

I fixed some errors in your question.  My question for you is: is this homework?  If so, you should solve it yourself.  The entire point of homework is to force you to struggle with these problems yourself; that's the only way you will learn it.  You won't learn the material by looking at how other people have solved the problem. – D.W. Nov 14 '12 at 3:39

## 1 Answer

Since this looks like homework, I'm not going to answer the question directly (and I hope others won't either), but I'll just give some hints:

• You're on a good direction. If you want to prove that $G'$ is a secure PRG, then your general approach (trying to show that a distinguisher for $G'$ implies a distinguisher for $G$) is a good strategy. Keep at it.

• Your particular distinguisher $A$ is not an effective distinguisher against $G$. Hint: What is the running time to compute $A(x)$?

• You can probably fix up your distinguisher (to get the runtime down to something reasonable), but that's working harder than you need to. Instead, you might want to read on....

• Have you heard of the notion of a "hybrid argument"? If yes, can you see any way that it might be relevant? If no, go read up on "hybrid arguments"; they are a fundamental and important proof techniques for proving indistinguishability/distinguishability.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 12, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9478504657745361, "perplexity_flag": "middle"}