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{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.
Chapter PDF
Similar content being viewed by others
References
Digital signature standard (DSS). NIST (National Institute of Standards and Technology) FIPS, 186–4 (2013)
Bernstein, D.J., Lange, T.: Computing small discrete logarithms faster. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 317–338. Springer, Heidelberg (2012)
Boneh, D., Boyen, X.: Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol. 21(2), 149–177 (2008)
Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)
Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)
Bruen, A.A.: Polynomial multiplicities over finite fields and intersection sets. Journal of Combinatorial Theory, Series A 60(1), 19–33 (1992)
Hitchcock, Y., Montague, P., Carter, G., Dawson, E.: The efficiency of solving multiple discrete logarithm problems and the implications for the security of fixed elliptic curves. International Journal of Information Security 3(2), 86–98 (2004)
Kuhn, F., Struik, R.: Random walks revisited: Extensions of Pollard’s Rho algorithm for computing multiple discrete logarithms. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, p. 212. Springer, Heidelberg (2001)
Lee, H.T., Cheon, J.H., Hong, J.: Accelerating ID-based encryption based on trapdoor DL using pre-computation. Cryptology ePrint Archive, Report 2011/187 (2011). http://eprint.iacr.org/2011/187
Maurer, U.M., Yacobi, Y.: A non-interactive public-key distribution system. Designs, Codes and Cryptography 9(3), 305–316 (1996)
Nechaev, V.I.: Complexity of a determinate algorithm for the discrete logarithm. Mathematical Notes 55(2), 165–172 (1994)
Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997)
Sørensen, A.B.: On the number of rational points on codimension-1 algebraic sets in \(P^n(F_q)\). Discrete Mathematics 135(1–3), 321–334 (1994)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
Yun, A. (2015). Generic Hardness of the Multiple Discrete Logarithm Problem. In: Oswald, E., Fischlin, M. (eds) Advances in Cryptology - EUROCRYPT 2015. EUROCRYPT 2015. Lecture Notes in Computer Science(), vol 9057. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46803-6_27
Download citation
DOI: https://doi.org/10.1007/978-3-662-46803-6_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46802-9
Online ISBN: 978-3-662-46803-6
eBook Packages: Computer ScienceComputer Science (R0)