The Distinction Between Fixed and Random Generators in Group-Based Assumptions
The Distinction Between Fixed and Random Generators in Group-Based Assumptions
复制标题
DOI：
10.1007/978-3-030-26951-7_27
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
James Bartusek;Fermi Ma;Mark Zhandry
中科院分区：
文献类型：
--
作者：
James Bartusek;Fermi Ma;Mark Zhandry
令人惊讶的是，在DDH等基于群体的假设中，对generatorgin的确切作用几乎没有共识。有些作品认为群体描写是固定的，有些则认为是随机的。我们从多个角度研究了这一微妙的区别。在一般的群体模型中，我们证明了随机生成者DDH（分别为：CDH）是硬的，但固定的发电机DDH（分别。CDH）很容易。我们发现，如果生成器是随机的，那么带有预处理的离散对数和CDH问题（Corrigan-Gibbs and Kogan，Eurocrypt 2018）的看似紧的通用下界在次常数成功概率制度中并不紧。我们解决这个问题，通过证明严格的下界的随机生成器的变体;我们的结果形式化的直觉，使用随机生成器将降低预处理攻击的有效性。我们观察到，DDH类假设，其中指数是从低熵分布是特别敏感的固定与随机生成器的区别。最值得注意的是，我们发现Komargodski和Yogev（Komargodski and Yogev，Eurocrypt 2018）用于非延展点混淆的强幂DDH假设实际上是错误的，因为它需要一个固定的生成器。作为回应，我们制定了一个替代的固定发电机的假设，足以为一个新的建设的非可塑性点混淆，我们证明了假设持有的通用组模型。我们还给出了固定生成器，低熵DDH（Canetti，Crypto 1997）的安全性的通用群证明。
There is surprisingly little consensus on the precise role of the generatorgin group-based assumptions such as DDH. Some works considergto 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 factfalseprecisely 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).