Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Let $G: \ K \rightarrow \{0,1\}^n$ be a secure PRG. Define $G'(k_1,k_2)=G(k_1)\wedge G(k_2)$ where $\wedge$ is the bit-wise AND function. Consider the following statistical test $A$ on $\{0,1\}^n$: $A(x)$ outputs $LSB(x)$, the least significant bit of $x$. What is $Adv_{PRG}[A,G']$? You may assume that $LSB(G(k))$ is $0$ for exactly half the seeds $k$ in $K$.

I have no idea how to solve this kind of assigments. $Adv_{PRG}[A,G'] = \left|Pr_{k,j\leftarrow H}[A(G'(k,j))=1] - Pr_{r\leftarrow \{0,1\}^n}[A(r)=1] \right|$

$Pr_{r\leftarrow \{0,1\}^n}[A(r)=1]=\frac{1}{2}$

$Pr_{k,j\leftarrow H}[A(G'(k,j))=1]=Pr_{k,j\leftarrow H}[A(G(k)\wedge G(j))=1]=Pr_{k,j\leftarrow H}[A(G(k))=1 \ \vee \ A(G(j))=1]=2Pr_{k\leftarrow H}[A(G(k))=1] - Pr_{k,j\leftarrow H}[A(G(k))=1 \ \wedge \ A(G(j))=1]=...$

And now I stucked...

Is this $...=2\cdot \frac{1}{2} - \frac{1}{4}=\frac{3}{4}$ ? Then, $Adv_{PRG}[A,G']=|\frac{3}{4}-\frac{1}{2}|=\frac{1}{4}$

share|improve this question
What have you tried? Where are you stuck? This isn't a question answering service. –  mikeazo Jun 29 at 16:48
Hint: what's the definition of Advantage? –  poncho Jun 29 at 17:49
@mikeazo please check my post again :) –  nopenope Jun 29 at 17:56
It looks like you answered your own question... –  poncho Jun 29 at 18:03
Ok, I needed to confirm my solution. Thanks, It wasn't hard;) –  nopenope Jun 29 at 18:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.