Generic hardness of the multiple discrete logarithm problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

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(√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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings
EditorsMarc Fischlin, Elisabeth Oswald
PublisherSpringer Verlag
Pages817-836
Number of pages20
ISBN (Print)9783662468029
DOIs
StatePublished - 2015
Event34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015 - Sofia, Bulgaria
Duration: 26 Apr 201530 Apr 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9057
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015
Country/TerritoryBulgaria
CitySofia
Period26/04/1530/04/15

Keywords

  • Generic group model
  • Multiple discrete logarithm
  • Search-by-hyperplane-queries

Fingerprint

Dive into the research topics of 'Generic hardness of the multiple discrete logarithm problem'. Together they form a unique fingerprint.

Cite this