Victor Shoup New York University TITLE: The Twin Diffie-Hellman Problem and Applications ABSTRACT: 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. Authors: David Cash, Eike Kiltz, and Victor Shoup