Departamento de Computación

Los esquemas criptográficos basados en emparejamientos bilineales fueron propuestos en el área de criptografía asimétrica a principios de siglo, con la finalidad de dar solución a problemas que estuvieron abiertos por décadas. Uno de estos problemas, por nombrar sólo uno, consiste en cómo compartir un secreto entre tres entidades mediante el intercambio de información pública, en una sola ronda. Estos esquemas criptográficos utilizan un emparejamiento bilineal entre subgrupos cíclicos definidos en curvas elípticas o hiperelípticas, y un subgrupo multiplicativo en una cierta extensión del campo finito sobre el que se construyen las curvas. Los emparejamientos bilineales simétricos conocidos como de Tipo 1 se definen sobre un campo base de característica 2 o 3, esto nos da la posibilidad de tomar ventaja de las características de la nueva generación de procesadores durante la fase de implementación debido a la naturaleza de la aritmética en estos campos, permitiendo así una implementación rápida y eficiente. Los emparejamientos de Tipo 1 brindan propiedades específicas que son aprovechadas en la construcción de novedosos protocolos basados en ellos. Una condición de seguridad indispensable en un esquema criptográfico basado en emparejamientos, es que el problema del logaritmo discreto definido en los subgrupos de curvas y en el subgrupo del campo finito que componen el emparejamiento sea difícil de resolver. En los últimos años, ha habido avances significativos en el cálculo del logaritmo discreto en campos finitos de característica pequeña, lo que puso en una situación de incertidumbre e inestabilidad la seguridad de la criptografía basada en emparejamientos de Tipo 1. En esta tesis, se demuestra por primera vez que los nuevos algoritmos para el cálculo del logaritmo discreto impactan drásticamente la seguridad de los esquemas basados en emparejamientos de Tipo 1. También, se muestra que los campos de característica pequeña F_3^6·509 , F_2^12·367 , F_3^6·1429 y F_2^4·3041 que se pensaba ofrecían 128 y 192 bits de seguridad en realidad brindad niveles de seguridad significativamente más bajos. El análisis que llevo a estas conclusiones fue posible gracias al diseño de herramientas y un marco de trabajo que permiten realizar evaluaciones prácticas de estos nuevos algoritmos. Además, se presenta la primera implementación de los recientes algoritmos para el cálculo del logaritmo discreto con el fin de atacar el campo finito F_3^6·137, el cual es de interés criptográfico. Este cómputo ilustra la efectividad de los nuevos métodos para el cálculo del logaritmo discreto en campos finitos de característica pequeña que no sean de Kummer o twisted-Kummer. Debido a los refinamientos a los nuevos algoritmos, se realizó el primer cálculo de logaritmo discreto en un campo finito de característica 3, F_3^6·509 , que se pensaba ofrecía 128 bits de seguridad. Además del trabajo realizado en el problema del logaritmo discreto, en esta tesis se presentan dos nuevos algoritmos que permiten calcular raíces cuadradas en extensiones de grado par de campos de característica grande. Uno de estos algoritmos supera a los algoritmos existentes en el estado del arte en varios escenarios criptográficos, mientras que el otro ofrece un mejor balance entre eficiencia y seguridad en comparación con los algoritmos existentes.

Abstract

Pairing-based protocols appeared in public key cryptography, at the beginning of the century, as solutions to problems that remained unsolved for decades. One of these problems, to name but one, is the possibility for three parties to share a secret key by exchanging information via a public network in only one round. These protocols essentially use bilinear pairing maps defined from cyclic subgroups of elliptic or hyperelliptic curves, to a subgroup of the multiplicative group of some extension of the finite field, over which are defined the curves. In symmetric bilinear pairings, known as Type 1 pairings, the underlying finite field has characteristic 2 or 3. Besides the significant acceleration new generation processors can provide when performing operations in finite fields of characteristic 2 or 3, Type 1 pairings have the benefit of being equipped with specific properties that allow them to be employed in most pairing-based protocols. A necessary condition for the security of a pairing-based cryptosystem is that the discrete logarithm problem (DLP) in the subjacent curve subgroups and the field subgroup must be hard. In recent years, there have been several dramatic improvements in algorithms for computing discrete logarithms in small characteristic finite fields, that consequently placed the security of the Type 1 pairing-based cryptography in a state of uncertainty. In this thesis, we demonstrate for the first time that the new algorithms drastically impact the security of cryptosystems based on Type 1 pairings. We show that small characteristic finite fields of cryptographic interest, such as F_3^6·509 , F_2^12·367 , F_3^6·1429 , and F_2^4·3041 that were assumed to enjoy 128 and 192 bits of security, in fact, find their security levels considerably lowered, and, at the same time, that of cryptographic protocols utilizing pairings derived from elliptic or hyperelliptic curves over these fields. The concrete analyses that led to these conclusions were made possible by designing a convenient framework and tools able to perform practical assessments of the new algorithms. The first implementation of the new DLP algorithms for attacking a cryptographically interesting finite field, namely F_3^6·137, is presented in this thesis. This computation illustrates the effectiveness of the new algorithms in small characteristic finite fields that are not Kummer or twisted-Kummer extensions. As a consequence of more recent refinements on the recent methods, we completed the first discrete logarithm computation in a characteristic-three finite field that was previously believed to provide 128 bits of security, namely F_3^6·509. In addition to the work on the DLP over small characteristic finite fields, we present two new algorithms for computing square roots in even-degree extension fields of large characteristic. One of these algorithms outperforms previously existing algorithms in several cryptographic settings, while the other one offers a better trade-off between efficiency and security than previous methods.