IACR paper details
Title  The Twin DiffieHellman Problem and Applications 

Booktitle  IACR Eprint archive 

Pages  

Year  2008 

URL  http://eprint.iacr.org/2008/067 

Author  David Cash 

Author  Eike Kiltz 

Author  Victor Shoup 

Abstract 
We propose a new computational problem called the twin DiffieHellman problem. This problem is closely related to the usual (computational) DiffieHellman problem and can be used in many of the same cryptographic constructions that are based on the DiffieHellman problem. Moreover, the twin DiffieHellman problem is at least as hard as the ordinary DiffieHellman problem. However, we are able to show that the twin DiffieHellman 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 DiffieHellman 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 DiffieHellman problem is hard. We present several other applications as well, including: a new variant of Diffie and Hellmans noninteractive key exchange protocol; a new variant of CramerShoup encryption, with a very simple proof in the standard model; a new variant of BonehFranklin identitybased encryption, with very short ciphertexts; a more robust version of a passwordauthenticated key exchange protocol of Abdalla and Pointcheval.


Search for the paper
@misc{eprint200817744,
title={The Twin DiffieHellman Problem and Applications},
booktitle={IACR Eprint archive},
keywords={publickey cryptography / publickey encryption, identitybased 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
}
Download a complete BibTeX file.