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 13:28:09 +0000 (UTC)

Julia Faflek <faflek@upb.de> wrote:
>Heiko Stamer wrote:
>> Now my questions: Can we reduce the size of r (similar to [3]) without
>> essential weakening the DDH? What is know about lattice based attacks like
>> [4] in such cases? (We don't use "small" subgroups.) Are there any helpful
>> references (on these topics) that I've missed?
>
>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.

This paper refers to exponents where the lower-order bits are
zero. I believe Heiko Stamer is asking about exponents where the
high-order bits are zero.