A Generalization of DDH with Applications to Protocol Analysis and Computational Soundness

Emmanuel Bresson, Yassine Lakhnech, Laurent Mazare, Bogdan Warinschi

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

33 Citations (Scopus)

Abstract

In this paper we identify the $(P,Q)\mbox{-}\DDH$ assumption, as an extreme, powerful generalization of the Decisional Diffie-Hellman (\DDH) assumption: virtually all previously proposed generalizations of \DDH\ are instances of the $(P,Q)\mbox{-}\DDH$ problem. We prove that our generalization is no harder than \DDH\ through a concrete reduction that we show to be rather tight in most practical cases. One important consequence of our result is that it yields significantly simpler security proofs for protocols that use extensions of \DDH. We exemplify in the case of several group-key exchange protocols (among others we give an elementary, direct proof for the Burmester-Desmedt protocol). Finally, we use our generalization of \DDH\ to extend the celebrated computational soundness result of Abadi and Rogaway~\cite{Abadi00} so that it can also handle exponentiation and Diffie-Hellman-like keys. The extension that we propose crucially relies on our generalization and seems hard to achieve through other means.
Translated title of the contributionA Generalization of DDH with Applications to Protocol Analysis and Computational Soundness
Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2007
PublisherSpringer Berlin Heidelberg
Pages482-499
Volume4622
Publication statusPublished - 2007

Bibliographical note

Other page information: 482-499
Conference Proceedings/Title of Journal: CRYPTO'07
Other identifier: 2000755

Fingerprint

Dive into the research topics of 'A Generalization of DDH with Applications to Protocol Analysis and Computational Soundness'. Together they form a unique fingerprint.

Cite this