Paper 2017/343

Towards a Classification of Non-interactive Computational Assumptions in Cyclic Groups

Essam Ghadafi and Jens Groth

Abstract

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 Bilinar 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.