Hardcore Bits

Let \(f:\{0,1\}^n\rightarrow\{0,1\}^n\) be \((t,\epsilon)\)-one-way.

First we note that there exists \(1\le i \le n\) such that for all \((t/n)\)-time algorithms \(A\),

(If not, then for all \(i\) there exists an algorithm \(A_i\) with \(\Pr[A_i(f(x))=x_i]\ge1-(1-\epsilon)/n\), which would imply \(\Pr[(\text{for all }i) A_i(f(x))=x|_i] \ge \epsilon\) by the union bound, a contradiction.

Theorem: Suppose \(B:\{0,1\}^n\rightarrow\{0,1\}\) is a predicate such that for all \(t\)-time algorithms \(A\), \(\Pr[A(f(x))=x]\lt 1-\epsilon\). Define \(B_m(x_1,...,x_m)=B(x_1)\oplus ... \oplus B(x_m)\). Then if \(m=\lfloor 1/\epsilon\rfloor\), then for all \((t/m)\)-time \(A_m\), we have

(where \(x_1,...,x_m\leftarrow\{0,1\}^n\)).

This implies that for \(m=\lfloor 1/\epsilon\rfloor\), \(B_m\) is a \((t/m,\epsilon)\)-hardcore bit of \(f(x_1)||...||f(x_m)\).

Given \(x,y \in \{0,1\}^n\), define \(\langle x,y \rangle = \sum_{i=1}^n x_i y_i \bmod 2\).

Let \(f:\{0,1\}^n\rightarrow\{0,1\}^n\) be a \((t,\epsilon/2)\)-one-way permutation. Define \(g:\{0,1\}^{2n}\rightarrow\{0,1\}^{2n}\) by \(g(x,r)=f(X)||r\). Define \(B:\{0,1\}^{2n}\rightarrow\{0,1\}\) by \(B(x,r)=\langle x,r\rangle\).

Theorem: Let \(f\) be a \((t,\epsilon/2)\)-one-way permutation. Then \(B\) is \((t',\epsilon)\)-hardcore for \(g\) where \(t'=t/TIME(GL)\), where GL is the Goldreich-Levin algorithm.

Proof: Suppose \(B\) is not \((t',\epsilon)\) hardcore for \(g\). Then there exists a \(t'\)-time algorithm \(A\) such that

Define the set \(S\subseteq\{0,1\}^n\) by

In other words, all \(x\)'s that the algorithm works with good probability.

By a counting argument, \(|S| \gt (\epsilon/2)2^n\). We shall construct an algorithm \(D\) such that for all \(x\in S\), \(D(f(x)) = x\) with \(E[TIME(D)] = t' TIME(GL) = O(t'(n^2/\epsilon^2))\).

For a fixed \(x\in S\), define \(A_x(r) = A(f(x),r)\). Then \(Pr_r[A_x(r) = \langle x,r\rangle] \gt 1/2 + \epsilon / 2\).

The Goldreich-Levin Algorithm: given an oracle for \(A_x\), the algorithm outputs all \(y\in\{0,1\}^n\) such that \(\Pr[A_x(r) = \langle y,r\rangle] \gt 1/2 + \epsilon/2\) with running time \(O(n^2/\epsilon^2)\).

It turns out there are at most \(1/\epsilon^2\) such \(y \in\{0,1\}^n\).

Then \(D\) works by scanning the output of the \(GL\) algorithm to find \(f^{-1}(f(x))\).

The Rackoff method for the GL algorithm corrects the predictor probability for \(A\) from \(1/2 + \epsilon\) to \(1-\epsilon\). This corrected predictor can be used to find \(x\).

Let \(f:\mathbb{F}_p\rightarrow\{0,1\}^n\) be a one-to-one function for some \(n\)-bit prime. Define \(g(x,a,b)=[f(x),a,b)]\) where \(a,b\in\mathbb{F}_p\). Then for \(1\le i\le n-\Omega(\log n)\), define \(B_i(x,a,b) = (ax + b \bmod p)|_i\). Note we ignore the \(\log n\) most significant bits because they are biased.

Theorem: If \(f\) is \((t,\epsilon/2)\)-one-way, then for all \(1\le i \le n-\Omega(\log n)\), \(B_i\) is \((t',\epsilon')\)-hardcore for \(g\) where \(t' = t/TIME(Naslund) = t(n^2/\epsilon^2)\) and \(\epsilon' = \epsilon + (c/p)\) for some constant \(c\).

Proof: Suppose there exists \(i, A_i\) such that

Define \(S \subseteq \mathbb{F}_p\) by

We shall build an algorithm \(D\) such that for all \(x\in S\), \(D(f(x)) =x\) and the running time of \(D\) is \(t(n^2/\epsilon^2)\). Naslund’s algorithm finds all such \(x\) in time \(n^2/\epsilon^2\).

Corollary: Let \(p,q\) be prime, and suppose \(q\) is \(n\)-bits. Let \(g\in\mathbb{Z}_p^*\) be an element of order \(q\). Let \(G=\langle g\rangle \triangleleft\mathbb{F}_p^*\). Then for all \(1\le i \le n-\Omega(\log n)\), \(x|_i\) is \((t,\epsilon)\)-hardcore for \(f(x)=g^x \bmod p\) assuming no \((t n^2/\epsilon^2)\)-time discrete logarithm algorithm exists.

Proof: Suppose there exists \(i, A_i\) such that

and \(A_i\) runs in time \(t\). Then we shall construct a discrete log algorithm that outputs \(x\) when given \(y = g^x \bmod p\). Define \(B_y(a,b) = (ax + b \bmod q)|_i\).

Then \(B_y(a,b) = Dlog_g(y^a g^b)|_i\) and

Naslund’s algorithm will find all \(x\)'s that satisfy the above, and one of them is the discrete log of \(y\).

Let \(a_1,...,a_n\in\mathbb{F}_p\) where \(p\) is an \(m\)-bit prime, and let \(s\in\{0,1\}^n\). Set \(b=\sum_{i=1}^n s_i a_i\). The subset sum problem is to find \(s\) given \(a_1,...,a_n,b\). The problem is believed to be hard for \(n\approx m\approx 1000\) on random instances.

Take \(m = (1+\epsilon)n\), for, say, \(\epsilon=1/10\).

Define a generator as follows

On every iteration, \(G\) produces \(mn + m\) bits from \(mn + n\) bits.

Theorem [IN]: \(G\) is a \((t,\epsilon)\)-PRNG assuming no \(t n^2/\epsilon^2\)-time subset sum algorithm exists.

Proof: Suppose there exists \(A\) that \((t,\epsilon)\)-distinguishes between

and

Then we shall construct an algorithm that takes as input \(a_1,...,a_n,b \in\mathbb{F}_p\) and whose goal is to find \(s\in\{0,1\}^n\).

To do this, we build a predictor \(D\) such that

and then use the Goldreich-Levin algorithm to find \(s\). \(D\) is given \(a_1,..,a_n\in\mathbb{F}_p, r\in\{0,1\}^n\), and works as follows: