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
-
CC BY
BibTeX
@misc{cryptoeprint:2014/637,
author = {Aaram Yun},
title = {Generic Hardness of the Multiple Discrete Logarithm Problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2014/637},
year = {2014},
url = {https://eprint.iacr.org/2014/637}
}
