On the Discrete Logarithm Problem on Algebraic Tori

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(\mathbb{F}_{p^m})$ and $T_6(\mathbb{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.


Editor(s):
Shoup, Victor
Published in:
Advances in Cryptology – CRYPTO 2005, 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005. Proceedings, 66-85
Presented at:
Advances in Cryptology – CRYPTO 2005, Santa Barbara, California, USA, August 14-18, 2005
Year:
2005
Publisher:
Springer Berlin Heidelberg
Laboratories:




 Record created 2016-01-19, last modified 2018-09-13

External link:
Download fulltext
URL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)