# Stream ciphers based on discrete logs

Blum Blum Shub is a stream cipher that is provably reducible to the difficulty of factoring integers.

I'm wondering whether there is a similar construction for discrete logs?

For example, I could imagine having something like this being the update function for the internal state:

$x_{i+1} = g^{x_i} \mod p$

And then you just XOR the least significant byte with the plain-text.

Does anyone know of analysis of these type of constructions?

• Discrete log is not a permutation. So $x_{i+1} = g^{x_i} \mod p$ will not necessarily work, as $x_i$ is most likely not an element of $\mathbb{Z}_q$ (q being the order of the group we are working in) – Maeher Jul 3 '12 at 21:31
• It's important to note that most of these reductions only apply in the asymptotic limit, and make no useful statement about the security of realistic key sizes. – CodesInChaos Jul 4 '12 at 9:13
• Not directly DL based, but based on the related DH problem: Dual_EC_DRBG. The infamous backdoored PRNG. – CodesInChaos Oct 11 '12 at 21:49

There is a similar proposal for a PRNG based on the hardness of computing discrete logarithms by Blum and Micali (How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, 1984). The extraction from the internal state $x_i$ consists in a bit the value reflecting the outcome of the test $[x_i < {p-1\over 2}]$.
Please note that the construction you propose cannot be proven secure with the standard methodology in that the lowest significant bit of $x$ can always be determined given the value of $g^x\mod p$, so that it cannot be proven to be a hard-core bit for the corresponding one-way function — and even less so the simultaneous bits forming the least significant byte(s).