Paper 2014/570

Deja Q: Using Dual Systems to Revisit q-Type Assumptions

Melissa Chase and Sarah Meiklejohn


After more than a decade of usage, bilinear groups have established their place in the cryptographic canon by enabling the construction of many advanced cryptographic primitives. Unfortunately, this explosion in functionality has been accompanied by an analogous growth in the complexity of the assumptions used to prove security. Many of these assumptions have been gathered under the umbrella of the "uber-assumption," yet certain classes of these assumptions -- namely, q-type assumptions -- are stronger and require larger parameter sizes than their static counterparts. In this paper, we show that in certain groups, many classes of q-type assumptions are in fact implied by subgroup hiding (a well-established, static assumption). Our main tool in this endeavor is the dual-system technique, as introduced by Waters in 2009. As a case study, we first show that in composite-order groups, we can prove the security of the Dodis-Yampolskiy PRF based solely on subgroup hiding and allow for a domain of arbitrary size (the original proof only allowed a polynomially-sized domain). We then turn our attention to classes of q-type assumptions and show that they are implied -- when instantiated in appropriate groups -- solely by subgroup hiding. These classes are quite general and include assumptions such as q-SDH. Concretely, our result implies that every construction relying on such assumptions for security (e.g., Boneh-Boyen signatures) can, when instantiated in appropriate composite-order bilinear groups, be proved secure under subgroup hiding instead.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2014
bilinear groups
Contact author(s)
smeiklej @ cs ucsd edu
2014-07-24: received
Short URL
Creative Commons Attribution


      author = {Melissa Chase and Sarah Meiklejohn},
      title = {Deja Q: Using Dual Systems to Revisit q-Type Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2014/570},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.