A Classification of Computational Assumptions in the Algebraic Group Model
| Autor: | Balthazar Bauer, Georg Fuchsbauer, Julian Loss |
|---|---|
| Přispěvatelé: | Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Institute of Applied Physics [Vienna] (TU Wien), Vienna University of Technology (TU Wien), University of Maryland [College Park], University of Maryland System, This work is funded in part by the MSR–Inria Joint Centre. The second author is supported by the Vienna Science and Technology Fund (WWTF) through project VRG18-002., Daniele Micciancio, Thomas Ristenpart, Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Logarithm
Bilinear interpolation 0102 computer and information sciences 02 engineering and technology 01 natural sciences Algebra Pairing-based cryptography Uber Assumption Algebraic Group Model 010201 computation theory & mathematics Algebraic group Taxonomy (general) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing [INFO]Computer Science [cs] Pairing-Based Cryptography Mathematics |
| Zdroj: | Advances in Cryptology – CRYPTO 2020. CRYPTO 2020-40th Annual International Cryptology Conference CRYPTO 2020-40th Annual International Cryptology Conference, Aug 2020, Santa Barbara / Virtual, United States. pp.121-151, ⟨10.1007/978-3-030-56880-1_5⟩ Advances in Cryptology – CRYPTO 2020 ISBN: 9783030568795 CRYPTO (2) |
| DOI: | 10.1007/978-3-030-56880-1_5⟩ |
| Popis: | International audience; a 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|