A Classification of Computational Assumptions in the Algebraic Group Model

Balthazar Bauer, Georg Fuchsbauer, and Julian Loss

Abstract

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.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2020
Keywords
Algebraic Group ModelUber AssumptionPairing-Based Cryptography
Contact author(s)
balthazar bauer @ ens fr
History
Short URL
https://ia.cr/2020/859

CC BY

BibTeX

@misc{cryptoeprint:2020/859,
author = {Balthazar Bauer and Georg Fuchsbauer and Julian Loss},
title = {A Classification of Computational Assumptions in the Algebraic Group Model},
howpublished = {Cryptology ePrint Archive, Paper 2020/859},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/859}},
url = {https://eprint.iacr.org/2020/859}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.