On the Discrete Logarithm Problem on Algebraic Tori

R Granger, Frederik R G Vercauteren

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

Abstract

Using a recent idea of Gaudry and exploiting rational representations of algebraic tori, we present an index calculus type algorithm for solving the discrete logarithm problem that works directly in these groups. Using a prototype implementation, we obtain practical upper bounds for the difficulty of solving the DLP in the tori $T_2(\F_{p^m})$ and $T_6(\F_{p^m})$ for various $p$ and $m$. Our results do not affect the security of the cryptosystems LUC, XTR, or CEILIDH over prime fields. However, the practical efficiency of our method against other methods needs further examining, for certain choices of $p$ and $m$ in regions of cryptographic interest.
Translated title of the contributionOn the Discrete Logarithm Problem on Algebraic Tori
Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2005
PublisherSpringer Berlin Heidelberg
Pages66 - 85
Number of pages19
Volume3621
Publication statusPublished - Aug 2005

Publication series

NameLecture Notes in Computer Science
PublisherSpringer

Bibliographical note

Conference Proceedings/Title of Journal: Advances in Cryptology (CRYPTO 2005)

Fingerprint Dive into the research topics of 'On the Discrete Logarithm Problem on Algebraic Tori'. Together they form a unique fingerprint.

  • Cite this

    Granger, R., & Vercauteren, F. R. G. (2005). On the Discrete Logarithm Problem on Algebraic Tori. In Advances in Cryptology - CRYPTO 2005 (Vol. 3621, pp. 66 - 85). (Lecture Notes in Computer Science). Springer Berlin Heidelberg. http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000247