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(√np) 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.
|Title of host publication||Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings|
|Editors||Marc Fischlin, Elisabeth Oswald|
|Number of pages||20|
|State||Published - 2015|
|Event||34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015 - Sofia, Bulgaria|
Duration: 26 Apr 2015 → 30 Apr 2015
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015|
|Period||26/04/15 → 30/04/15|
Bibliographical notePublisher Copyright:
© International Association for Cryptologic Research 2015.
- Generic group model
- Multiple discrete logarithm