### Deja Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions

Melissa Chase, Mary Maller, and Sarah Meiklejohn

##### Abstract

In this paper, we demonstrate that various cryptographic constructions--including ones for broadcast, attribute-based, and hierarchical identity-based encryption--can rely for security on only the static subgroup hiding assumption when instantiated in composite-order bilinear groups, as opposed to the dynamic q-type assumptions on which their security previously was based. This specific goal is accomplished by more generally extending the recent Deja Q framework (Chase and Meiklejohn, Eurocrypt 2014) in two main directions. First, by teasing out common properties of existing reductions, we expand the q-type assumptions that can be covered by the framework; i.e., we demonstrate broader classes of assumptions that can be reduced to subgroup hiding. Second, while the original framework applied only to asymmetric composite-order bilinear groups, we provide a reduction to subgroup hiding that works in symmetric (as well as asymmetric) composite-order groups. As a bonus, our new reduction achieves a tightness of log(q) rather than q.

Available format(s)
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2016
Keywords
assumptionsreductions
Contact author(s)
s meiklejohn @ ucl ac uk
History
Short URL
https://ia.cr/2016/840

CC BY

BibTeX

@misc{cryptoeprint:2016/840,
author = {Melissa Chase and Mary Maller and Sarah Meiklejohn},
title = {Deja Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions},
howpublished = {Cryptology ePrint Archive, Paper 2016/840},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/840}},
url = {https://eprint.iacr.org/2016/840}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.