2007 | OriginalPaper | Chapter
A Generalization of DDH with Applications to Protocol Analysis and Computational Soundness
Authors : Emmanuel Bresson, Yassine Lakhnech, Laurent Mazaré, Bogdan Warinschi
Published in: Advances in Cryptology - CRYPTO 2007
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we identify the (
P
,
Q
) −
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
) −
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 [1] 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.