Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-515-96

Authors:

Date:

February 1996

Pages:

13

Download Formats:

We show that computing the most significant bits of the secret key in

a Diffie-Hellman key-exchange protocol from the public keys of the

participants is as hard as computing the secret key itself. This is

done by studying the following {em hidden number problem}: Given an

oracle $O_{alpha,eta}(x)$ that on input $x$ computes the $k$ most

significant bits of $alpha g^x + eta mod p $, find $alpha, eta

mod p$. We present many other applications of this problem

including: (1) MSB's in El-Gamal encryptions, Shamir Message passing

scheme etc. are hard to compute. (2) Factoring with hints. Our

results lead us to suggest a new variant of Diffie-Hellman key

exchange, for which we prove the most significant bit is hard to

compute.