tailieunhanh - On the Discrete Logarithm Problem on Algebraic Tori

Using a recent idea of Gaudry and exploiting rational repre-sentations of algebraic tori, we present an index calculus type a lgorithm for solving the discrete logarithm problem that works directly in these groups. | On the Discrete Logarithm Problem on Algebraic Tori R. Granger1 and F. Vercauteren2 1 University of Bristol Department of Computer Science Merchant Venturers Building Woodland Road Bristol BS8 1UB United Kingdom granger@ 2 Department of Electrical Engineering University of Leuven Kasteelpark Arenberg 10 B-3001 Leuven-Heverlee Belgium 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 T2 Fpm and T6 Fpm 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. 1 Introduction The first instantiation of public key cryptography the Diffie-Hellman key agreement protocol 5 was based on the assumption that discrete logarithms in finite fields are hard to compute. Since then the discrete logarithm problem DLP has been used in a variety of cryptographic protocols such as the signature and encryption schemes due to ElGamal 6 and its variants. During the 1980 s these schemes were formulated in the full multiplicative group of a finite field Fp. To speed-up exponentiation and obtain shorter signatures Schnorr 24 proposed to work in a small prime order subgroup of the multiplicative group F of a prime finite field. Most modern DLP-based cryptosystems such as the Digital Signature Algorithm DSA 9 follow Schnorr s idea. Lenstra 15 showed that by working in a prime order subgroup G of F m for extensions that admit an optimal normal basis one can obtain a further The work described in this paper has been supported in part by the