Beyond Uber: Instantiating Generic Groups via PGGs

The Generic Group Model (GGM) has been used to make analyses of many cryptographic assumptions and protocols. However, it is well known that the GGM should be used with caution, as there are protocols that are secure in this model that are not secure in practice.

This motivates the study of standard model notions formalizing the fact that a real-world group "looks generic" in some sense.

We introduce a standard model definition called pseudo-generic group (PGG). The definition we obtain generalizes the Uber assumptions. Our other results focus on applications of PGGs. We first show that PGGs are a generalization of Uber, and then present a number of applications.

Some of our implications use a new type of hash function, which we call linear dependency destroyers (LDDs) and which we use to relate PGGs to UCE hash functions (which are the analog of PGGs for hash functions).