Computing small discrete logarithms faster

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

17 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 Dive into the research topics of 'Computing small discrete logarithms faster'. Together they form a unique fingerprint.

Cite this