]> Cryptography - Hardcore Bits

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

Pr[M(f(X))=B(X)X{0,1 } n]1 /2 <ε

("B(x) is hard to compute from f(x).")


  • Hardcore bit of discrete log [Blum-Micali '81]: Let p be an n-bit prime, g p *. Define B: p *{0,1 } as

B(x)=msb(x)={0 ifx<p/2 1 ifx>p/2

Theorem: B(x) is a (t,ε)-hardcore bit of f(x)=g xmodp assuming there is no tn 3 /ε-time discrete log algorithm in p * (that succeeds with constant probability).

  • Hardcore bit of RSA [ACGS '84]: Let N=pq be an n-bit RSA modulus and e2 . Define B(x)=lsb(x)=xmod2 (B: n{0,1 }.)

Theorem: B(x) is a (t,ε)-hardcore bit of f(x)=x emodN assuming there is no tn 2 /ε 3 -time eth 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:{0,1 } n{0,1 } n be (t,ε)-one-way.

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

Pr[A(f(x))=x i]<1 (1 ε)/n

(If not, then for all i there exists an algorithm A i with Pr[A i(f(x))=x i]1 (1 ε)/n, which would imply Pr[(for all i)A i(f(x))=x i]ε by the union bound, a contradiction.

Yao's XOR Lemma

Theorem: Suppose B:{0,1 } n{0,1 } is a predicate such that for all t-time algorithms A, Pr[A(f(x))=x]<1 ε. Define B m(x 1 ,...,x m)=B(x 1 )...B(x m). Then if m=1 /ε, then for all (t/m)-time A m, we have

Pr[A m(f(x 1 ),...,f(x m))=B m(x 1 ,...,x m)]<1 /2 +ε

(where x 1 ,...,x m{0,1 } n).

This implies that for m=1 /ε, B m is a (t/m,ε)-hardcore bit of f(x 1 )...f(x m).

Goldreich-Levin Method

Given x,y{0,1 } n, define x,y= i=1 nx iy imod2 .

Let f:{0,1 } n{0,1 } n be a (t,ε/2 )-one-way permutation. Define g:{0,1 } 2 n{0,1 } 2 n by g(x,r)=f(X)r. Define B:{0,1 } 2 n{0,1 } by B(x,r)=x,r.

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

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

Pr[A(f(x),r)=x,rx,r{0,1 } n]>1 /2 +ε

Define the set S{0,1 } n by

{x{0,1 } nPr[A(f(x),r)=x,rr{0,1 } n]>1 /2 +ε/2 }

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

By a counting argument, S>(ε/2 )2 n. We shall construct an algorithm D such that for all xS, D(f(x))=x with E[TIME(D)]=tTIME(GL)=O(t(n 2 /ε 2 )).

For a fixed xS, define A x(r)=A(f(x),r). Then Pr r[A x(r)=x,r]>1 /2 +ε/2 .

The Goldreich-Levin Algorithm: given an oracle for A x, the algorithm outputs all y{0,1 } n such that Pr[A x(r)=y,r]>1 /2 +ε/2 with running time O(n 2 /ε 2 ).

It turns out there are at most 1 /ε 2 such y{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 +ε to 1 ε. 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{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𝔽 p. Then for 1 inΩ(logn), define B i(x,a,b)=(ax+bmodp) i. Note we ignore the logn most significant bits because they are biased.

Theorem: If f is (t,ε/2 )-one-way, then for all 1 inΩ(logn), B i is (t,ε)-hardcore for g where t=t/TIME(Naslund)=t(n 2 /ε 2 ) and ε=ε+(c/p) for some constant c.

Proof: Suppose there exists i,A i such that

Pr[A i(f(x),a,b)=(ax+b) i>1 /2 +ε

Define SF p by

S={x𝔽 pPr a,b[A i((f(x),a,b)=(ax+b) i]>1 /2 +ε/2 }

We shall build an algorithm D such that for all xS, D(f(x))=x and the running time of D is t(n 2 /ε 2 ). Naslund's algorithm finds all such x in time n 2 /ε 2 .

Corollary: Let p,q be prime, and suppose q is n-bits. Let g p * be an element of order q. Let G=g𝔽 p *. Then for all 1 inΩ(logn), x i is (t,ε)-hardcore for f(x)=g xmodp assuming no (tn 2 /ε 2 )-time discrete logarithm algorithm exists.

Proof: Suppose there exists i,A i such that

Pr x𝔽 p[A i(g xmodp)=x i]>1 /2 +ε

and A i runs in time t. Then we shall construct a discrete log algorithm that outputs x when given y=g xmodp. Define B y(a,b)=(ax+bmodq) i.

Then B y(a,b)=Dlog g(y ag b) i and

Pr a,b[A i(y ag b)=(ax+bmodq) i]>1 /2 +ε.

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𝔽 p where p is an m-bit prime, and let s{0,1 } n. Set b= i=1 ns ia i. The subset sum problem is to find s given a 1 ,...,a n,b. The problem is believed to be hard for nm1000 on random instances.

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

Define a generator as follows

G(a 1 ,...,a n,s)=(a 1 ,...,a n, i=1 ns ia i).

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

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

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

{(a 1 ,...,a n,R)a 1 ,...,a n𝔽 p}


{(a 1 ,...,a n,b)a 1 ,...,a n𝔽 p,s{0,1 } n,b= i=1 ns ia i}

Then we shall construct an algorithm that takes as input a 1 ,...,a n,b𝔽 p and whose goal is to find s{0,1 } n.

To do this, we build a predictor D such that

Pr[D(a 1 ,...,a n,b,r)=r,s]>1 /2 +ε

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

  1. Pick random t𝔽 p, k{0 ,...,n}

  2. Define a i=a i if r i=0 , otherwise a i=a i+t if r i=1

  3. Run algorithm A on input (a 0 ,...,a n,b+kt).

  4. If A fails, output parity(k), otherwise output 1 parity(k).