Welcome to the resource topic for 2020/859
Title:
A Classification of Computational Assumptions in the Algebraic Group Model
Authors: Balthazar Bauer, Georg Fuchsbauer, 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.
ePrint: https://eprint.iacr.org/2020/859
Talk: https://www.youtube.com/watch?v=oIGvC2pkEaQ
Slides: https://iacr.org/submit/files/slides/2020/crypto/crypto2020/348/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .