A Classification of Computational Assumptions in the Algebraic Group Model

Une classification des hypothèses calculatoire dans le modèle du groupe algébrique

Balthazar Bauer (1, 2, 3, 4, 5) , Georg Fuchsbauer (6) , Julian Loss (7)

1 DI-ENS - Département d'informatique - ENS Paris
2 CNRS - Centre National de la Recherche Scientifique
3 PSL - Université Paris Sciences et Lettres
4 ENS-PSL - École normale supérieure - Paris
5 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
6 TU Wien - Institute of Applied Physics [Vienna]
7 University of Maryland [College Park]

a We give a taxonomy of computational assumptions in the algebraic group model (AGM). We first analyze Boyen's Uber assumption family for bilinear groups and then extend it in several ways to cover assumptions as diverse as Gap Diffie-Hellman and LRSW. We show that in the AGM every member of these families is implied by the q-discrete logarithm (DL) assumption, for some q that depends on the degrees of the polynomials defining the Uber assumption. Using the meta-reduction technique, we then separate (q + 1)-DL from q-DL, which yields a classification of all members of the extended Uber-assumption families. We finally show that there are strong assumptions, such as one-more DL, that provably fall outside our classification, by proving that they cannot be reduced from q-DL even in the AGM.

Mots clés: Algebraic Group Model; Uber Assumption; Pairing-Based Cryptography

Domaines: Informatique [cs]

Balthazar Bauer, Georg Fuchsbauer, Julian Loss. A Classification of Computational Assumptions in the Algebraic Group Model. CRYPTO 2020 - 40th Annual International Cryptology Conference, Aug 2020, Santa Barbara / Virtual, United States. pp.121-151, ⟨10.1007/978-3-030-56880-1_5⟩. ⟨hal-02968271⟩