Paper 2008/067

The Twin Diffie-Hellman Problem and Applications

David Cash, Eike Kiltz, and Victor Shoup

Abstract

We propose a new computational problem called the \emph{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 Diffie-Hellman problem in general. Specifically, we show how to build a certain ``trapdoor test'' that allows us to effectively answer decision oracle queries for the twin Diffie-Hellman problem 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.

Note: Appeared at EUROCRYPT 2008. This is the full version.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Preliminary version to appear in EUROCRYPT 2008. This is the full version.
Keywords
public-key encryptionidentity-based encryption
Contact author(s)
cdc @ gatech edu
History
2009-02-10: last of 2 revisions
2008-02-11: received
See all versions
Short URL
https://ia.cr/2008/067
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/067,
      author = {David Cash and Eike Kiltz and Victor Shoup},
      title = {The Twin Diffie-Hellman Problem and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2008/067},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/067}},
      url = {https://eprint.iacr.org/2008/067}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.