La criptografía es la práctica y estudio de técnicas para asegurar las comunicaciones en presencia de terceras personas llamadas adversarios. La criptografía toma como base "problemas computacionalmente difíciles" para proveer servicios como autenticación, confidencialidad, integridad, no repudio, entre otros. Se dice que un problema es computacionalmente difícil si no existe un algoritmo polinomial (en complejidad y espacio) capaz de resolverlo en un escenario factible. Algunos problemas computacionales que son considerados difíciles en computadoras clásicas podrían no ser difíciles en computadoras cuánticas por ejemplo, la factorización entera. El algoritmo de Shor puede resolver la factorización entera en tiempo polinomial cuántico, más aún, también puede resolver el problema del logaritmo discreto. Hoy en día muchos protocolos de seguridad están basados en esos dos problemas por lo que surge la necesidad de encontrar problemas difíciles para computadoras cuánticas. Recientemente los procotolos basados en isogenias han llamado la atención de los criptógrafos por su capacidad de resistir las computadoras cuánticas. Las isogenias entre curvas elípticas con homomorphismos de grupo y para propósitos criptográficos, es posible definir un par de problemas computacionales difíciles aún ante la amenaza de computadoras cuánticas. Si bien estudio de las isogenias en matemáticas no es nuevo, el uso de estas como una primitiva criptográfica viable lo es.
En éste trabajo presentamos un estudio de cómo las isogenias son utilizadas en criptografía y de manera particular en la criptografía de llave pública. Presentamos las cuatro clases de isogenia que existen en las curvas de Koblitz definidas sobre F4 y como una de éstas (hasta donde sabemos no estudiada antes) contiene un endomorfismo que permite una aceleración considerable en la multiplicación escalar en dichas curvas. Se presenta un análisis de seguridad del protocolo SIDH tomando como base el problema de encontrar colisiones en dos conjuntos, y con base en éste análisis se proponen nuevos parámetros para ser utilizados en el protocolo SIDH. Además presentamos algunas remediaciones ante ataques de fallo a la implementación del protocolo CSIDH y se presenta la forma de obtener una implementación de tiempo constante. Se introduce el uso de algoritmos aritméticos para mejorar el cómputo de isogenias de grado impar de la forma d = 8k + r con r ∈ {1,3,5,7}. Finalmente se estudia la inclusión del cómputo paralelo en el protocolo SIDH la cuál nos permite desarrollar una variante del mismo llamada eSIDH ("extended SIDH"). El cómputo paralelo en el contexto del cómputo de isogenias ha sido estudiado antes pero nuestra variante introduce el uso de 3 primos en la configuración de SIDH lo cuál permite tomar ventaja del cómputo paralelo en la generación de llaves y el cómputo de isogenias. Más aún, tomamos ventaja de algunas propiedades de la escalera de Montgomery para computar eficientemente múltiplos de la llave privada en paralelo y en conjunto, todas estas mejoras derivan en una aceleración teórica cercana a computar el protocolo eSIDH hasta 3 veces más rápido
Abstract
Cryptography is the practice and study of techniques for secure communication in the presence of third parties called adversaries [103]. Cryptography uses "hard computational problems" to provide security services such as authentication, confidentiality, integrity, non-repudiation, among others. We say that a computational problem is hard if there is no polynomial (time and space) algorithm able to solve it in a feasible scenario. Some computational problems that are considered hard on non-quantum (classical) computers could be not hard on quantum computers, for example, the integer factorization. Shor's algorithm can solve integer factorization in a quantum computer in polynomial time; moreover, it can also break the discrete log problem. Nowadays, most security protocols are based on those problems, and then there is a necessity to find hard problems for quantum computing. Recently, isogeny-based protocols took the attention of cryptographers due to its resistance to quantum computers. Isogenies between elliptic curves are group homomorphisms, and for cryptography purposes, it is possible to define a couple of hard computational problems even considering the quantum menace.
The study of isogenies in mathematics is not new, but the use as a viable cryptographic primitive is, in this work, we review how isogenies are used in cryptography in particular, in public key cryptography. We present the 4 isogeny classes on Koblitz curves over F4 and how a no-studied-before (as far as we know) class contains an eficient endomorphim which allows a considerable speed-up for scalar multiplication computation on such curves. We present a security analysis of the SIDH protocol based on the problem of found collitions on two sets and exhibe new parameters to be used in SIDH protocol. We present some remediations to CSIDH implementation against fault attacks an how we can achieve a constant-time implementation. We introduce the use of some arithmetic algorithms to improve the computation of odd-degree isogenies of the form d = 8k + r con r ∈ {1,3,5,7}. Finally we introduce the use of parallel computing in SIDH and we develop a variant of SIDH that we dubed as eSIDH (extended SIDH). Parallel computing has been studies before in the isogeny computation context but our novel variant of eSIDH introduces the use of 3 primes into the SIDH configuration, allowing us to take more advantage of parallel computing in key generation and isogeny computations. Furthermore we take advantage of some properties of Montgomery ladder to compute multiples of the key in parallel and this all together derives in a theoretically speed up of about 3 times faster than traditional SIDH
