DIMACS Special Year on Networks Seminar


On the hardness of computing most significant bits of a Diffie-Hellman secret


Dan Boneh


AT&T Murray Hill Building, Room: 2A-435
Note: Visitors not from the MH building should use the east side entrance "stairway 9", and call Avishai Wool, phone number 6576, to let them in. Since entering the MH building takes time, visitors are requested to arrive no latter than 1:45pm.
AT&T Host: Avishai Wool


2:00 p.m
Friday, January 24, 1997

We study the hardness of computing the most significant bits of the secret key in a Diffie-Hellman key-exchange protocol from the public keys of the participants. Most of our techniques are based on lattices, specifically lattice reductions and rounding. In this talk we will survey our current state of knowledge on this topic including some new results. Our methods are general enough and can be used to prove the hardness of computing bits in other schemes related to Diffie-Hellman. Examples include ElGamal's public key system, Shamir's message passing scheme and Okamoto's conference key sharing scheme. Our results leads us to suggest a simple variant of the Diffie-Hellman key exchange, for which we prove the single most significant bit is hard to compute.

Joint work with R. Venkatesan.

Document last modified on January 17, 1997