2
$\begingroup$

I am running into the Goldreich Levin Theorem.

According to what I know a predicate $h: \{ 0,1 \}^* \to \{ 0,1 \} $ is a hardcore predicate for a function $f: \{ 0,1 \}^* \to \{ 0,1 \}^* $ if:

  1. $h$ is deterministic and efficiently computable
  2. It's hard to find $h(x)$ given $f(x)$ for any probabilistic time adversary

The Goldreich Levin Theorem states that a hardcore predicate can be found given any OWF

According to Wikipedia (https://en.wikipedia.org/wiki/Hard-core_predicate) and every other research paper that I found (ie. https://www3.cs.stonybrook.edu/~omkant/S06.pdf) this hardcore predicate is generated as follows:

"Let $f$ be a OWF (OWP). We defined the function $g(x, r) = (f(x), r)$ where, $|x| = |r|$. It is not hard to see that g is also a OWF (OWP). The Goldreich-Levin Theorem proves that $h(x, r) =< x, r >$ is a hard core predicate for $g$."

I don't really understand the $<x, r>$ notation, in Wikipedia I found that <> stands for inner product / XOR. But according to the definition above, a hardcore predicate $h: \{ 0,1 \}^* \to \{ 0,1 \} $ for a function $f: \{ 0,1 \}^* \to \{ 0,1 \}^* $ is supposed to be a decission problem (0/1) whereas in this definition $|h(x)| > 1$, actually it should be $|h(x)| = |x| = |r| = |x \oplus r|$

EDIT

I have found this question in the forum about the notation What Does This Symbol Mean? (Hardcore Predicates for One-Way Functions) but it still doesn't solve my question about the output size of the hardcore predicate

$\endgroup$

1 Answer 1

2
$\begingroup$

I just found out the answer, the notation $<>$ stands indeed for the inner product, which is defined as follows for binary strings:

$h(x, r) = <x, r> = \sum x_{i}r_{i} \mod 2$

Here's an example: $x=1101, r=1101 $

$h(x, r) = <x, r> = \sum x_{i}r_{i}\mod 2 = 1*1+1*1+0*0+1*1 \mod 2 = 3 \mod 2 = 1$

$\endgroup$
1
  • 1
    $\begingroup$ Your answer is correct. You can accept it. $\endgroup$
    – kodlu
    Feb 27, 2023 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.