On Lifting AGM Security to the AGM with Oblivious Sampling
:12
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.