## CryptoDB

### Paper: A Classification of Computational Assumptions in the Algebraic Group Model

Authors: Balthazar Bauer , Inria, ENS, and PSL, France Georg Fuchsbauer , TU Wien, Austria Julian Loss , University of Maryland, USA DOI: https://doi.org/10.1007/978-3-030-56880-1_5 (login may be required) Search ePrint Search Google Slides CRYPTO 2020 We give a taxonomy of computational assumptions in the algebraic group model (AGM). We first analyze the Uber assumption family for bilinear groups defined by Boyen and then extend it in multiple ways to cover assumptions such as Gap Diffie-Hellman and the LRSW assumption. We show that in the AGM every member of these families reduces to the q-discrete logarithm (DL) problem, for some q that depends on the degrees of the polynomials defining the assumption. Using the meta-reduction technique, we then separate (q+1)-DL from q-DL, which thus 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, as we prove that they cannot be reduced to q-DL even in the AGM.
##### BibTeX
@inproceedings{crypto-2020-30454,
title={A Classification of Computational Assumptions in the Algebraic Group Model},
publisher={Springer-Verlag},
doi={https://doi.org/10.1007/978-3-030-56880-1_5},
author={Balthazar Bauer and Georg Fuchsbauer and Julian Loss},
year=2020
}