Re: Order question

From: An Metet (anmetet_at_freedom.gmsociety.org)
Date: 04/30/04 

Date: Thu, 29 Apr 2004 21:20:36 -0400

NOTE: This message was sent thru a mail2news gateway.
No effort was made to verify the identity of the sender.
--------------------------------------------------------

Peter Fairbrother wrote:
>> Next question. Can you simply show that the subgroup of order q is the same
>> group as the group of QR's? I've done this before, but I lost it.

We will show that every element in the subgroup of order q is a QR,
by constructing a square root for each element. Each such element can
be expressed as g^k for a g which generates the group. If k is even
the square root is g^(k/2). If k is odd, k+q is even since q is odd,
so g^((k+q)/2) is the square root. QED.

> A typical DH with optimisation will have p = mq+1, and use a generator of
> the subgroup of order q. Are there any security implications to using a q of
> the usual say 160 bits size, but with small Hamming weight?

Of course DH is not known to be as secure as the DL problem. So there
are two questions here: one is whether such a q would provide an attack
on DH without solving discrete logs; and the other is whether such a
q would speed up solutions of the DL problem. Unfortunately I am not
qualified to answer either of these.

I can only state the obvious, that the commonly discussed DL algorithms,
including Shanks, Pollard rho and kangaroo, do not get sped up by a
special q, nor would methods aiming at p like the number field sieve be
affected by q at all. The one minor consideration is that a low hamming
weight q is likely to be half the size of an average q of the same bit
length, hence would be solved sqrt(2) times faster than an average q by
the q-based algorithms.

A low hamming weight q would be advantageous for allowing quick tests
of group membership. Many DL protocols have hidden flaws if they skip
these tests, as shown for example by the work of Lim and Lee. If such
q values are in fact safe then they would be useful for DL protocols.