Black-Box Separations for One-More (Static) CDH and Its Generalization

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.