Skip to main content

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

Author(s): Bartusek, James; Ma, Fermi; Zhandry, Mark

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr15g15
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBartusek, James-
dc.contributor.authorMa, Fermi-
dc.contributor.authorZhandry, Mark-
dc.date.accessioned2021-10-08T19:48:20Z-
dc.date.available2021-10-08T19:48:20Z-
dc.date.issued2019en_US
dc.identifier.citationBartusek, James, Fermi Ma, and Mark Zhandry. "The Distinction Between Fixed and Random Generators in Group-Based Assumptions." In Annual International Cryptology Conference (2019): pp. 801-830. doi:10.1007/978-3-030-26951-7_27en_US
dc.identifier.issn0302-9743-
dc.identifier.urihttps://www.cs.princeton.edu/~mzhandry/docs/papers/RandomGenerator.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr15g15-
dc.description.abstractThere 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).en_US
dc.format.extent801 - 830en_US
dc.language.isoen_USen_US
dc.relation.ispartofAnnual International Cryptology Conferenceen_US
dc.rightsAuthor's manuscripten_US
dc.titleThe Distinction Between Fixed and Random Generators in Group-Based Assumptionsen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1007/978-3-030-26951-7_27-
dc.identifier.eissn1611-3349-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
DistinctionFixedRandomGeneratorsGroupBasedAssumption.pdf629.33 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.