Paper 2023/1504

Algebraic Group Model with Oblivious Sampling

Helger Lipmaa, University of Tartu
Roberto Parisella, Simula UiB, Norway
Janno Siim, Simula UiB, Norway

In the algebraic group model (AGM), an adversary has to return with each group element a linear representation with respect to input group elements. In many groups, it is easy to sample group elements obliviously without knowing such linear representations. Since the AGM does not model this, it can be used to prove the security of spurious knowledge assumptions. We show several well-known zk-SNARKs use such assumptions. We propose AGM with oblivious sampling (AGMOS), an AGM variant where the adversary can access an oracle that allows sampling group elements obliviously from some distribution. We show that AGM and AGMOS are different by studying the family of ``total knowledge-of-exponent'' assumptions, showing that they are all secure in the AGM, but most are not secure in the AGMOS if the DL holds. We show an important separation in the case of the KZG commitment scheme. We show that many known AGM reductions go through also in the AGMOS, assuming a novel falsifiable assumption TOFR. We prove that TOFR is secure in a version of GGM with oblivious sampling.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2023
Admissible encodingalgebraic group modelelliptic-curve hashingFindRepKZG extractablityoblivious sampling
Contact author(s)
helger lipmaa @ gmail com
robertoparisella @ hotmail it
jannosiim @ gmail com
2023-10-03: approved
2023-10-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Helger Lipmaa and Roberto Parisella and Janno Siim},
      title = {Algebraic Group Model with Oblivious Sampling},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1504},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.