(2026-03) Hashing in Generic Groups; Completing the AGM-to-GGM Transfer
2026-03-06
The algebraic group model (AGM), formalized by Fuchsbauer, Kiltz, and Loss (Crypto 2018), has recently garnered significant attention. Notably, Katz, Zhang, and Zhou (Asiacrypt 2022) challenged a widely held belief: that hardness results proven in the AGM imply corresponding results in the generic group model (GGM). They showed that this implication fails under Shoup's GGM framework. In response, Jaeger and Mohan (Crypto 2024) proposed an alternative interpretation based on Maurer's GGM and proved that, under this interpretation, the implication indeed holds.
Many cryptographic applications analyzed in the AGM also rely on the random oracle model (ROM), which is largely absent from Jaeger and Mohan's framework. Because Maurer’s GGM and the ROM are inherently incomparable, Jaeger and Mohan's framework may not capture all AGM-based proofs. To bridge this gap and faithfully translate all known AGM-based proofs into the GGM setting, we make the following contributions:
- Limitations of JM's framework: Jaeger and Mohan’s framework captures only those primitives that can be instantiated within Maurer’s GGM. We identify a primitive—specifically, a public-key encryption scheme with short ciphertexts—whose security has been analyzed in the AGM, and establish a black-box separation between this primitive and Maurer’s GGM, even when combined with the ROM. This result provides concrete evidence that JM’s framework cannot encompass all known AGM-based proofs.
- Augmented framework: We propose an augmented framework that integrates Maurer’s GGM with a carefully constructed ROM, enabling inputs and outputs to incorporate group elements defined within Maurer’s model.
- Transferring all known AGM-based proofs to GGM setting: Building on our augmented framework, we prove the lifting lemma from the AGM to our model, demonstrating that hardness results in the AGM+ROM directly carry over to our setting, thereby justifying all known AGM-based proofs.