Generic hardness of the multiple discrete logarithm problem

Aaram Yun

doi:10.1007/978-3-662-46803-6_27

Generic hardness of the multiple discrete logarithm problem

Aaram Yun

Department of Cyber Security

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

14 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 language	English
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
Publisher	Springer Verlag
Pages	817-836
Number of pages	20
ISBN (Print)	9783662468029
DOIs	https://doi.org/10.1007/978-3-662-46803-6_27
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

Publication series

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

Conference

Conference	34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015
Country/Territory	Bulgaria
City	Sofia
Period	26/04/15 → 30/04/15

Bibliographical note

Publisher Copyright:
© International Association for Cryptologic Research 2015.

Keywords

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

Access to Document

10.1007/978-3-662-46803-6_27

Cite this

Yun, A. (2015). Generic hardness of the multiple discrete logarithm problem. In M. Fischlin, & E. Oswald (Eds.), Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings (pp. 817-836). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9057). Springer Verlag. https://doi.org/10.1007/978-3-662-46803-6_27

Yun, Aaram. / Generic hardness of the multiple discrete logarithm problem. Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings. editor / Marc Fischlin ; Elisabeth Oswald. Springer Verlag, 2015. pp. 817-836 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8054c391e4c24caba109bbde39de8f81,

title = "Generic hardness of the multiple discrete logarithm problem",

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.",

keywords = "Generic group model, Multiple discrete logarithm, Search-by-hyperplane-queries",

author = "Aaram Yun",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2015.; 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015 ; Conference date: 26-04-2015 Through 30-04-2015",

year = "2015",

doi = "10.1007/978-3-662-46803-6_27",

language = "English",

isbn = "9783662468029",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "817--836",

editor = "Marc Fischlin and Elisabeth Oswald",

booktitle = "Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings",

}

Yun, A 2015, Generic hardness of the multiple discrete logarithm problem. in M Fischlin & E Oswald (eds), Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9057, Springer Verlag, pp. 817-836, 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015, Sofia, Bulgaria, 26/04/15. https://doi.org/10.1007/978-3-662-46803-6_27

Generic hardness of the multiple discrete logarithm problem. / Yun, Aaram.
Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings. ed. / Marc Fischlin; Elisabeth Oswald. Springer Verlag, 2015. p. 817-836 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9057).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Generic hardness of the multiple discrete logarithm problem

AU - Yun, Aaram

N1 - Publisher Copyright: © International Association for Cryptologic Research 2015.

PY - 2015

Y1 - 2015

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

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

KW - Generic group model

KW - Multiple discrete logarithm

KW - Search-by-hyperplane-queries

UR - http://www.scopus.com/inward/record.url?scp=84942693903&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-46803-6_27

DO - 10.1007/978-3-662-46803-6_27

M3 - Conference contribution

AN - SCOPUS:84942693903

SN - 9783662468029

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 817

EP - 836

BT - Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings

A2 - Fischlin, Marc

A2 - Oswald, Elisabeth

PB - Springer Verlag

T2 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015

Y2 - 26 April 2015 through 30 April 2015

ER -

Yun A. Generic hardness of the multiple discrete logarithm problem. In Fischlin M, Oswald E, editors, Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings. Springer Verlag. 2015. p. 817-836. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-46803-6_27

Generic hardness of the multiple discrete logarithm problem

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this