Actualmente los emparejamientos bilineales sobre curvas elípticas han sido utilizados como una primitiva en la construcción de nuevos protocolos criptográficos. Con el objetivo de hacer práctico el uso de estos protocolos, en los últimos años diversos trabajos de investigación se han enfocado en el diseño e implementación eficiente y segura de los emparejamientos bilineales. En general, un emparejamiento bilineal está definido como la proyección e : G1 ×G2 --> GT , donde G1 y G2 son grupos cíclicos escritos de manera aditiva, formados por puntos en una curva elíptica E de orden r y GT es un grupo cŽiclico escrito de manera multiplicativa, formado por los elementos de orden r del campo finito Fpk , tal que r es un número primo y k es el grado de encajamiento de E/Fp.
En esta tesis se muestran las estimaciones referentes al desempeño de los emparejamientos óptimos ate y óptimos de Weil en su versión serial y paralela con 192 bits de seguridad, sobre las siguientes familias de curvas elípticas amables con los emparajeramientos: BN (Barreto-Naehrig), BW-12 (Brezing-Weng), KSS-18 (Kachisa-Schaefer- Scott) y BLS-24 (Barreto-Lynn-Scott). Además, se presentan dos nuevos métodos basados en rejillas que mejoran de manera significativa el cómputo de la "exponenciación final" y el cómputo de la "función picadillo hacia el grupo G2". Los resultados obtenidos a partir de ambos métodos son los más eficientes reportados hasta el momento.
Abstract
Nowadays, the bilinear pairings over elliptic curves have been used as a primitive in the construction of new insteresting cryptographic protocols. With the aim of making these protocols practical, in the recent years a lot of research towards the efficient and secure design and implementation of the pairings have been done. Roughly speaking, a bilinear pairing is defined by the mapping e : G1 × G2 --> GT , where G1 and G2 are additively written cyclic groups, comprised by all the points of order r in an elliptic curve E, and GT is multiplicatively written cyclic group, comprised by all the elements of order r in the finite field Fpk, such that r is a large prime number and k is the embedding degree of E/Fp.
In this work, it's presented the estimated computational costs of the optimal ate and optimal Weil pairings in a sequential and parallel implementation at a 192-bit security level, over the following families of pairing-friendly elliptic curves: BN (Barreto- Naehrig), BW-12 (Brezing-Weng), KSS-18 (Kachisa-Schaefer-Scott) y BLS-24 (Barreto- Lynn-Scott). Moreover, a new lattice-based methods for computing the "final exponentiation" and the "hashing to G2", are presented. These novel methods are the most efficient so far.
