Criptografía de Curvas Elípticas y Logaritmo Discreto. Implementación de Autoreducibilidad aleatoria - Claudio Qureshi (2012)

Este trabajo se enmarca en el contexto de Criptografía de Curvas Elípticas. Uno de los tópicos principales en dicha área son los criptosistemas basados en el Problema del Logaritmo Discreto (PLD) en Curvas elípticas. Este es un caso particular de criptosis- temas de clave pública que basa su seguridad en la dificultad de resolver el PLD en un grupo abeliano. \( \\ \\ \\ \) Inicialmente se tomó como grupo, el grupo multiplicativo de un cuerpo finito. Al ser descubierto un algoritmo de tiempo subexponencial para resolver el PLD en esos grupos (basado en el Index Calculus) se necesitaban claves cada vez más largas para garantizar un buen nivel de seguridad. \( \\ \\ \\ \) En 1985 independientemente Koblitz y Miller propusieron utilizar el grupo formado por los puntos racionales de una curva elíptica definida sobre un cuerpo finito. La ventaja primordial, es que se lograban alcanzar los mismos niveles de seguridad que utilizando el grupo multiplicativo de un cuerpo finito utilizando claves mucho más cortas. Esta característica lo hacía ideal para ser utilizado en dispositivos con entornos operativos restringidos (limitaciones de memoria, ancho de banda, potencia, etc). \( \\ \\ \\ \) Hasta el momento no se ha encontrado un algoritmo de tiempo subexponencial capaz de resolver el PLD en curvas elíıpticas en general y se ha convertido en uno de los principales estándares a ser utilizado en la actualidad. No todas las curvas elípticas definidas sobre el mismo cuerpo finito ofrecen el mismo nivel de seguridad respecto del PLD. Se conocen criterios que hacen a una curva débil, todos ellos se reducen de alguna forma a alguna condición sobre la cantidad de puntos racionales que posea la curva. Sin embargo, aún es un problema en abierto determinar si el hecho de que dos curvas (definidas sobre el mismo cuerpo finito) posean la misma cantidad de puntos racionales implica necesariamente que la dificultad de resolver el PLD en ambas curvas sea equivalente. \( \\ \\ \\ \) Una manera de probar la equivalencia del PLD en dos grupos es encontrando un isomorfismo entre ambos grupos que tanto él, como su inversa puedan ser computados eficientemente (digamos, en tiempo polinomial por ejemplo). Esto es fácil de ver, dado que los isomorfismos preservan el orden de los elementos. Generalizando esta idea, se puede llegar a la conclusión que basta con que haya una cadena de homomorfismos de grupo (cada una con kernel de cardinal pequeño y conocido) que partiendo de uno de los grupos llegue al otro; en este caso cada homomorfismo debe ser eficientemente computable.