Skip to Main content Skip to Navigation
Conference papers

The Algebraic Group Model and its Applications

Georg Fuchsbauer 1 Eike Kiltz 2 Julian Loss 2 
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique - ENS Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : One of the most important and successful tools for assessing hardness assumptions in cryptography is the Generic Group Model (GGM). Over the past two decades, numerous assumptions and protocols have been analyzed within this model. While a proof in the GGM can certainly provide some measure of confidence in an assumption, its scope is rather limited since it does not capture group-specific algorithms that make use of the representation of the group. To overcome this limitation, we propose the Algebraic Group Model (AGM), a model that lies in between the Standard Model and the GGM. It is the first restricted model of computation covering group-specific algorithms yet allowing to derive simple and meaningful security statements. To prove its usefulness, we show that several important assumptions, among them the Computational Diffie-Hellman, the Strong Diffie-Hellman, and the interactive LRSW assumptions, are equivalent to the Discrete Logarithm (DLog) assumption in the AGM. On the more practical side, we prove tight security reductions for two important schemes in the AGM to DLog or a variant thereof: the BLS signature scheme and Groth’s zero-knowledge SNARK (EUROCRYPT 2016), which is the most efficient SNARK for which only a proof in the GGM was known. Our proofs are quite simple and therefore less prone to subtle errors than those in the GGM. Moreover, in combination with known lower bounds on the Discrete Logarithm assumption in the GGM, our results can be used to derive lower bounds for all the above-mentioned results in the GGM.
Document type :
Conference papers
Complete list of metadata
Contributor : Georg Fuchsbauer Connect in order to contact the contributor
Submitted on : Friday, September 7, 2018 - 10:07:40 AM
Last modification on : Wednesday, June 8, 2022 - 12:50:03 PM




Georg Fuchsbauer, Eike Kiltz, Julian Loss. The Algebraic Group Model and its Applications. CRYPTO 2018 - 38th Annual International Cryptology Conference, Aug 2018, Santa Barbara, United States. pp.33-62, ⟨10.1007/978-3-319-96881-0_2⟩. ⟨hal-01870015⟩



Record views