CROSSING Research Seminar: Beyond the Uber Assumption: Instantiating Generic Groups via PGGs

Organizer: Jacqueline Brendel, CROSSING

Abstract

The generic-group model (GGM) is a popular way of idealizing algebraic groups, and alongside the random-oracle (RO) and other idealized models, has been very successful in making the analyses of many cryptographic assumptions and protocols tractable. It is, however, well known that the GGM (like the other idealized models) 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.”

Accordingly, 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 notion of Universal Computational Extractors (UCEs) of Bellare, Hoang, and Keelveedhi (BHK, CRYPTO 2013) to a setting where the underlying ideal reference object is a generic group rather than a random oracle. At the same time, our notion also generalizes the Uber assumption family by removing the restriction that group exponents are polynomially induced.

Our definition is parameterized by a class of sources, which can be adjusted to tailor or expand the assumption. Finding an achievable class of sources turns out to be a delicate task: To rule out generic attacks, we introduce several restrictions that lead to the definition of masking sources, which suffice for all our applications. At the core of our contribution is the notion of algebraic unpredictability, which reinterprets the standard Schwartz-Zippel lemma as a restriction on sources, rather than a property that automatically holds for polynomials.

Our remaining results focus on applications of PGGs. We first show that PGGs are indeed a generalization of the Uber family of assumptions. We then present applications beyond Uber by proving that a classical and practical scheme, namely ElGamal, meets a number of advanced security properties previously achieved only by complex and inefficient schemes. We also show that PGGs imply UCEs for the class of split sources, which are sufficient for many applications as demonstrated by BHK.

Speaker Bio

Patrick Harasser is a PhD Student at the Cryptography and Complexity Theory Group at TU Darmstadt under the supervision of Prof. Marc Fischlin, and a member of the Collaborative Research Center 1119 CROSSING.

He holds a Master Degree in Mathematics from the Universities of Trento (Italy) and Tübingen (Germany). His research interests include sanitizable and blind signatures, sigma protocols, and idealized models.