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! 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