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?
The Blum-Blum-Schub construction is a PRNG rather than a stream-cipher. (A stream cipher differs from a PRNG in that it provides for a loading mechanism for the key and an IV.)

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 &lt; {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 &mdash; and even less so the simultaneous bits forming the least significant byte(s). 

Gennaro (2000) proposes to extract a number of low significant bits from the state (starting from the second).

Now many authors proposed an analysis of the concrete security of this (or similar schemes), and of course, you can always take "another look" at it.