Paper 2017/517

PRF-ODH: Relations, Instantiations, and Impossibility Results

Jacqueline Brendel, Marc Fischlin, Felix Günther, and Christian Janson


The pseudorandom-function oracle-Diffie–Hellman (PRF-ODH) assumption has been introduced recently to analyze a variety of DH-based key exchange protocols, including TLS 1.2 and the TLS 1.3 candidates, as well as the extended access control (EAC) protocol. Remarkably, the assumption comes in different flavors in these settings and none of them has been scrutinized comprehensively yet. In this paper here we therefore present a systematic study of the different PRF-ODH variants in the literature. In particular, we analyze their strengths relative to each other, carving out that the variants form a hierarchy. We further investigate the boundaries between instantiating the assumptions in the standard model and the random oracle model. While we show that even the strongest variant is achievable in the random oracle model under the strong Diffie–Hellman assumption, we provide a negative result showing that it is implausible to instantiate even the weaker variants in the standard model via algebraic black-box reductions to common cryptographic problems.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2017
PRF-ODHkey exchange
Contact author(s)
jacqueline brendel @ cryptoplexity de
2017-09-26: revised
2017-06-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jacqueline Brendel and Marc Fischlin and Felix Günther and Christian Janson},
      title = {PRF-ODH: Relations, Instantiations, and Impossibility Results},
      howpublished = {Cryptology ePrint Archive, Paper 2017/517},
      year = {2017},
      doi = {10.1007/978-3-319-63697-9_22},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.