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?

  • 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$
    – Maeher
    Sep 14 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$
    – Zoey
    Sep 14 at 16:46
  • $\begingroup$ Remember that GL define a specific OWF, for which the inner product is hard-core. $\endgroup$
    – Maeher
    Sep 14 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$
    – Maeher
    Sep 15 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$
    – Zoey
    Sep 16 at 5:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.