Protocolos criptográficos en anillos de grupo

• Autores: María Dolores Gómez Olvera
• Directores de la Tesis: Blas Torrecillas Jover (dir. tes.) , Juan Antonio López Ramos (codir. tes.)
• Lectura: En la Universidad de Almería ( España ) en 2024
• Idioma: español
• Títulos paralelos:
  • Cryptographic Protocols over Group Rings
• Tribunal Calificador de la Tesis: Joachim Rosenthal (presid.) , Juan Ramón García Rozas (secret.) , Joan-Josep Climent Coloma (voc.)
• Enlaces
  • Tesis en acceso abierto en: riUAL
• Resumen
  • español

    La investigación en Criptografía de clave pública, ciencia que estudia las comunicaciones seguras a través de un medio inseguro, está en plena ebullición. Desde que en 1976 W. Diffie y M. Hellman iniciasen esta rama de la Criptología, con el primer intercambio de clave que permitía la comunicación entre usuarios que no pueden encontrarse físicamente, no han cesado las propuestas para mejorar la eficiencia y la seguridad de esta rama.

    Pero a partir de 2016, cuando el Instituto Nacional de Estándares y Tecnología estadounidense (NIST) creó la competición para encontrar nuevos protocolos criptográficos, se ha visto que es cada vez más necesario tener alternativas a los más conocidos y utilizados actualmente, que en su mayoría siguen estando basados en el mismo problema propuesto en 1976, el Problema del Logaritmo Discreto.

    La principal amenaza a nuestras comunicaciones es la posibilidad de implementar el algoritmo de Shor, propuesto por P. Shor en 1997, y basado en computación cuántica. Cuando se diseñó este algoritmo, se cuestionaba si era posible su implementación, y en el mejor de los casos, se consideraba que tardaría muchos años en ser viable. Sin embargo, vemos como año tras año la investigación en computación cuántica avanza rápidamente. En 2019, Google alcanzó la supremacía cuántica, y en 2022, IBM presentó el procesador Osprey, de 433 qubits. La implementación del algoritmo de Shor supondría que los problemas en los que se basan los protocolos utilizados actualmente dejarían de ser seguros. En consecuencia, el NIST ha anunciado que es muy probable que los nuevos algoritmos resistentes a los ataques cuánticos que se están seleccionando comiencen a utilizarse en 2024. Aunque ya hay algoritmos seleccionados para este fin (CRYSTAL-Kyber en el caso de encriptación de clave pública), el NIST no ha dada por finalizada la competición, y sigue considerando nuevas alternativas.

    En la búsqueda de nuevos problemas en los que puedan basarse los protocolos criptográficos, G. Maze, C.

    Monico y J. Rosenthal proponen el Problema de la Acción del Semigrupo (SAP), que generaliza al Problema del Logaritmo Discreto. Este problema general no es vulnerable a los ataques cuánticos (aunque sí lo son algunos casos particulares del mismo), con lo que consideramos que es el ambiente adecuado en el que basarnos para proponer alternativas a los protocolos criptográficos actuales.

    En este trabajo se plantea una nueva línea de investigación, en el ámbito de los protocolos basados en anillos de grupo. Se proponen los anillos de grupo torcidos mediante un 2-cociclo como estructura algebraica, y una variación del Problema de la Descomposición, que denominamos Problema de la Descomposición del Producto Dihedral, como problema subyacente.

    En este contexto, presentamos un protocolo de acuerdo de clave y un criptosistema de clave pública, como protocolos criptográficos para dos usuarios. Posteriormente, generalizamos el acuerdo de clave para n usuarios, y estudiamos sus características de eficiencia.

    Entonces estudiamos la seguridad de los protocolos propuestos, en la línea basada en indistinguibilidad, planteando el problema subyacente de nuestros protocolos en forma de juego de seguridad, y también sus versiones computacional y decisional. Así, probamos que nuestro criptosistema tiene seguridad semántica, mediante una secuencia de juegos. Además, probamos que nuestros protocolos son seguros frente a los ataques conocidos en la literatura.

    Finalmente, probamos que los protocolos multiusuario son seguros, demostrando que la información compartida en los mismos no supone una ventaja con respecto a los protocolos de dos usuarios; y que tienen seguridad hacia delante y hacia detrás, esto es, que los antiguos usuarios no tendrán acceso a la información del grupo una vez que hayan sido eliminados, y que los nuevos no tendrán acceso a la información previa antes de pertenecer al grupo.

  • English

    Research in Public Key Cryptography, the science that studies secure communications through an insecure channel, is at its peak. Since W. Diffie and M. Hellman initiated this area of Cryptology in 1976, with the first key exchange that allowed communication between users who cannot physically meet, proposals to improve the efficiency and security in this area have not ceased. But since 2016, when the American National Institute of Standards and Technology (NIST) created the competition to find new cryptographic protocols, it has been seen that it is increasingly necessary to have alternatives to the best known and currently used ones, since they are mostly still based on the same problem proposed in 1976, the Discrete Logarithm Problem. The main threat to our communications is the possibility of implementing Shor’s algorithm, proposed by P. Shor in 1997, and based on quantum computing. When this algorithm was designed, it was questioned whether it was possible to implement it, and at best, it was considered that it would take many years to be viable. However, we see how research in quantum computing advances rapidly year after year. In 2019, Google achieved quantum supremacy, and in 2022, IBM presented the Osprey processor, with 433 qubits. The implementation of Shor’s algorithm would mean that the problems on which the currently used protocols are based would no longer be secure. Consequently, NIST has announced that it is very likely that the new algorithms resistant to quantum attacks that are being selected will begin to be used in 2024. Although there are already algorithms selected for this purpose (CRYSTAL-Kyber in the case of public key encryption), NIST has not finished the competition, and continues to consider new alternatives. In the search for new problems on which cryptographic protocols can be based, G. Maze, C. Monico and J. Rosenthal propose the Semigroup Action Problem (SAP), which generalizes to the Discrete Logarithm Problem. This general problem is not vulnerable to quantum attacks (although some particular cases of it are), so we consider it to be the appropriate environment on which to base ourselves to propose alternatives to current cryptographic protocols. In this work, a new line of research is proposed, in the field of protocols based on group rings. Twisted group rings with the multiplication twisted by a 2-cocycle are proposed as the algebraic structure, and a variation of the Decomposition Problem, which we call the Dihedral Product Decomposition Problem, as the underlying problem. In this context, we present a key agreement protocol and a public key cryptosystem, as two-user cryptographic protocols. Subsequently, we generalize the key agreement for n users, and study its efficiency characteristics. Then we study the security of the proposed protocols, along the lines based on indistinguishability, posing the underlying problem of our protocols in the form of a security game, and also its computational and decisional versions. Thus, we prove that our cryptosystem has semantic security, through a sequence of games. Furthermore, we prove that our protocols are secure against known attacks in the literature. Finally, we prove that multi-user protocols are secure, demonstrating that the information shared in them does not represent an advantage with respect to two-users protocols; and that they have forward and backward security, that is, that old users will not have access to the group information once they have been eliminated, and that new users will not have access to previous information before belonging to the group.