# DIMACS Special Year on Networks Seminar

## Title:

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

## Speaker:

- Dan Boneh
- Bellcore

## Place:

- 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

## Time:

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

Abstract:
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