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.
Category / Keywords: foundations / bilinear groups Original Publication (with major differences): IACR-EUROCRYPT-2014 Date: received 22 Jul 2014 Contact author: smeiklej at cs ucsd edu Available format(s): PDF | BibTeX Citation Version: 20140724:124921 (All versions of this report) Short URL: ia.cr/2014/570 Discussion forum: Show discussion | Start new discussion