Departamento de Computación

Un problema se considera difícil de resolver si no se conoce ningún algoritmo que lo solucione con complejidad polinomial en tiempo. Por ejemplo, dado un grupo cíclico con orden suficientemente grande, la exponenciación es un cálculo sencillo, mientras que su operación inversa, el logaritmo discreto, se cree que es un cálculo difícil. Una función de un solo sentido (one-way function en inglés) es una función fácil de calcular pero difícil de invertir, y el logaritmo discreto se clasifica como una función de este tipo. Las funciones de un solo sentido se utilizan en criptografía de llave pública; el protocolo Diffie-Hellman de intercambio de llaves y el criptosistema ElGamal, son ejemplos del uso del logaritmo discreto. Actualmente, el algoritmo estándar para calcular el logaritmo discreto, es el algoritmo de cálculo de índices. La complejidad de este algoritmo es sub-exponencial en tiempo y consta de cuatro fases: (i) base de factores, (ii) generación de relaciones, (iii) álgebra lineal y (iv) descenso. Desde que Leonard Adleman propuso la primer versión del algoritmo en 1979, se han presentado diversas mejoras en las fases para reducir su complejidad total. La fase de descenso se ejecuta por pasos, y la operación más costosa en cada paso es determinar si un polinomio es suave respecto a un grado establecido. Para lo anterior, se tiene la opción de factorizar al polinomio en cuestión, o la de calcular una prueba de suavidad. La segunda estrategia resulta ser más eficiente en términos computacionales. Este trabajo está enfocado en la prueba de suavidad para polinomios, con el obejtivo principal de realizar una implementación eficiente de dicha prueba. Para ello, se escogió un campo finito que contiene un subgrupo multiplicativo de interés criptográfico, y se calculó el logaritmo discreto en este grupo. Específicamente, la implementación de la prueba de suavidad se utilizó en los pasos de descenso por fracciones continuas y descenso clásico. Actualmente, no se han reportado resultados del cálculo del logaritmo discreto en el campo elegido, y nuestro propósito es establecer una referencia en tiempo del esfuerzo requerido para este cálculo.

Abstract

A problem is considered to be difficult if there is no known algorithm that solves it with polynomial time complexity. For example, given a cyclic group whose order is sufficiently large, exponentiation is a rather simple computation, whereas its inverse operation, i.e. the discrete logarithm, is believed to be a difficult one. A one-way function is a function that is easy to compute, but difficult to invert, and the discrete logarithm is classified as a function of this kind. One-way functions are widely used within public key cryptography; the Diffie-Hellman key exchange protocol and the ElGamal cryptosystem, are examples of the usage of the discrete logarithm. Nowadays, the standard algorithm to compute the discrete logarithm is the indexcalculus algorithm. This algorithm has sub-exponential time complexity and consists of four phases: (i) factor base, (ii) generation of relations, (iii) linear algebra and (iv) descent. Since Leonard Adleman proposed the first version of this algorithm in 1979, there have been many improvements in its phases, aiming to reduce the total complexity of the whole algorithm. The descent phase is performed in steps, and the most complex operation in these steps is to determine whether a polynomial is smooth with respect to a given degree. For this, one can either factorize the polynomial or perform a smoothness test on it. The latter approach is more efficient from a computational perspective. This work focuses on the smoothness test for polynomials, and the main objective is to develop an efficient implementation of this test. We chose a finite field that contains a multiplicative subgroup of cryptographic interest, and we computed the discrete logarithm in that group. Specifically, the smoothness test implementation was used in the continued-fraction and classical steps of the descent phase. At the time of writing this manuscript, there are no reported results on the computation of the discrete logarithm for the chosen field, and our purpose is to establish a time reference of the effort required for this computation.