]> Cryptography - Hardcore Bits

Let $f:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{n}$ be a permutation. A $\left(t,\epsilon \right)$-hardcore bit is a function $B:\left\{0,1{\right\}}^{n}\to \left\{0,1\right\}$ (predicate) such that for any $t$-time algorithm $M$ we have

$\mid \mathrm{Pr}\left[M\left(f\left(X\right)\right)=B\left(X\right)\mid X←\left\{0,1{\right\}}^{n}\right]-1/2\mid <\epsilon$

("$B\left(x\right)$ is hard to compute from $f\left(x\right)$.")

Examples:

• Hardcore bit of discrete log [Blum-Micali '81]: Let $p$ be an $n$-bit prime, $g\in {ℤ}_{p}^{*}$. Define $B:{ℤ}_{p}^{*}\to \left\{0,1\right\}$ as

$B\left(x\right)=\mathrm{msb}\left(x\right)=\left\{\begin{array}{cc}0& \mathrm{if}x

p/2\end{array}$

Theorem: $B\left(x\right)$ is a $\left(t,\epsilon \right)$-hardcore bit of $f\left(x\right)={g}^{x}\mathrm{mod}p$ assuming there is no $t{n}^{3}/\epsilon$-time discrete log algorithm in ${ℤ}_{p}^{*}$ (that succeeds with constant probability).

• Hardcore bit of RSA [ACGS '84]: Let $N=\mathrm{pq}$ be an $n$-bit RSA modulus and $e\ge 2$. Define $B\left(x\right)=\mathrm{lsb}\left(x\right)=x\mathrm{mod}2$ ($B:{ℤ}_{n}\to \left\{0,1\right\}$.)

Theorem: $B\left(x\right)$ is a $\left(t,\epsilon \right)$-hardcore bit of $f\left(x\right)={x}^{e}\mathrm{mod}N$ assuming there is no $t{n}^{2}/{\epsilon }^{3}$-time $e$th root algorithm for ${ℤ}_{N}^{*}$.

The Blum-Micali generator is a PRNG that is constructed from hardcore bits.

Hardcore bits for general one-way permutations

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:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{n}$ be $\left(t,\epsilon \right)$-one-way.

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

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

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

Yao's XOR Lemma

Theorem: Suppose $B:\left\{0,1{\right\}}^{n}\to \left\{0,1\right\}$ is a predicate such that for all $t$-time algorithms $A$, $\mathrm{Pr}\left[A\left(f\left(x\right)\right)=x\right]<1-\epsilon$. Define ${B}_{m}\left({x}_{1},...,{x}_{m}\right)=B\left({x}_{1}\right)\oplus ...\oplus B\left({x}_{m}\right)$. Then if $m=⌊1/\epsilon ⌋$, then for all $\left(t/m\right)$-time ${A}_{m}$, we have

$\mathrm{Pr}\left[{A}_{m}\left(f\left({x}_{1}\right),...,f\left({x}_{m}\right)\right)={B}_{m}\left({x}_{1},...,{x}_{m}\right)\right]<1/2+\epsilon$

(where ${x}_{1},...,{x}_{m}←\left\{0,1{\right\}}^{n}$).

This implies that for $m=⌊1/\epsilon ⌋$, ${B}_{m}$ is a $\left(t/m,\epsilon \right)$-hardcore bit of $f\left({x}_{1}\right)\mid \mid ...\mid \mid f\left({x}_{m}\right)$.

Goldreich-Levin Method

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

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

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

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

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

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

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

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

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

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

The Goldreich-Levin Algorithm: given an oracle for ${A}_{x}$, the algorithm outputs all $y\in \left\{0,1{\right\}}^{n}$ such that $\mathrm{Pr}\left[{A}_{x}\left(r\right)=⟨y,r⟩\right]>1/2+\epsilon /2$ with running time $O\left({n}^{2}/{\epsilon }^{2}\right)$.

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

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

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 \left\{0,1{\right\}}^{n}$ be a one-to-one function for some $n$-bit prime. Define $g\left(x,a,b\right)=\left[f\left(x\right),a,b\right)\right]$ where $a,b\in {𝔽}_{p}$. Then for $1\le i\le n-\Omega \left(\mathrm{log}n\right)$, define ${B}_{i}\left(x,a,b\right)=\left(\mathrm{ax}+bmodp\right){\mid }_{i}$. Note we ignore the $\mathrm{log}n$ most significant bits because they are biased.

Theorem: If $f$ is $\left(t,\epsilon /2\right)$-one-way, then for all $1\le i\le n-\Omega \left(\mathrm{log}n\right)$, ${B}_{i}$ is $\left(t\prime ,\epsilon \prime \right)$-hardcore for $g$ where $t\prime =t/\mathrm{TIME}\left(\mathrm{Naslund}\right)=t\left({n}^{2}/{\epsilon }^{2}\right)$ and $\epsilon \prime =\epsilon +\left(c/p\right)$ for some constant $c$.

Proof: Suppose there exists $i,{A}_{i}$ such that

$\mathrm{Pr}\left[{A}_{i}\left(f\left(x\right),a,b\right)=\left(\mathrm{ax}+b\right){\mid }_{i}>1/2+\epsilon$

Define $S\subseteq {F}_{p}$ by

$S=\left\{x\in {𝔽}_{p}\mid {\mathrm{Pr}}_{a,b}\left[{A}_{i}\left(\left(f\left(x\right),a,b\right)=\left(\mathrm{ax}+b\right){\mid }_{i}\right]>1/2+\epsilon \prime /2\right\}$

We shall build an algorithm $D$ such that for all $x\in S$, $D\left(f\left(x\right)\right)=x$ and the running time of $D$ is $t\left({n}^{2}/{\epsilon }^{2}\right)$. 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 {ℤ}_{p}^{*}$ be an element of order $q$. Let $G=⟨g⟩◃{𝔽}_{p}^{*}$. Then for all $1\le i\le n-\Omega \left(\mathrm{log}n\right)$, $x{\mid }_{i}$ is $\left(t,\epsilon \right)$-hardcore for $f\left(x\right)={g}^{x}modp$ assuming no $\left(t{n}^{2}/{\epsilon }^{2}\right)$-time discrete logarithm algorithm exists.

Proof: Suppose there exists $i,{A}_{i}$ such that

${\mathrm{Pr}}_{x\in {𝔽}_{p}}\left[{A}_{i}\left({g}^{x}modp\right)=x{\mid }_{i}\right]>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}\left(a,b\right)=\left(\mathrm{ax}+b\mathrm{mod}q\right){\mid }_{i}$.

Then ${B}_{y}\left(a,b\right)={\mathrm{Dlog}}_{g}\left({y}^{a}{g}^{b}\right){\mid }_{i}$ and

${\mathrm{Pr}}_{a,b}\left[{A}_{i}\left({y}^{a}{g}^{b}\right)=\left(\mathrm{ax}+bmodq\right){\mid }_{i}\right]>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 \left\{0,1{\right\}}^{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=\left(1+\epsilon \right)n$, for, say, $\epsilon =1/10$.

Define a generator as follows

$G\left({a}_{1},...,{a}_{n},s\right)=\left({a}_{1},...,{a}_{n},\sum _{i=1}^{n}{s}_{i}{a}_{i}\right).$

On every iteration, $G$ produces $\mathrm{mn}+m$ bits from $\mathrm{mn}+n$ bits.

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

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

$\left\{\left({a}_{1},...,{a}_{n},R\right)\mid {a}_{1},...,{a}_{n}←{𝔽}_{p}\right\}$

and

$\left\{\left({a}_{1},...,{a}_{n},b\right)\mid {a}_{1},...,{a}_{n}←{𝔽}_{p},s←\left\{0,1{\right\}}^{n},b=\sum _{i=1}^{n}{s}_{i}{a}_{i}\right\}$

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 \left\{0,1{\right\}}^{n}$.

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

$\mathrm{Pr}\left[D\left({a}_{1},...,{a}_{n},b,r\right)=⟨r,s⟩\right]>1/2+\epsilon$

and then use the Goldreich-Levin algorithm to find $s$. $D$ is given ${a}_{1},..,{a}_{n}\in {𝔽}_{p},r\in \left\{0,1{\right\}}^{n}$, and works as follows:

1. Pick random $t←{𝔽}_{p}$, $k←\left\{0,...,n\right\}$

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 $\left(a{\prime }_{0},...,a{\prime }_{n},b+\mathrm{kt}\right)$.

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