Skip to main content

Research Repository

Advanced Search

Towards a classification of non-interactive computational assumptions in cyclic groups

Ghadafi, Essam; Groth, Jens


Essam Ghadafi
Senior Lecturer in Computer Science

Jens Groth


We study non-interactive computational intractability assumptions in prime-order cyclic groups. We focus on the broad class of computational assumptions, which we call target assumptions, where the adversary's goal is to compute a concrete group element and investigate the structure of this class.

Our analysis identifies two families of intractability assumptions, the q-Generalized Diffie-Hellman Exponent assumptions and the q-Simple Fractional assumptions that imply all other target assumptions. These two assumptions therefore serve as Uber assumptions that can underpin all the target assumptions where the adversary has to compute specific group elements. We also study the internal hierarchy among members of these two assumption families. We provide heuristic evidence that both families are necessary to cover the full class of target assumptions, and we show that the lowest level in the q-GDHE hierarchy (the 1-GDHE assumption) is equivalent to the computational Diffie-Hellman assumption.

We generalize our results to the bilinear group setting. For the base groups our results translate nicely and a similar structure of non-interactive computational assumptions emerges. We also identify Uber assumptions in the target group but this requires replacing the q-GDHE assumption with a more complicated assumption, which we call the Bilinear Gap Assumption.

Our analysis can assist both cryptanalysts and cryptographers. For cryptanalysts, we propose the q-GDHE and the q-SDH assumptions are the most natural and important targets for cryptanalysis in prime-order groups. For cryptographers, we believe our classification can aid the choice of assumptions underpinning cryptographic schemes and be used as a guide to minimize the overall attack surface that different assumptions expose.


Ghadafi, E., & Groth, J. (2017). Towards a classification of non-interactive computational assumptions in cyclic groups. In Advances in Cryptology – ASIACRYPT 2017 (66-96).

Conference Name International Conference on the Theory and Application of Cryptology and Information Security
Start Date Dec 3, 2017
End Date Dec 7, 2017
Acceptance Date Dec 3, 2017
Online Publication Date Nov 18, 2017
Publication Date Nov 18, 2017
Deposit Date May 4, 2017
Publisher Springer Verlag
Peer Reviewed Not Peer Reviewed
Volume 10625
Pages 66-96
Series Title Lecture Notes in Computer Science
Series ISSN 0302-9743
Book Title Advances in Cryptology – ASIACRYPT 2017
ISBN 9783319706962
Keywords non-interactive assumptions, computational assumptions, target assumptions, prime-order groups, bilinear groups
Public URL
Publisher URL


You might also like

Downloadable Citations