2014 | OriginalPaper | Buchkapitel
Black-Box Separations for One-More (Static) CDH and Its Generalization
verfasst von : Jiang Zhang, Zhenfeng Zhang, Yu Chen, Yanfei Guo, Zongyang Zhang
Erschienen in: Advances in Cryptology – ASIACRYPT 2014
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
As one-more problems are widely used in both proving and analyzing the security of various cryptographic schemes, it is of fundamental importance to investigate the hardness of the one-more problems themselves. Bresson
et al.
(CT-RSA ’08) first showed that it is difficult to rely the hardness of some one-more problems on the hardness of their “regular” ones. Pass (STOC ’11) then gave a stronger black-box separation showing that the hardness of some one-more problems cannot be based on standard assumptions using black-box reductions. However, since previous works only deal with one-more problems whose solution can be efficiently checked, the relation between the hardness of the one-more (static) CDH problem over non-bilinear groups and other hard problems is still unclear. In this work, we give the first impossibility results showing that black-box reductions cannot be used to base the hardness of the one-more (static) CDH problem (over groups where the DDH problem is still hard) on any standard hardness assumption. Furthermore, we also extend the impossibility results to a class of generalized “one-more” problems, which not only subsume/strengthen many existing separations for traditional one-more problems, but also give new separations for many other interesting “one-more” problems.