The Distinction Between Fixed and Random Generators in Group-Based Assumptions

James Bartusek, Fermi Ma, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

There is surprisingly little consensus on the precise role of the generator g in group-based assumptions such as DDH. Some works consider g to be a fixed part of the group description, while others take it to be random. We study this subtle distinction from a number of angles. In the generic group model, we demonstrate the plausibility of groups in which random-generator DDH (resp. CDH) is hard but fixed-generator DDH (resp. CDH) is easy. We observe that such groups have interesting cryptographic applications.We find that seemingly tight generic lower bounds for the Discrete-Log and CDH problems with preprocessing (Corrigan-Gibbs and Kogan, Eurocrypt 2018) are not tight in the sub-constant success probability regime if the generator is random. We resolve this by proving tight lower bounds for the random generator variants; our results formalize the intuition that using a random generator will reduce the effectiveness of preprocessing attacks.We observe that DDH-like assumptions in which exponents are drawn from low-entropy distributions are particularly sensitive to the fixed- vs. random-generator distinction. Most notably, we discover that the Strong Power DDH assumption of Komargodski and Yogev (Komargodski and Yogev, Eurocrypt 2018) used for non-malleable point obfuscation is in fact false precisely because it requires a fixed generator. In response, we formulate an alternative fixed-generator assumption that suffices for a new construction of non-malleable point obfuscation, and we prove the assumption holds in the generic group model. We also give a generic group proof for the security of fixed-generator, low-entropy DDH (Canetti, Crypto 1997).

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings
EditorsAlexandra Boldyreva, Daniele Micciancio
PublisherSpringer Verlag
Pages801-830
Number of pages30
ISBN (Print)9783030269500
DOIs
StatePublished - 2019
Event39th Annual International Cryptology Conference, CRYPTO 2019 - Santa Barbara, United States
Duration: Aug 18 2019Aug 22 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11693 LNCS

Conference

Conference39th Annual International Cryptology Conference, CRYPTO 2019
Country/TerritoryUnited States
CitySanta Barbara
Period8/18/198/22/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'The Distinction Between Fixed and Random Generators in Group-Based Assumptions'. Together they form a unique fingerprint.

Cite this