[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.

BibTeX

Copy

@Inproceedings{C:FucKilLos18,
  author = {Georg Fuchsbauer and Eike Kiltz and Julian Loss},
  title = {The Algebraic Group Model and its Applications},
  pages = {33--62},
  editor = {Hovav Shacham and Alexandra Boldyreva},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2018, Part~II},
  volume = {10992},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~19--23},
  publisher = {Springer, Cham, Switzerland},
  year = {2018},
  doi = {10.1007/978-3-319-96881-0_2},
}