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

note = "conference; 13th International Conference on Cryptology in India; 2012-12-09; 2012-12-12 ; Conference date: 09-12-2012 Through 12-12-2012",

}