You are looking at a specific version 20150123:171042 of this paper. See the latest version.

Paper 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.

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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in EUROCRYPT 2015
Keywords
multiple discrete logarithmsearch-by-hyperplane-queriesgeneric group model
Contact author(s)
aaramyun @ unist ac kr
History
2015-01-23: last of 4 revisions
2014-08-21: received
See all versions
Short URL
https://ia.cr/2014/637
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.