Why consider a random $r$ in building a hardcore predicate in Goldreich Levin theorem? Why not consider just the XOR of all bits of the input?
5
-
2$\begingroup$ Let $f : \{0,1\}^n \to \{0,1\}^n$ be a one-way function. Consider the function $g : \{0,1\}^n \to \{0,1\}^{n+1}$ defined as $g(x) = g(x_1\ldots x_n) := f(x)\Vert \bigoplus_{i=1}^{n} x_i$. Is $g$ one-way? Is the xor of all input bits a hardcore predicate for $g$? $\endgroup$– MaeherCommented Sep 14, 2021 at 14:09
-
$\begingroup$ it isnt since it is part of the output. But then why cant the same be done with <x,r>. If you include that in the output that will be not be hard-core too right? Also isn't XOR the special case when r is all 1s? $\endgroup$– ZoeyCommented Sep 14, 2021 at 16:46
-
$\begingroup$ Remember that GL define a specific OWF, for which the inner product is hard-core. $\endgroup$– MaeherCommented Sep 14, 2021 at 22:02
-
1$\begingroup$ $r$ is part of the input you can't set it to anything, it's chosen uniformly at random. But crucially it's not part of the input of the underlying function, so that function cannot do anything funny. $\endgroup$– MaeherCommented Sep 15, 2021 at 7:59
-
$\begingroup$ Let me try to understand here: XOR of bits is not a hardcore bit for any OWF because we can construct one where XOR is part of the output. XOR can be a hardcore of the underlying function $f$, it happens if $r= 11...1$ (all 1s) is a randomly chosen choice for the input of the GL transformation of $f$, i.e. $g$. $\endgroup$– ZoeyCommented Sep 16, 2021 at 5:01
Add a comment
|