Paper 2026/201

On Lifting AGM Security to the AGM with Oblivious Sampling

Juraj Belohorec, Czech Academy of Sciences, Institute of Mathematics, Charles University
Pavel Hubáček, Czech Academy of Sciences, Institute of Mathematics, Charles University
Dominik Stejskal, Charles University
Abstract

The Algebraic Group Model (AGM) is widely used to prove the security of cryptographic schemes involving groups and pairings. It requires adversaries to explain how their output group elements are obtained from the elements they have received. The AGM with Oblivious Sampling (AGMOS), introduced by Lipmaa, Parisella, and Siim (TCC 2023), additionally allows adversaries to sample group elements without learning their discrete logarithms. This models capabilities such as hashing to a group, but complicates security proofs: security in the AGM does not always imply security in the AGMOS. We give a framework for transferring AGM security proofs to the AGMOS for a broad class of pairing-based security games. Our results separate the existing AGM argument from the additional reasoning needed to handle obliviously sampled elements. Under the Find Polynomial Representation (FPR) and Tensor Oracle Find Representation (TOFR) assumptions, this additional reasoning can be handled by general reductions. Games with further requirements, such as extractability, also require a lifting condition that ensures these requirements are preserved. We first establish a lifting theorem for non-interactive games and apply it to KZG extractability, the multivariate Adaptive Rational Strong Diffie-Hellman assumption, and the special-soundness of the Polymath SNARK. We then extend the framework to interactive games that use random oracles and other oracles that depend on the trapdoor. In the interactive setting, we apply the theorem to the existential unforgeability of BLS signatures and strong unforgeability of BBS signatures under FPR/PDL and TOFR assumptions. For BLS, we also provide an AGM security proof for Type-3 pairings, adapting the original Type-1 analysis. Our framework allows existing AGM proofs to be reused in the AGMOS. To apply the framework, it is enough to check its requirements, including oracle simulation and, where needed, the lifting condition, without repeating the full security proof.

Note: Major revision: we extend the lifting theorem to interactive security games with random oracles and simulatable trapdoor-dependent oracles, and apply it to the EUF-CMA security of BLS (with a new AGM proof for Type-3 pairings) and the SUF-CMA security of BBS. We also add the special-soundness of Polymath as a non-interactive application, show that the lifting condition is needed only for games with an additional structural check such as extractability, and revise the presentation throughout.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Algebraic Group ModelOblivious SamplingAGMAGMOSLifting Security Proofs
Contact author(s)
belohorec @ math cas cz
hubacek @ math cas cz
History
2026-10-27: revised
2026-02-08: received
See all versions
Short URL
https://ia.cr/2026/201
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/201,
      author = {Juraj Belohorec and Pavel Hubáček and Dominik Stejskal},
      title = {On Lifting {AGM} Security to the {AGM} with Oblivious Sampling},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/201},
      year = {2026},
      url = {https://eprint.iacr.org/2026/201}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.