Score:0

XOR of all bits of $f(x)$ a hard-core bit

cn flag

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?

cn flag
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$?
Zoey avatar
cn flag
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?
cn flag
Remember that GL define a *specific* OWF, for which the inner product is hard-core.
cn flag
$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.
Zoey avatar
cn flag
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$.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.