Re: Hardness of DDH with short exponents

From: Heiko Stamer (stamer_at_gaos.org)
Date: 02/02/05 

Date: Wed, 02 Feb 2005 00:26:14 +0100

First, I want to thank everybody who contributed to this thread.

Julia Faflek wrote:
> I refer you to the paper "Koshiba & Kurosawa: Short Exponent
> Diffie-Hellman Problems" (PKC 2004, LNCS 2947, pp. 173-186) in which it
> is shown that short-exponent-DDH is as hard as DDH and discrete
> logarithms with short exponents.

I've got it and roughly read. This was exactly the reference I was
looking for. Thus one can compute the masking operations [1] in a more
efficient way. The additional DLSE assumption seems to be reasonable for
our application. However, we should "add a large safety margin" ;-)

By the way: Camenisch et al. [2] using a subgroup DDH assumption to
guarantee privacy in their "Direct Anonymous Attestation" protocol.
They use non-shifted but shortened exponents (split into two parts,
each of size e.g. 104 bit) and work in a prime order (e.g. |q| 208 bit)
subgroup of Z/pZ (|p| 1632 bit), where p = rq + 1 and p, q are both
primes. Can their assumption be related to DLSE+DDH, too?

David Wagner wrote:

>>I don't understand the problem. Where is the difference when using a
>>group G of odd order? Then it is possible to shift the least significant
>>bits which are zero by (g^r)^(2^-i mod |G|) to the high-order bits or
>>not?
>
> I agree. Sounds equivalent if the group order |G| is known and odd.

For our group QR_p the order is known (odd prime). Although the generation
of safe primes is less efficient it does not really matter here, because
this part will be done very rarely.

[1] Adam Barnett, Nigel P. Smart: Mental Poker Revisited, 2003.
[2] E. Brickell, J. Camenisch, L. Chen: Direct Anonymous Attestation, 2004.

Relevant Pages

  • Re: Sandwich primes!
    ... >>more primes than the Mersenne's. ... The Mersenne numbers for all odd ... where the Mersenne primes only have ... for the first 25 prime exponents. ...
    (sci.math)
  • Re: Proof Attempt For Fermats Last Theorem
    ... takes time to learn from your mistakes and finally suceed. ... primefactors and the possible exponents. ... numbers, squarefreeness of Mersenne numbers, Sophie Germain-primes, ... then the problem of the difficult properties of Wieferich primes, ...
    (sci.math)
  • Re: numbers n with large sum of divisors compared to n
    ... The ratio sigma/n can grow with n, ... Since the product over all primes ... This means that by adjusting the exponents of the prime factors of n, ... Using and the multiplicativity of sigma/n, ...
    (sci.math)
  • Re: numbers n with large sum of divisors compared to n
    ... The ratio sigma/n can grow with n, ... Since the product over all primes ... This means that by adjusting the exponents of the prime factors of n, ... Using and the multiplicativity of sigma/n, ...
    (sci.math)
  • Re: Formulating sentences in a possibly consistent ZF
    ... You might be interested to know that Goldbach's weak conjecture, ... every integer greater than 5 can be written as the sum of 3 primes, ... single odd ... on Dedekind's property of infinity. ...
    (sci.logic)