An Analysis of the Algebraic Group Model

Jonathan Katz; Cong Zhang; Hong-Sheng Zhou

Paper 2022/210

An Analysis of the Algebraic Group Model

Jonathan Katz, Cong Zhang, and Hong-Sheng Zhou

Abstract

The algebraic group model (AGM), proposed by Fuchsbauer, Kiltz and Loss (CRYPTO 2018) has received huge attention. One of the most appealing properties of the AGM, is that, the hardness of security games in the generic group model (GGM) can be transferred via a generic reduction in the AGM. More concretely, for any two security games, G and H, if there exists a generic reduction from H to G in the AGM, and H is hard in the GGM, then G is also hard in the GGM. In this work, we analyze the relationship between the AGM and Shoup’s GGM (Eurocrypt 1997) and give evidence that: • hardness of security games in Shoup’s GGM cannot be transferred via a generic reduction in the AGM; • the AGM and Shoup’s GGM are incomparable.

Note: We add a subsection 1.3 on page 5, providing comparison to a concurrent and independent result by Mark Zhandry (eprint.iacr.org/2022/226), as well as presenting additional discussions.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. Minor revision.
Contact author(s): hszhou @ vcu edu
congresearch @ gmail com
History: 2022-05-05: last of 2 revisions; 2022-02-22: received; See all versions
Short URL: https://ia.cr/2022/210
License: CC BY

BibTeX

@misc{cryptoeprint:2022/210,
      author = {Jonathan Katz and Cong Zhang and Hong-Sheng Zhou},
      title = {An Analysis of the Algebraic Group Model},
      howpublished = {Cryptology ePrint Archive, Paper 2022/210},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/210}},
      url = {https://eprint.iacr.org/2022/210}
}