It is well known that weak OWF implies strong OWF by concatenating several evaluations of weak OWF (see e.g. here), where weak OWF is defined as

$ \exists $ poly $Q$, $\forall$ PPT $\mathcal A$ such that:

$$Pr[x←\{0,1\}^n; \mathcal A(1^n,f(x))=x′ s.t. f(x′)=f(x)]≤1−1/Q(n).$$

I want to establish a similar argument for a hardcore bit:

Let $f : \{0,1\}^n \rightarrow \{0,1\}^m$ be an (injective) function and $B : \{0,1\}^n \rightarrow \{0,1\}$ be a weak hardcore predicate of $f.$ Define a concatenate function $F: \{0,1\}^{t\cdot n} \rightarrow \{0,1\}^{t\cdot m}$ defined by $$ F(x_1, \cdots,x_t) = (f( x_1) || \cdots || f(x_t)). $$ Then for sufficiently large $t,$ for any PPT $\mathcal B,$ $$ \Pr[x_i \leftarrow \{0,1\}^n; \mathcal B(1^{t\cdot n}, (F(x_1, \cdots, x_t)) = (B(x_1), \cdots, B( x_t))] = negl(n).$$

So far, I defined weak hardcore predicate in a similar way to OWF, and trying to adapt the proof for OWF to this case, but it gives many obstacles so far.

Is there anyone who know some results for this? I've failed to find those kind of argument, so any help, even some counterexamples, will be appreciated.

(*) In my goal, the vector $(B(\vec x_1), \cdots, B(\vec x_t))$ does not need to be indistinguishable from uniform, whose concept seems to be called by simultaneous hardcore bits.


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.