Departamento de Computación

Desde el año 2000 los emparejamientos bilineales han sido la piedra angular de novedosos y creativos protocolos criptográficos. Desafortunadamente, todos los protocolos basados en emparejamientos requieren del cálculo de varios de éstos. Además, el costo computacional de los emparejamientos es bastante alto. Por tales motivos, se han publicado diversas propuestas en la literatura abierta donde se muestran mejoras de los algoritmos de los emparejamientos de Weil y de Tate. Recientemente, Vercauteren propuso una variante del emparejamiento de Tate llamada emparejamiento óptimo "ate''. Otras mejoras propuestas han sido en torno a la generación de curvas elípticas amigables con los emparejamientos bilineales, como las presentadas por Barreto y Naehrig, las cuales son fáciles de generar a partir de una selección adecuada de parámetros que contribuyen a la eficiencia del cálculo del emparejamiento. Posteriormente, Naehrig mostró la particularización del emparejamiento óptimo "ate'' para curvas Barreto-Naehrig. Esta tesis describe el análisis, diseño e implementación de una biblioteca de software eficiente para el cálculo del emparejamiento óptimo "ate'' sobre curvas elípticas Barreto-Naehrig. .

Abstract

Since year 2000, bilinear pairings have been the heart of several news and creative cryptographic protocols. Unfortunately, the pairing based protocols require the computation of many pairings. Hence pairings have a very high computational cost. For those reasons, many proposal have been published in the open literature showing improvements on the Weil and Tate pairing algorithms. More recently, Vercauteren proposed and improvement on the Tate pairing algorithm called optimal ate pairing. Others described improvements are about the pairing friendly elliptic curve generation, such kind of curves are the described by Barreto and Naehrig, which are particularly easy to generate from a proper choice of parameters, those parameters will contribute to the efficiency on the pairing computation. Then, Naehrig showed the particularization of the optimal ate pairing on Barreto-Naehrig elliptic curves. This thesis describes the analysis, design and implementation of an efficient software library for the optimal ate pairing computation on Barreto-Naehrig elliptic curves. .