Paper 2023/1601

The Uber-Knowledge Assumption: A Bridge to the AGM

Balthazar Bauer, Université de Versailles Saint-Quentin-en-Yvelines, France
Pooya Farshim, Input Output Global, Switzerland, Durham University, UK
Patrick Harasser, Technische Universität Darmstadt, Germany
Markulf Kohlweiss, Input Output Global, UK, University of Edinburgh, UK

The generic-group model (GGM) and the algebraic-group model (AGM) have been exceptionally successful in proving the security of many classical and modern cryptosystems. These models, however, come with standard-model uninstantiability results, raising the question whether the schemes analyzed under them can be based on firmer standard-model footing. We formulate the uber-knowledge (UK) assumption, a standard-model assumption that naturally extends the uber-assumption family to knowledge-type problems. We justify the soundness of the UK assumption in both the bilinear GGM and the bilinear AGM. Along the way we extend these models to account for hashing into groups, an adversarial capability that is available in many concrete groups---In contrast to standard assumptions, hashing may affect the validity of knowledge assumptions. These results, in turn, enable a modular approach to security in the GGM and the AGM. As example applications, we use the UK assumption to prove knowledge soundness of Groth16 and of KZG polynomial commitments in the standard model, where for the former we reuse the existing proof in the AGM without hashing.

Note: Corrected claims that the uber-knowledge assumption implies several other knowledge assumptions, and provided formal proofs.

Available format(s)
Publication info
Knowledge assumptionStandard modelGeneric-group modelAlgebraic-group modelGroth16KZG commitment
Contact author(s)
balthazar bauer @ ens fr
pooya farshim @ gmail com
patrick harasser @ tu-darmstadt de
mkohlwei @ ed ac uk
2024-03-13: last of 2 revisions
2023-10-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Balthazar Bauer and Pooya Farshim and Patrick Harasser and Markulf Kohlweiss},
      title = {The Uber-Knowledge Assumption: A Bridge to the {AGM}},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1601},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.