## CryptoDB

### Paper: The Twin Diffie-Hellman Problem and Applications

Authors: David Cash Eike Kiltz Victor Shoup URL: http://eprint.iacr.org/2008/067 Search ePrint Search Google We propose a new computational problem called the twin Diffie-Hellman problem. This problem is closely related to the usual (computational) Diffie-Hellman problem and can be used in many of the same cryptographic constructions that are based on the Diffie-Hellman problem. Moreover, the twin Diffie-Hellman problem is at least as hard as the ordinary Diffie-Hellman problem. However, we are able to show that the twin Diffie-Hellman problem remains hard, even in the presence of a decision oracle that recognizes solutions to the problem  this is a feature not enjoyed by the ordinary Diffie-Hellman problem. In particular, we show how to build a certain trapdoor test that allows us to effectively answer such decision oracle queries without knowing any of the corresponding discrete logarithms. Our new techniques have many applications. As one such application, we present a new variant of ElGamal encryption with very short ciphertexts, and with a very simple and tight security proof, in the random oracle model, under the assumption that the ordinary Diffie-Hellman problem is hard. We present several other applications as well, including: a new variant of Diffie and Hellmans non-interactive key exchange protocol; a new variant of Cramer-Shoup encryption, with a very simple proof in the standard model; a new variant of Boneh-Franklin identity-based encryption, with very short ciphertexts; a more robust version of a password-authenticated key exchange protocol of Abdalla and Pointcheval.
##### BibTeX
@misc{eprint-2008-17744,
title={The Twin Diffie-Hellman Problem and Applications},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / public-key encryption, identity-based encryption},
url={http://eprint.iacr.org/2008/067},
note={Preliminary version to appear in EUROCRYPT 2008. This is the full version. cdc@gatech.edu 14041 received 8 Feb 2008, last revised 11 Jun 2008},
author={David Cash and Eike Kiltz and Victor Shoup},
year=2008
}