Paper 2022/1502

Beyond Uber: Instantiating Generic Groups via PGGs

Balthazar Bauer, IRIF, CNRS, France
Pooya Farshim, IOHK, Durham University, UK
Patrick Harasser, Technische Universität Darmstadt, Germany
Adam O'Neill, University of Massachusetts Amherst, USA

The generic-group model (GGM) has been very successful in making the analyses of many cryptographic assumptions and protocols tractable. It is, however, well known that the GGM is “uninstantiable,” i.e., there are protocols secure in the GGM that are insecure when using any real-world group. This motivates the study of standard-model notions formalizing that a real-world group in some sense “looks generic.” We introduce a standard-model definition called pseudo-generic group (PGG), where we require exponentiations with base an (initially) unknown group generator to result in random-looking group elements. In essence, our framework delicately lifts the influential notion of Universal Computational Extractors of Bellare, Hoang, and Keelveedhi (BHK, CRYPTO 2013) to a setting where the underlying ideal reference object is a generic group. The definition we obtain simultaneously generalizes the Uber assumption family, as group exponents no longer need to be polynomially induced. At the core of our definitional contribution is a new notion of algebraic unpredictability, which reinterprets the standard Schwartz–Zippel lemma as a restriction on sources. We prove the soundness of our definition in the GGM with auxiliary-input (AI-GGM). Our remaining results focus on applications of PGGs. We first show that PGGs are indeed a generalization of Uber. We then present a number of applications in settings where exponents are not polynomially induced. In particular we prove that simple variants of ElGamal meet several advanced security goals previously achieved only by complex and inefficient schemes. We also show that PGGs imply UCEs for split sources, which in turn are sufficient in several applications. As corollaries of our AI-GGM feasibility, we obtain the security of all these applications in the presence of preprocessing attacks. Some of our implications utilize a novel type of hash function, which we call linear-dependence destroyers (LDDs) and use to convert standard into algebraic unpredictability. We give an LDD for low-degree sources, and establish their plausibility for all sources by showing, via a compression argument, that random functions meet this definition.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2022
Generic-group model Uber assumption UCE Deterministic PKE KDM and RKA security
Contact author(s)
balthazar bauer @ ens fr
pooya farshim @ gmail com
patrick harasser @ tu-darmstadt de
adamo @ cs umass edu
2022-11-06: approved
2022-11-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Balthazar Bauer and Pooya Farshim and Patrick Harasser and Adam O'Neill},
      title = {Beyond Uber: Instantiating Generic Groups via {PGGs}},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1502},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.