TY - GEN
T1 - The twin diffie-hellman problem and applications
AU - Cash, David
AU - Kiltz, Eike
AU - Shoup, Victor
PY - 2008
Y1 - 2008
N2 - 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" which 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.
AB - 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" which 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.
UR - http://www.scopus.com/inward/record.url?scp=44449176564&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=44449176564&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-78967-3_8
DO - 10.1007/978-3-540-78967-3_8
M3 - Conference contribution
AN - SCOPUS:44449176564
SN - 3540789669
SN - 9783540789666
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 127
EP - 145
BT - Advances in Cryptology - EUROCRYPT 2008 - 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
T2 - 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2008
Y2 - 13 April 2008 through 17 April 2008
ER -