]> Cryptography - The Blum-Micali Generator

Consider this simple idea for constructing a PRNG: seed the state with some key and pick some encryption algorithm such as DES. Then each iteration, encrypt the current state and output a few bits of it. Intuitively, this seems like it should produce random-looking bits.

The Blum-Micali scheme mimics this process, but on a firm theoretical foundation, by using hardcore bits.

Let $f:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{n}$ be a permutation and $B:\left\{0,1{\right\}}^{n}\to \left\{0,1\right\}$ be a $\left(t,\epsilon \right)$-hardcore bit of $f$. Define ${G}_{\mathrm{BM}}:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{m}$ as follows:

Pick random seed $S\in \left\{0,1{\right\}}^{n}$. For $i=1$ to $m$ 1. Output ${h}_{i}=B\left(S\right)$ 2. $S←f\left(S\right)$

Theorem [Blum-Micali '81]: If $B$ is $\left(t,\epsilon \right)$-hardcore then ${G}_{\mathrm{BM}}$ is a $\left(t-m\mathrm{TIME}\left(f\right),\epsilon m\right)$-PRNG.

Proof: First we devise notation to record the reverse of a bit string. Define ${G}_{\mathrm{BM}}^{R}\left(S\right)=\left[{G}_{\mathrm{BM}}\left(S\right){\right]}^{R}$, that is, if ${G}_{\mathrm{BM}}\left(S\right)={b}_{1}...{b}_{m}$, then ${G}_{\mathrm{BM}}^{R}\left(S\right)={b}_{m}...{b}_{1}$.

Then note that if ${G}_{\mathrm{BM}}^{R}$ is a $\left(t,\epsilon \right)$-PRNG, then ${G}_{\mathrm{BM}}$ is also a $\left(t,\epsilon \right)$-PRNG.

Now suppose ${G}_{\mathrm{BM}}^{R}$ is not a $\left(t-m\mathrm{TIME}\left(f\right),m\epsilon \right)$-PRNG. Then there exists a $\left(t-m\mathrm{TIME}\left(f\right)\right)$ algorithm $A$, and $0\le i such that

$\mathrm{Pr}\left[A\left({G}_{\mathrm{BM}}^{R}\left(S\right){\mid }_{1...i}\right)={G}_{\mathrm{BM}}^{R}\left(S\right){\mid }_{i+1}\right]\ge 1/2+\epsilon$

We shall build an algorithm $A\prime$ that predicts $B\left(x\right)$ given $f\left(x\right)$.

Let $S\in \left\{0,1{\right\}}^{n}$ and define $y={f}^{m-i}\left(S\right)$. Then

$\begin{array}{ccc}{G}_{\mathrm{BM}}^{R}\left(S\right){\mid }_{1...i}& =& \left[B\left({f}^{m}\left(S\right)\right),B\left({f}^{m-1}\left(S\right)\right),...,B\left({f}^{m-i+1}\left(S\right)\right)\right]\\ & =& \left[B\left({f}^{i}\left(y\right)\right),...,B\left(f\left(y\right)\right)\right]\end{array}$

Algorithm $A\prime$ acts as follows. Given $z=f\left(y\right)$,

1. Compute $T\left(z\right)=\left[B\left({f}^{i-1}\left(z\right)\right),...,B\left(z\right)\right]$

2. Output $A\left(T\left(z\right)\right)$.

Note that $\mathrm{TIME}\left(A\prime \right)$ = $t$. Then we wish to show that

$\mathrm{Pr}\left[A\prime \left(f\left(y\right)\right)=B\left(y\right)\mid y←\left\{0,1{\right\}}^{n}\right]\ge 1/2+\epsilon$

This follows since $f$ is a permutation and hence the distribution $\left\{{T}_{z}\mid y←\left\{0,1{\right\}}^{n},z=f\left(y\right)\right\}$ is identical to the distribution $\left\{{G}_{\mathrm{BM}}^{R}\left(S\right){\mid }_{1...i}\mid S←\left\{0,1{\right\}}^{n}\right\}$.

This is a contradiction because $B$ is $\left(t,\epsilon \right)$-hardcore for $f$.

## Examples of BM generators

• Dlog generator: $p=1024$-bit prime, $g\in {ℤ}_{p}^{*}$ a generator. Let $f:\left\{1,...,p-1\right\}\to \left\{1,...,p-1\right\}$, $f\left(x\right)={g}^{x}\mathrm{mod}p$. We know $\mathrm{MSB}\left(x\right)=\left\{0\text{if}x

p/2$

is a $\left(t,\epsilon \right)$-hardcore bit of $f$ if no ${\mathrm{tn}}^{3}/\epsilon$-time discrete log algorithm exists. Thus we have a PRNG assuming Dlog is hard.

• Blum-Blum-Shub (BBS): $N=\mathrm{pq}$ 1024-bit, $p=q=3\mathrm{mod}4$. Let ${\mathrm{QR}}_{N}=\left\{x\in {ℤ}_{N}^{*}\mid x\text{is QR}\right\}$. Then $f\left(x\right)={x}^{2}\mathrm{mod}N$ is a permutation of ${\mathrm{QR}}_{N}$. LSB(x) is $\left(t,\epsilon \right)$-hardcore for $f$ assuming no $\left({\mathrm{tn}}^{2}/\epsilon \right)$ factoring algorithm exists.

1. $S←{\mathrm{QR}}_{N}$

2. Output $\mathrm{LSB}\left(S\right)$

3. $S←{S}^{2}\left(\mathrm{mod}N\right)$

4. Goto step 1

[BBS not $\left(t,\epsilon \right)$-hardcore implies LSB is not $\left(t,\epsilon /m\right)$-hardcore (where $m$ is the number of output bits), which implies there exists a $t\left({n}^{m}/\epsilon {\right)}^{2}$-time factoring algorithm (where $n=\mathrm{lg}N$).]

Example: suppose no ${2}^{100}$-time factoring algorithm exists for 1024-bit numbers, and that $m={2}^{20}$. Then we get that BBS is secure for $t/{\mathrm{epsilon}}^{2}={2}^{40}$, e.g. BBS is a $\left({2}^{20},{2}^{-10}\right)$-PRNG, which is not secure.

### Speeding up BM

We can output one bit per application of $f$. Can we output more?

For Dlog it turns out that for $i=1,...,n/2$ the msb_i(x) is a hardcore bit. But this is not enough. We need a notion of simultaneous security.

Definition: Let $f:\left\{0,1{\right\}}^{n}\to \left\{0,1\right\}$. Then bits ${B}_{1},...,{B}_{k}:\left\{0,1{\right\}}^{n}\to \left\{0,1\right\}$ are $\left(t,\epsilon \right)$-simultaneously secure if $\left\{f\left(x\right),{B}_{1}\left(x\right),...,{B}_{k}\left(x\right)\mid x\in \left\{0,1\right\}\right\}$ is $\left(t,\epsilon \right)$-indistinguishable from $\left\{f\left(x\right),{r}_{1},...,{r}_{k}\mid {r}_{1}...{r}_{k}←\left\{0,1{\right\}}^{k}$.

The Blum-Micali Theorem remains true for simultaneously secure bits.

Best result for Dlog [Shamir-Schrift]: $N=\mathrm{pq},f\left(x\right)={g}^{x}\mathrm{mod}N$. Then the bits in the most significant half of $x$ are $\left(t,\epsilon \right)$-simultaneously secure for $f$ assuming no $O\left(t\left(n/\epsilon {\right)}^{3}\right)$-time factoring algorithms exist.