Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
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

1 Answer

up vote 2 down vote

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 < {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).

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.

share|improve this answer
1  
Do you know the concrete security claims of proof? For example for BBS, the non-tight reduction in the proof lead to a huge modulus that's practically unusable. – CodesInChaos Oct 11 '12 at 21:53
I don't know the details, but BM is going to be tremendously slow and Gennaro's proposal is probably comparable to BBS. Gennaro proposes a nice implementation trick, but this is not going to change the practicality of it. – bob Oct 15 '12 at 19:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.