Cryptology ePrint Archive: Report 2014/637

Generic Hardness of the Multiple Discrete Logarithm Problem

Aaram Yun

Abstract: We study generic hardness of the multiple discrete logarithm problem, where the solver has to solve $n$ instances of the discrete logarithm problem simultaneously. There are known generic algorithms which perform $O(\sqrt{n p})$ group operations, where $p$ is the group order, but no generic lower bound was known other than the trivial bound. In this paper we prove the tight generic lower bound, showing that the previously known algorithms are asymptotically optimal. We establish the lower bound by studying hardness of a related computational problem which we call the search-by-hyperplane-queries problem, which may be of independent interest.

Category / Keywords: foundations / multiple discrete logarithm, search-by-hyperplane-queries, generic group model

Original Publication (in the same form): IACR-EUROCRYPT-2015

Date: received 18 Aug 2014, last revised 23 Jan 2015

Contact author: aaramyun at unist ac kr

Available format(s): PDF | BibTeX Citation

Note: Fixed typos, added some remarks, and relaxed the condition for the parameters

Version: 20150123:171042 (All versions of this report)

Short URL: ia.cr/2014/637

Discussion forum: Show discussion | Start new discussion