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

Ghadafi, Essam; Groth, Jens

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

• Presentation Conference Type: Conference Paper (published)
• 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
• Publicly Available 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
• DOI: https://doi.org/10.1007/978-3-319-70697-9_3
• Keywords: non-interactive assumptions, computational assumptions, target assumptions, prime-order groups, bilinear groups
• Public URL: https://uwe-repository.worktribe.com/output/877206
• Publisher URL: https://doi.org/10.1007/978-3-319-70697-9_3
• Contract Date: May 4, 2017