###
**Bauer, Balthazar ; Farshim, Pooya ; Harasser, Patrick ; O'Neill, Adam** (2022):

*Beyond Uber: Instantiating Generic Groups via PGGs.*

In: Lecture Notes in Computer Science, 13749, In: Theory of Cryptography, pp. 212-242,

Springer, 20th Theory of Cryptography Conference (TCC 2022), Chicago, USA, 07.-10.11.2022, ISBN 978-3-031-22367-9,

DOI: 10.1007/978-3-031-22368-6_8,

[Conference or Workshop Item]

## Abstract

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.

Item Type: | Conference or Workshop Item |
---|---|

Erschienen: | 2022 |

Creators: | Bauer, Balthazar ; Farshim, Pooya ; Harasser, Patrick ; O'Neill, Adam |

Title: | Beyond Uber: Instantiating Generic Groups via PGGs |

Language: | English |

Abstract: | 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. |

Book Title: | Theory of Cryptography |

Series: | Lecture Notes in Computer Science |

Series Volume: | 13749 |

Publisher: | Springer |

ISBN: | 978-3-031-22367-9 |

Uncontrolled Keywords: | Primitives, P2 |

Divisions: | 20 Department of Computer Science 20 Department of Computer Science > Cryptography and Complexity Theory DFG-Collaborative Research Centres (incl. Transregio) DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1119: CROSSING – Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments |

Event Title: | 20th Theory of Cryptography Conference (TCC 2022) |

Event Location: | Chicago, USA |

Event Dates: | 07.-10.11.2022 |

Date Deposited: | 21 Mar 2023 09:06 |

DOI: | 10.1007/978-3-031-22368-6_8 |

URL / URN: | https://link.springer.com/chapter/10.1007/978-3-031-22368-6_... |

PPN: | |

Corresponding Links: | |

Export: | |

Suche nach Titel in: | TUfind oder in Google |

Send an inquiry |

**Options (only for editors)**

Show editorial Details |