InfoSec Seminar: Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions

Speaker: Mary Maller

Date/Time: 09-Nov-2016, 16:30 UTC

Venue: Roberts 309



In cryptography, most cryptographic constructions rely on some assumption for their security guarantees. In this speech I plan to highlight how in a recent paper with Chase and Meiklejohn, we showed how to base the security of various cryptographic constructions of more secure assumptions.  In our paper, we demonstrate that various cryptographic constructions 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.  


Mary Maller is a PhD candidate in the area of cryptography, working under the supervision of Dr Sarah Meiklejohn and Professor Jens Groth. Her PhD is supported by Microsoft Research. Mary has been part of the Information Security Group at UCL since November 2015. Currently, her research focusses on q-type assumptions and zero knowledge proofs.

Add to Calendar

This page was last modified on 27 Mar 2014.