Paper 2012/653

How powerful are the DDH hard groups?

Periklis A. Papakonstantinou, Charles W. Rackoff, and Yevgeniy Vahlis


The question whether Identity-Based Encryption (IBE) can be based on the Decisional Diffie-Hellman (DDH) assumption is one of the most prominent questions in Cryptography related to DDH. We study limitations on the use of the DDH assumption in cryptographic constructions, and show that it is impossible to construct a secure Identity-Based Encryption system using, in a black box way, only the DDH (or similar) assumption about a group. Our impossibility result is set in the generic groups model, where we describe an attack on any IBE construction that relies on oracle access to the group operation of randomly labelled group elements -- a model that formalizes naturally DDH hardness. The vast majority of existing separation results typically give separation from general primitives, whereas we separate a primitive from a class of number theoretic hardness assumptions. Accordingly, we face challenges in creating an attack algorithm that will work against constructions which leverage the underlying algebraic structure of the group. In fact, we know that this algebraic structure is powerful enough to provide generic constructions for several powerful primitives including oblivious transfer and chosen ciphertext secure public-key cryptosystems (note that an IBE generalizes such systems). Technically, we explore statistical properties of the group algebra associated with a DDH oracle, which can be of independent interest.

Available format(s)
Publication info
Published elsewhere. (first part of the result appears in the PhD thesis of P.A.Papakonstantinou (March 2010) )
Generic GroupsDDHIBEblack-box separation
Contact author(s)
ppapakons @ gmail com
2012-11-21: received
Short URL
Creative Commons Attribution


      author = {Periklis A.  Papakonstantinou and Charles W.  Rackoff and Yevgeniy Vahlis},
      title = {How powerful are the DDH hard groups?},
      howpublished = {Cryptology ePrint Archive, Paper 2012/653},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.