Computing small discrete logarithms faster

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

17 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelProgress in Cryptology - INDOCRYPT 2012 (13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings)
RedacteurenS. Galbraith, M. Nandi
Plaats van productieBerlin
UitgeverijSpringer
Pagina's318-338
ISBN van geprinte versie978-3-642-34930-0
DOI's
StatusGepubliceerd - 2012
Evenementconference; 13th International Conference on Cryptology in India; 2012-12-09; 2012-12-12 -
Duur: 9 dec 201212 dec 2012

Publicatie series

NaamLecture Notes in Computer Science
Volume7668
ISSN van geprinte versie0302-9743

Congres

Congresconference; 13th International Conference on Cryptology in India; 2012-12-09; 2012-12-12
Periode9/12/1212/12/12
Ander13th International Conference on Cryptology in India

Vingerafdruk Duik in de onderzoeksthema's van 'Computing small discrete logarithms faster'. Samen vormen ze een unieke vingerafdruk.

Citeer dit