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 -