|
Abstract : |
We show that computing the most significant bits of the secret key in a Diffie-Hellman keyexchange protocol from the public keys of the participants is as hard as computing the secret key itself. This is done by studying the following hidden number problem: Given an oracle O ff;fi (x) that on input x computes the k most significant bits of ffg x + fi mod p, find ff; fi 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, |
