3
$\begingroup$

Suppose that we have a secure PRG $$G:\{0,1\}^{n} \rightarrow \{0,1\}^{l(n)}$$

I want to construct a secure PRG $G'$ that when we select its seed $s \in \lbrace 0,1 \rbrace^n$ that $parity(s)=0$, it becomes insecure.

I construct this: $$G'(s||\operatorname{parity}(s)) = G(s)||\operatorname{parity}(s)$$

(where $\operatorname{parity}(s)$ is defined as XOR of all bits of $s$)

Intuitively, I think this is correct. Am I wrong? I couldn't prove it.


$\endgroup$
  • $\begingroup$ What is $\;\;\; G\hspace{.03 in}'\:(\:s\:||\:1\hspace{-0.06 in}-\hspace{-0.04 in}\operatorname{parity}(s)\:) \;\;\;$? $\;\;\;\;\;\;\;\;$ $\endgroup$ – user991 Apr 6 '17 at 21:47
  • $\begingroup$ You mean "what about"?@RickyDemer $\endgroup$ – ThisIsMe Apr 7 '17 at 7:15
  • $\begingroup$ I don't mean what you said. ​ ​ $\endgroup$ – user991 Apr 7 '17 at 7:16
  • $\begingroup$ So, I don't understand your question.@RickyDemer $\endgroup$ – ThisIsMe Apr 7 '17 at 10:34
  • $\begingroup$ You gave the values for G' when the input's last bit is the parity of the rest of the input. ​ What are the values of G' when the input's last bit is not the parity of the rest of the input? ​ ​ ​ ​ $\endgroup$ – user991 Apr 7 '17 at 10:46
1
$\begingroup$

Parity alone is a hard-core predicate of a oneway function, with this example given in the wiki:

With $f$ a oneway function, define $g(x,r) = (f(x),r)$ with $|x|=|r|$. Clearly $g$ is oneway, too, and it's trivial to build an adversary for $f$ from an adversary for $g$ and vice versa. However, $g$ has a hard-core predicate:

$$b(x,r) := <x,r> = \bigoplus_j x_j r_j$$

If we fix $r$ as the all-$1$ input, we get exactly the parity function.

In a similar context in this question the answer of Thomas Pornin has an example where the parity of the input to a oneway trapdoor function is is used as a hardcore predicate.

Now, the difference here is that you have a PRG, with a different definition than oneway functions, but my intuition would be that this is actually a secure PRG (regardless of the input parity) - since one of the standard way to construct a PRG is based on using hardcore predicates. And in the input domain you just fix one bit of the input by calculating the last bit as parity of the others, that should not break the PRG definition.


Edit, here's a sketch for the security proof:

Let's assume you have a distinguisher for $G'$, and we want to build a distinguisher for $G$. We get a challenge $x$ of length $l(n)$, which is either $G(s)$ or a randomly chosen number (from the uniform distribution). Now, we run the distinguisher for $G'$ on the $x|1$ and on $x|0$. Running a poly time algorithm twice is still a poly time algorithm. Loosely speaking, a distinguisher guesses, whether a challenge is in the image of the PRG or not and then returns this guess - but of course any value in the image could also have been the randomly chosen number.

So if at least one of our distinguishers returns "this was generated by the PRG", then we also answer this - if $x|0$ is in the range of the function $G'$, then $x|1$ could be in the range as well or it might not be. For an actual proof you would want to estimate the actual advantages.

| improve this answer | |
$\endgroup$

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.