Cryptography

It is possible to find a hardcore bit of any given one-way permutation:

• Yao's XOR Lemma ['82]

• Goldreich-Levin ['87]

• Naslund ['96]

Yao's Method

Let $f:\{\mathrm{0,1}{\}}^n\to \{\mathrm{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$,

$$\mathrm{Pr}[A(f(x))=x{\mid }_i]<1-(1-\epsilon )/n$$

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

Yao's XOR Lemma

Theorem: Suppose $B:\{\mathrm{0,1}{\}}^n\to \{\mathrm{0,1}\}$ is a predicate such that for all $t$-time algorithms $A$, $\mathrm{Pr}[A(f(x))=x]<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

$$\mathrm{Pr}[A_m(f(x_1),...,f(x_m))=B_m(x_1,...,x_m)]<1/2+\epsilon$$

(where $x_1,...,x_m\leftarrow \{\mathrm{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)\mid \mid ...\mid \mid f(x_m)$.

Goldreich-Levin Method

Given $x,y\in \{\mathrm{0,1}{\}}^n$, define $⟨x,y⟩={\sum }_{i=1}^n{x}_i{y}_{i}mod2$.

Let $f:\{\mathrm{0,1}{\}}^n\to \{\mathrm{0,1}{\}}^n$ be a $(t,\epsilon /2)$-one-way permutation. Define $g:\{\mathrm{0,1}{\}}^{2n}\to \{\mathrm{0,1}{\}}^{2n}$ by $g(x,r)=f(X)\mid \mid r$. Define $B:\{\mathrm{0,1}{\}}^{2n}\to \{\mathrm{0,1}\}$ by $B(x,r)=⟨x,r⟩$.

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

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

$$\mathrm{Pr}[A(f(x),r)=⟨x,r⟩\mid x,r\leftarrow \{\mathrm{0,1}{\}}^n]>1/2+\epsilon$$

Define the set $S\subseteq \{\mathrm{0,1}{\}}^n$ by

$$\{x\in \{\mathrm{0,1}{\}}^n\mid \mathrm{Pr}[A(f(x),r)=⟨x,r⟩\mid r\leftarrow \{\mathrm{0,1}{\}}^n]>1/2+\epsilon /2\}$$

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

By a counting argument, $\mid S\mid >(\epsilon /2)2^n$. We shall construct an algorithm $D$ such that for all $x\in S$, $D(f(x))=x$ with $E[\mathrm{TIME}(D)]=t\prime \mathrm{TIME}(\mathrm{GL})=O(t\prime (n^2/{\epsilon }^2))$.

For a fixed $x\in S$, define $A_x(r)=A(f(x),r)$. Then ${\mathrm{Pr}}_r[A_x(r)=⟨x,r⟩]>1/2+\epsilon /2$.

The Goldreich-Levin Algorithm: given an oracle for $A_x$, the algorithm outputs all $y\in \{\mathrm{0,1}{\}}^n$ such that $\mathrm{Pr}[A_x(r)=⟨y,r⟩]>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 \{\mathrm{0,1}{\}}^n$.

Then $D$ works by scanning the output of the $\mathrm{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$.

• Every one-way permutation has an efficient hardcore bit.

• The proof is based on a noisy predictor for the inner product.

• The GL algorithm is found in learning theory.

Naslund Method

Let $f:{𝔽}_p\to \{\mathrm{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 {𝔽}_p$. Then for $1\le i\le n-\Omega (\log n)$, define $B_i(x,a,b)=(\mathrm{ax}+bmodp){\mid }_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\prime ,\epsilon \prime )$-hardcore for $g$ where $t\prime =t/\mathrm{TIME}(\mathrm{Naslund})=t(n^2/{\epsilon }^2)$ and $\epsilon \prime =\epsilon +(c/p)$ for some constant $c$.

Proof: Suppose there exists $i,A_i$ such that

$$\mathrm{Pr}[A_i(f(x),a,b)=(\mathrm{ax}+b){\mid }_i>1/2+\epsilon$$

Define $S\subseteq F_p$ by

$$S=\{x\in {𝔽}_p\mid {\mathrm{Pr}}_{a,b}[A_i((f(x),a,b)=(\mathrm{ax}+b){\mid }_i]>1/2+\epsilon \prime /2\}$$

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=⟨g⟩◃{𝔽}_p^{*}$. Then for all $1\le i\le n-\Omega (\log n)$, $x{\mid }_i$ is $(t,\epsilon )$-hardcore for $f(x)=g^{x}modp$ assuming no $(t{n}^2/{\epsilon }^2)$-time discrete logarithm algorithm exists.

Proof: Suppose there exists $i,A_i$ such that

$${\mathrm{Pr}}_{x\in {𝔽}_p}[A_i(g^{x}modp)=x{\mid }_i]>1/2+\epsilon$$

and $A_i$ runs in time $t$. Then we shall construct a discrete log algorithm that outputs $x$ when given $y=g^{x}modp$. Define $B_y(a,b)=(\mathrm{ax}+b\mathrm{mod}q){\mid }_i$.

Then $B_y(a,b)={\mathrm{Dlog}}_g(y^a{g}^b){\mid }_i$ and

$${\mathrm{Pr}}_{a,b}[A_i(y^a{g}^b)=(\mathrm{ax}+bmodq){\mid }_i]>1/2+\epsilon .$$

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

Subset Sum Generator [IN '88]

Let $a_1,...,a_n\in {𝔽}_p$ where $p$ is an $m$-bit prime, and let $s\in \{\mathrm{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

$$G(a_1,...,a_n,s)=(a_1,...,a_n,\sum _{i=1}^n{s}_i{a}_i).$$

On every iteration, $G$ produces $\mathrm{mn}+m$ bits from $\mathrm{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

$$\{(a_1,...,a_n,R)\mid a_1,...,a_n\leftarrow {𝔽}_p\}$$

and

$$\{(a_1,...,a_n,b)\mid a_1,...,a_n\leftarrow {𝔽}_p,s\leftarrow \{\mathrm{0,1}{\}}^n,b=\sum _{i=1}^n{s}_i{a}_i\}$$

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

To do this, we build a predictor $D$ such that

$$\mathrm{Pr}[D(a_1,...,a_n,b,r)=⟨r,s⟩]>1/2+\epsilon$$

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

1. Pick random $t\leftarrow {𝔽}_p$, $k\leftarrow \{0,...,n\}$

2. Define $a{\prime }_i=a_i$ if $r_i=0$, otherwise $a{\prime }_i=a_i+t$ if $r_i=1$

3. Run algorithm $A$ on input $(a{\prime }_0,...,a{\prime }_n,b+\mathrm{kt})$.

4. If $A$ fails, output $\mathrm{parity}(k)$, otherwise output $1-\mathrm{parity}(k)$.