[KZ22] An Analysis of the Algebraic Group Model

Authors: Katz, Jonathan; Zhang, Cong | Venue: ASIACRYPT 2022 | Source

Abstract

The algebraic group model (AGM), formalized by Fuchsbauer, Kiltz, and Loss, was claimed to be a weaker model than the generic group model (GGM) in the sense that hardness for algebraic algorithms implies hardness for generic algorithms, and generic reductions in the AGM lift to the GGM. This paper challenges those claims: the authors identify settings where hardness in the AGM does not imply hardness in the GGM, and where a generic reduction in the AGM does not yield a corresponding reduction in the GGM. The results clarify the relationship between the two models and show that the hierarchy assumed in prior work is not generally valid.