[FKL18] The Algebraic Group Model and its Applications

Authors: Fuchsbauer, Georg; Kiltz, Eike; Loss, Julian | Venue: CRYPTO 2018 | Source

Abstract

This paper introduces the Algebraic Group Model (AGM), a model of computation that lies strictly between the standard model and the generic group model. An adversary in the AGM is algebraic: whenever it outputs a group element, it must simultaneously provide an explicit linear representation of that element over the group elements it has received. The authors show that several important assumptions — CDH, Strong DH, and the interactive LRSW assumption — are equivalent to the discrete logarithm assumption in the AGM, and prove tight security reductions for BLS signatures and Groth’s zero-knowledge SNARK. Combined with GGM lower bounds, these yield tight lower bounds for various group-based constructions.