Re: Hardness of DDH with short exponents

From: Kristian Gjøsteen (kristiag+news_at_item.ntnu.no)
Date: 01/28/05 

Date: Fri, 28 Jan 2005 10:00:36 +0000 (UTC)

David Wagner <daw-usenet@taverner.cs.berkeley.edu> wrote:
>Heiko Stamer wrote:
>>Now my questions: Can we reduce the size of r (similar to [3]) without
>>essential weakening the DDH?

One way to reduce the exponent length is to use a subgroup that is
hard to distinguish from the entire subgroup.

Example: If n=ab is an RSA modulus such that p=2n+1 is prime, you
have two subgroups (order a and order b) of Q_p that seem to be
hard to distinguish from the rest of the group Q_p.

There are other examples with other groups.

>Interesting question! I don't know. All I can say is that I don't
>know of any attacks.
>
>Here is one (very strong) condition which I suppose would be sufficient
>to guarantee that there is no weakening. Let f_k : QR_p -> QR_p be
>defined by f_k(x) = x^k mod p. Let E be a random variable distributed
>uniformly on [q]={0,..,q-1}. Let E' be a random variable distributed
>uniformly on [2^160], the space of short exponents. Suppose it were
>true that no efficient algorithm A can distinguish an oracle for f_E
>from an oracle for f_E'. Then I think it would follow that DDH is safe
>for use with exponents from [2^160] if DDH is safe with exponents from
>[q]. This doesn't help very much, since we don't have any more reason to
>believe that this condition holds than to simply believe that DDH is safe
>with short exponents, so I apologize that I wasn't able to help very much.

I believe this kind of reasoning makes sense, since you get two
essentially independent assumptions, instead of one complicated
assumption.

For what it's worth: I suggested this assumption at PKC'05 on Monday,
as a way to speed up one of my cryptosystems. There were no protests
from the listeners.

Here's the relevant quote from my slides (K is a group):

        Small-exponent assumption

        Let g be a generator for K. It is hard to distinguish the set
        { g^i | 1 <= i < 2^(2t) } from the set { g^i | 2^(2t) <= i < |K| }.

(The smaller set can obviously be distinguished with O(2^t) work.)

Relevant Pages