From dawagner@tucson.Princeton.EDU Sat Feb 26 14:14:02 EST 1994
Article: 21021 of sci.crypt
Newsgroups: sci.crypt
Path: princeton!tucson.Princeton.EDU!dawagner
From: dawagner@tucson.Princeton.EDU (David A. Wagner)
Subject: Discrete log bit security
Message-ID: <1994Feb26.080206.11946@Princeton.EDU>
Originator: news@nimaster
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: tucson.princeton.edu
Organization: Princeton University
Date: Sat, 26 Feb 1994 08:02:06 GMT
Lines: 168

I've been reading about discrete logarithms and am curious
the difficulty of guessing just one bit of a discrete log.
[No particular reason, it just seems like an interesting
mathematical question.]  I haven't seen anything about this
in the books I've looked at so far, but then again, our
library's holdings are a little bit, er, ancient. :-)

Would anyone be willing to look at some of my thoughts and
comment?  Books or papers to read would be cool!  I'd even
be happy to see comments like "you're totally confused and
here's why" or "this is trivial, read X" etc etc... :-)

Suppose we're looking at discrete logarithms in GF(p) to
the base g (a generator).  I seem to remember that p-1 should
contain at least one large factor, because otherwise the
discrete log problem isn't too hard.  Should we require
(p-1)/2 to be prime, as in RSA?

Finding the least significant bit of the discrete log of
any x in (Z/pZ)* should be as easy if I understand things
correctly, right?  If x=g^e, the Legendre symbol (x|p)
should be 1 iff e is even, since g must be a quadratic
non-residue [because the set of quadratic residues forms
a subgroup] and thus (g^e|p)=(g|p)^e=(-1)^e.  Did I get
that right?

If my reasoning is correct, finding the most significant
bit of the discrete log should be hard.  Given an oracle
to return the MSB of the discrete log of any element in
(Z/pZ)* [where I define the MSB of the discrete log of
g^e to be 0 if 0 <= e < (p-1)/2 or 1 if (p-1)/2 <= e < p-1]
I think I can construct an algorithm to solve the discrete
log problem.  Define the following functions:

DLogLSB(x,p,g)		# If x=g^e (mod p) calculate the LSB of e
1. if (x|p)=1 return 0 otherwise return 1

ShiftExp(x,p,g)		# If x=g^e (mod p) compute g^(e>>1) (mod p)
1. if DLogLSB(x,p,g)=1 set x <- g^(-1) x (mod p)
2. r <- OneSqrt(x,p)	# Compute one of the two square roots of x (mod p)
3. if MSBOracle(r,p,g)=0 return r otherwise return -r (mod p)

DLog(x,p,g)		# Compute the discrete log of x mod p to the base g
1. y <- 0; i <- 0
2. while x!=1 (mod p)
3.	y <- y | (DLogLSB(x,p,g,) << i)	# | is logical or, << is left shift
4.	x <- ShiftExp(x,p,g)
5.	i <- i+1
6. return y

Perhaps this needs a little explanation and justification.
The basic idea is to discover the least significant bit of
e [if x=g^e] and then quickly transform x=g^e into g^(e>>1)
without actually calculating e.  [e>>1 is e right shifted
by 1 bit.]  Cook until done.

If e is even, surely g^(e/2) is a square root of g^e.  [If
e is odd, then multiplying by the multiplicative inverse
of g transforms x=g^e into an element with even exponent,
for g^(-1) x = g^(e-1) (mod p).]  The main problem, then,
is to calculate the two square roots of x (mod p) and pick
the one with the smaller exponent.  If g^d is a square
root of x=g^e [ie 2d=e (mod p-1)] then g^(d + (p-1)/2)
= -g^d (mod p) is the other square root.

Now the MSBOracle gives us exactly what we want: it enables
to pick out which square root has the smaller exponent.
Repeating this process will terminate after at most log(p)
steps, as the exponent decreases by a factor of 2 at each
step.  Then we've recovered the discrete log of x.

