Paper 2017/620

The Algebraic Group Model and its Applications

Georg Fuchsbauer, Eike Kiltz, and Julian Loss

Abstract

One of the most important tools for assessing hardness assumptions in cryptography is the Generic Group Model (GGM). Over the past two decades, numerous assumptions 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. 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 '16), which is the most efficient SNARK for which only a proof in the GGM was known. 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2018
Keywords
discrete logarithm problem
Contact author(s)
julian loss @ rub de
History
2019-04-15: last of 6 revisions
2017-06-27: received
See all versions
Short URL
https://ia.cr/2017/620
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/620,
      author = {Georg Fuchsbauer and Eike Kiltz and Julian Loss},
      title = {The Algebraic Group Model and its Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2017/620},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/620}},
      url = {https://eprint.iacr.org/2017/620}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.