CryptoDB
A Classification of Computational Assumptions in the Algebraic Group Model
| Authors: |
|
|---|---|
| Download: |
|
| 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={10.1007/978-3-030-56880-1_5},
author={Balthazar Bauer and Georg Fuchsbauer and Julian Loss},
year=2020
}