Well, I kinda cheated.  I didn't actually mention how to
calculate the square root of x (mod p).  If p=3 (mod 4)
then r=x^((p+1)/4) is a square root of x.  [Why?  Well,
x is a quadratic residue implies that x^((p-1)/2)=1,
and r^2 = x^((p+1)/2) = x^(1+(p-1)/2) = x (mod p).]
If p=1 (mod 4) I have no clue how to efficiently calculate
a square root of x (mod p) - is there a way?

This gives a algorithm that takes time polynomial in
log(p) for calculating the discrete logarithm given an
oracle to calculate the most significant bit of it - if
my reasoning is correct - and that's a big if.  Can
anyone tell me whether I'm doing ok so far?  Am I totally
confused?

That algorithm should work fairly well even if the
oracle occasionally makes mistakes.  Just change the
last line of DLog to

6. return y mod p

On the other hand, if the oracle has only a 1/2+\epsilon
chance of being correct, then problems arise, and it
might not be polynomial time anymore.  Can anyone help
here?

The algorithm above can also be extended to the second
most significant bit, and more bits too.  [Define the
j-th most significant bit of the discrete logarithm of
x=g^e to be 0 iff floor(2^j e/(p-1)) is even, where
floor(y) is the greatest integer less than or equal
to y.]

For j=2, the ShiftExp function becomes quite a bit more
complicated.  Look at the two square roots of x=g^(2f):
call them r=g^f and -r=g^(f+(p-1)/2).  [Remember, we have
no idea yet which square root is r and which is -r.]  Use
the multiply-by-g^(-1) trick for whichever of the roots
has an odd exponent, and then calculate the two square
roots of each.  You get s=g^(f>>1) and -s=g^(f>>1 + (p-1)/2)
on the one hand, and t=g^((f+(p-1)/2)>>1) and -t on the
other hand.  Use the oracle on s, -s, t, and -t.  You
can see that the 2nd MSB of s and -s will be 0 and the
2nd MSB of t and -t will be 1.  Now we can use this to
tell which root is which, ie which root has the smaller
exponent.  I won't write out a pseudocode description
like above because I'm too lazy. :-)

This trick should extend to the first O(log(log(p))) bits
of e, proving [if my reasoning is correct] that finding
any of the first O(log(log(p))) most significant bits of
the discrete logarithm of x (mod p) is as hard as actually
calculating the discrete logarithm itself.  If you try to
prove the security of j-th MSB, where j>O(log(log(p)))
then you will haveta create a tree of height j in ShiftExp,
so it will certainly take at least O(2^j) time, which is
super-polynomial in log(p).

Do you agree?  Is this trivial, boring, wellknown, false?

I think I can also find a trick to show that the 2nd
least significant bit of the discrete log is secure.
Define the new functions

ShiftExp'(x,p,g)	# If x=g^e (mod p) compute g^(e>>1)
1. if DLogLSB(x,p,g)=1 set x <- g^(-1) x (mod p)
2. r <- OneSqrt(x,p)
3. if DLogLSB(r,p,g)=LSB2Oracle(x,p,g) return r otherwise return -r (mod p)

Also modify DLog to use the new ShiftExp'.  Then I
claim this will work for those p=3 (mod 4).

Why?  Well, (p-1)/2 is odd so DLogLSB(r,p,g) will
always be the complement of DLogLSB(-r,p,g) [since
if r=g^f then -r=g^(f+(p-1)/2)].  Thus exactly one
of r and -r will have an exponent with LSB equal
to the 2nd LSB of the discrete log of x=r^2, and
the root with the correct DLogLSB is exactly the
root with the smaller exponent.

Again this is a polynomial time reduction, and again
it will still work even if the oracle makes a few
infrequent errors.  However, I can't see any way to
extend this to show the security of the j-th least
significant bit of the discrete logarithm for j>2.
I'm probably just being blind. :-/

Ah well, I have all kinds of questions, but this is far
too long already, and if anyone reads this far I'll be
amazed! <grin>  I'd love to hear your criticisms and
comments, as there's really noone around here that I've
found who is interested in cryptography, so I'm pretty
much trying to figure this stuff out on my own.  [It's
not a pretty sight. :-]  Thanks!!

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu