Computing small discrete logarithms faster

D.J. Bernstein, T. Lange

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

16 Citations (Scopus)

Abstract

Computations of small discrete logarithms are feasible even in "secure" groups, and are used as subroutines in several cryptographic protocols in the literature. For example, the Boneh–Goh–Nissim degree-2-homomorphic public-key encryption system uses generic square-root discrete-logarithm methods for decryption. This paper shows how to use a small group-specific table to accelerate these subroutines. The cost of setting up the table grows with the table size, but the acceleration also grows with the table size. This paper shows experimentally that computing a discrete logarithm in an interval of order l takes only 1.93·l1/3 multiplications on average using a table of size l1/3 precomputed with 1.21·l2/3 multiplications, and computing a discrete logarithm in a group of order l takes only 1.77·l1/3 multiplications on average using a table of size l1/3 precomputed with 1.24·l2/3 multiplications.
Original languageEnglish
Title of host publicationProgress in Cryptology - INDOCRYPT 2012 (13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings)
EditorsS. Galbraith, M. Nandi
Place of PublicationBerlin
PublisherSpringer
Pages318-338
ISBN (Print)978-3-642-34930-0
DOIs
Publication statusPublished - 2012
Eventconference; 13th International Conference on Cryptology in India; 2012-12-09; 2012-12-12 -
Duration: 9 Dec 201212 Dec 2012

Publication series

NameLecture Notes in Computer Science
Volume7668
ISSN (Print)0302-9743

Conference

Conferenceconference; 13th International Conference on Cryptology in India; 2012-12-09; 2012-12-12
Period9/12/1212/12/12
Other13th International Conference on Cryptology in India

Fingerprint

Subroutines
Cryptography
Network protocols
Costs

Cite this

Bernstein, D. J., & Lange, T. (2012). Computing small discrete logarithms faster. In S. Galbraith, & M. Nandi (Eds.), Progress in Cryptology - INDOCRYPT 2012 (13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings) (pp. 318-338). (Lecture Notes in Computer Science; Vol. 7668). Berlin: Springer. https://doi.org/10.1007/978-3-642-34931-7_19
Bernstein, D.J. ; Lange, T. / Computing small discrete logarithms faster. Progress in Cryptology - INDOCRYPT 2012 (13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings). editor / S. Galbraith ; M. Nandi. Berlin : Springer, 2012. pp. 318-338 (Lecture Notes in Computer Science).
@inproceedings{0cd621ac1252414bbf0662d7d6224043,
title = "Computing small discrete logarithms faster",
abstract = "Computations of small discrete logarithms are feasible even in {"}secure{"} groups, and are used as subroutines in several cryptographic protocols in the literature. For example, the Boneh–Goh–Nissim degree-2-homomorphic public-key encryption system uses generic square-root discrete-logarithm methods for decryption. This paper shows how to use a small group-specific table to accelerate these subroutines. The cost of setting up the table grows with the table size, but the acceleration also grows with the table size. This paper shows experimentally that computing a discrete logarithm in an interval of order l takes only 1.93·l1/3 multiplications on average using a table of size l1/3 precomputed with 1.21·l2/3 multiplications, and computing a discrete logarithm in a group of order l takes only 1.77·l1/3 multiplications on average using a table of size l1/3 precomputed with 1.24·l2/3 multiplications.",
author = "D.J. Bernstein and T. Lange",
year = "2012",
doi = "10.1007/978-3-642-34931-7_19",
language = "English",
isbn = "978-3-642-34930-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "318--338",
editor = "S. Galbraith and M. Nandi",
booktitle = "Progress in Cryptology - INDOCRYPT 2012 (13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings)",
address = "Germany",

}

Bernstein, DJ & Lange, T 2012, Computing small discrete logarithms faster. in S Galbraith & M Nandi (eds), Progress in Cryptology - INDOCRYPT 2012 (13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings). Lecture Notes in Computer Science, vol. 7668, Springer, Berlin, pp. 318-338, conference; 13th International Conference on Cryptology in India; 2012-12-09; 2012-12-12, 9/12/12. https://doi.org/10.1007/978-3-642-34931-7_19

Computing small discrete logarithms faster. / Bernstein, D.J.; Lange, T.

Progress in Cryptology - INDOCRYPT 2012 (13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings). ed. / S. Galbraith; M. Nandi. Berlin : Springer, 2012. p. 318-338 (Lecture Notes in Computer Science; Vol. 7668).

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

TY - GEN

T1 - Computing small discrete logarithms faster

AU - Bernstein, D.J.

AU - Lange, T.

PY - 2012

Y1 - 2012

N2 - Computations of small discrete logarithms are feasible even in "secure" groups, and are used as subroutines in several cryptographic protocols in the literature. For example, the Boneh–Goh–Nissim degree-2-homomorphic public-key encryption system uses generic square-root discrete-logarithm methods for decryption. This paper shows how to use a small group-specific table to accelerate these subroutines. The cost of setting up the table grows with the table size, but the acceleration also grows with the table size. This paper shows experimentally that computing a discrete logarithm in an interval of order l takes only 1.93·l1/3 multiplications on average using a table of size l1/3 precomputed with 1.21·l2/3 multiplications, and computing a discrete logarithm in a group of order l takes only 1.77·l1/3 multiplications on average using a table of size l1/3 precomputed with 1.24·l2/3 multiplications.

AB - Computations of small discrete logarithms are feasible even in "secure" groups, and are used as subroutines in several cryptographic protocols in the literature. For example, the Boneh–Goh–Nissim degree-2-homomorphic public-key encryption system uses generic square-root discrete-logarithm methods for decryption. This paper shows how to use a small group-specific table to accelerate these subroutines. The cost of setting up the table grows with the table size, but the acceleration also grows with the table size. This paper shows experimentally that computing a discrete logarithm in an interval of order l takes only 1.93·l1/3 multiplications on average using a table of size l1/3 precomputed with 1.21·l2/3 multiplications, and computing a discrete logarithm in a group of order l takes only 1.77·l1/3 multiplications on average using a table of size l1/3 precomputed with 1.24·l2/3 multiplications.

U2 - 10.1007/978-3-642-34931-7_19

DO - 10.1007/978-3-642-34931-7_19

M3 - Conference contribution

SN - 978-3-642-34930-0

T3 - Lecture Notes in Computer Science

SP - 318

EP - 338

BT - Progress in Cryptology - INDOCRYPT 2012 (13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings)

A2 - Galbraith, S.

A2 - Nandi, M.

PB - Springer

CY - Berlin

ER -

Bernstein DJ, Lange T. Computing small discrete logarithms faster. In Galbraith S, Nandi M, editors, Progress in Cryptology - INDOCRYPT 2012 (13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings). Berlin: Springer. 2012. p. 318-338. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-34931-7_19