# Suppose there exists a one-way function, show that there exists a one-way function with none of its input bit is a hardcore bit

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.

• 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. Mar 24 at 22:50

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.