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

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.