International Association for Cryptologic Research

International Association
for Cryptologic Research

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
Download:
DOI: https://doi.org/10.1007/978-3-030-56880-1_5 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
Abstract: 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.
Video from CRYPTO 2020
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
}