Our lower bound, which is tight up to logarithmic factors, uses a synthesis of incompressibility techniques and classic methods for generic-group lower bounds. We apply our techniques to prove related lower bounds for the CDH, DDH, and multiple-discrete-log problems.
Finally, we demonstrate two new generic preprocessing attacks: one for the multiple-discrete-log problem and one for certain decisional-type problems in groups. This latter result demonstrates that, for generic algorithms with preprocessing, distinguishing tuples of the form $(g, g^x, g^{(x^2)})$ from random is much easier than the discrete-log problem.
Category / Keywords: public-key cryptography / discrete logarithm problem, generic-group model Original Publication (with minor differences): IACR-EUROCRYPT-2018 Date: received 16 Nov 2017, last revised 11 Jul 2019 Contact author: henrycg at cs stanford edu Available format(s): PDF | BibTeX Citation Note: This version corrects a reference in Section 3. Version: 20190711:211213 (All versions of this report) Short URL: ia.cr/2017/1113