### Abstract

Original language | English |
---|---|

Title of host publication | Progress in Cryptology - INDOCRYPT 2012 (13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings) |

Editors | S. Galbraith, M. Nandi |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 318-338 |

ISBN (Print) | 978-3-642-34930-0 |

DOIs | |

Publication status | Published - 2012 |

Event | conference; 13th International Conference on Cryptology in India; 2012-12-09; 2012-12-12 - Duration: 9 Dec 2012 → 12 Dec 2012 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 7668 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | conference; 13th International Conference on Cryptology in India; 2012-12-09; 2012-12-12 |
---|---|

Period | 9/12/12 → 12/12/12 |

Other | 13th International Conference on Cryptology in India |

### Fingerprint

### Cite this

*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

}

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 -