Please help with this question.
2
-
$\begingroup$ Please follow the guidelines of questions and add a descriptive label of the question. Moreover, please write the question (TeX syntax is available here), don't copy it as an image. It greatly helps people looking it up later. $\endgroup$– zajicCommented Sep 23, 2019 at 6:05
-
$\begingroup$ Welcome to Cryptography. is this homework? $\endgroup$– kelalakaCommented Sep 23, 2019 at 6:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Short answer: no.
Long answer: pseudorandom generators must be indistinguishable from uniform distributions (up to a bias $\epsilon$). Your $G'$ is constructed as an output of a pseudorandom generator ($G$) and a supplement $(s_1 \land s_2)$ that depends on two seed bits. Clearly, the $G$-part is okay; what determines the pseudorandomness of $G'$ is its last bit.
Let's create a distinguisher $A\in\mathcal A$ such that it
- outputs $0$ if the last bit of a $(n+1)$-bit sequence is $1$ (thinks it's a random distribution),
- outputs $1$ else (thinks it's $G'$).
Now evaluate the success rate of $A$ against uniform distribution over $(n+1)$ bits and your $G'$:
- Uniform distribution over $n+1$ bits has uniform distribution of the last bit as well, which means $A$ will have a uniform output, too.
- $(s_1\land s_2)=1\;\Leftrightarrow\;(s_1=1)\,\land\,(s_2=1)$, which happens (with uniformly-distributed input) in about $25\,\%$ of cases.
And that's pretty much it. Per definition, the statistical distance of $A(U_{n+1})$ and $A(G'(U_n))$ is non-negligible, it's $25\,\%$ indeed. $G'$ cannot be a pseudorandom generator.
