Paper 2011/280

DDH-like Assumptions Based on Extension Rings

Ronald Cramer, Ivan Damgaard, Eike Kiltz, Sarah Zakarias, and Angela Zottarel


We introduce and study a new type of DDH-like assumptions based on groups of prime order q. Whereas standard DDH is based on encoding elements of F_{q} ``in the exponent'' of elements in the group, we ask what happens if instead we put in the exponent elements of the extension ring R_f= \F_{q}[X]/(f) where f can be any degree-d polynomial. We show that solving the decision problem that follows naturally reduces to the case where f is irreducible. This variant is called the d-DDH problem, where 1-DDH is standard DDH. Essentially any known cryptographic construction based on DDH can be immediately generalized to use instead d-DDH, and we show in the generic group model that d-DDH is harder than DDH. This means that virtually any application of DDH can now be realized with the same (amortized) efficiency, but under a potentially weaker assumption. On the negative side, we also show that d-DDH, just like DDH, is easy in bilinear groups. This motivates our suggestion of a different type of assumption, the d-vector DDH problems (VDDH), which are based on f(X)= X^d, but with a twist to avoid the problems with reducible polynomials. We show in the generic group model that VDDH is hard in bilinear groups and that in fact the problems become harder with increasing d and hence form an infinite hierarchy. We show that hardness of VDDH implies CCA-secure encryption, efficient Naor-Reingold style pseudorandom functions, and auxiliary input secure encryption, a strong form of leakage resilience. This can be seen as an alternative to the known family of k-linear assumptions.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
DDHPublic Key EncryptionPRFLeakage Resilient Encryption
Contact author(s)
angela @ cs au dk
2012-03-07: last of 4 revisions
2011-05-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ronald Cramer and Ivan Damgaard and Eike Kiltz and Sarah Zakarias and Angela Zottarel},
      title = {DDH-like Assumptions Based on Extension Rings},
      howpublished = {Cryptology ePrint Archive, Paper 2011/280},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.