0
$\begingroup$

I just learnt the definition of hardcore bit, and I have no intuition about this. I want to know what are the possible approaches to this problem.

$\endgroup$
1
  • $\begingroup$ Hint: For any fixed output, some input bits must be hard to predict. But each bit can be easy to predict on average over random inputs. $\endgroup$
    – Maeher
    Mar 24 at 22:50

1 Answer 1

1
$\begingroup$

I get a good idea form my classmate.

Suppose that $f:\{0,1\}^n\to\{0,1\}^m$ is a one-way function.

We construct another one-way function $F:\{0,1\}^{n+1+\log(n+1)}\to\{0,1\}^{m+\log(n+1)+1}$ : For an input $x=x_0x_1\cdots x_{n-1}x_n||s$, where $s\in\{0,1,2,\cdots,n\}$ is a $\log(n+1)$-bit string, we have $$ F(x)=f(x_0x_1\cdots x_{s-1}x_{s+1}\cdots x_n)||s||x_s $$ Then we can prove that $F$ is a a one-way function with none of its input bit is a hardcore bit.

$\endgroup$

Your Answer

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

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