Victor Shoup
New York University

The Twin Diffie-Hellman Problem and Applications

We propose the \emph{strong twin Diffie-Hellman} assumption, a new interactive
assumption that we prove equivalent than the standard Diffie-Hellman (DH)
assumption.  We use it to construct the first redudancy-free public-key
encryption scheme based on the DH assumption in the random oracle model.
We find several other applications for these ideas, including \emph{non-interactive}
authenticated key exchange, securing password authenticated key exchange against
server compromise, and redundancy-free identity-based encryption. 

David Cash, Eike Kiltz, and Victor Shoup