Gráfico de isogenia supersingular

Clase de grafos expansores que surgen en la teoría de números computacionales

En matemáticas, los grafos de isogenia supersingular son una clase de grafos expansores que surgen en la teoría de números computacionales y se han aplicado en la criptografía de curvas elípticas . Sus vértices representan curvas elípticas supersingulares sobre cuerpos finitos y sus aristas representan isogenias entre curvas.

Definición y propiedades

Un grafo de isogenia supersingular se determina eligiendo un número primo grande y un número primo pequeño , y considerando la clase de todas las curvas elípticas supersingulares definidas sobre el cuerpo finito . Aproximadamente existen tales curvas, cada dos de las cuales pueden estar relacionadas por isogenias. Los vértices en el grafo de isogenia supersingular representan estas curvas (o más concretamente, sus j -invariantes , elementos de ) y los bordes representan isogenias de grado entre dos curvas. ^{[1] [2] [3]} ${\displaystyle p}$ ${\displaystyle \ell }$ ${\displaystyle \mathbb {F} _{p^{2}}}$ ${\displaystyle (p+1)/12}$ ${\displaystyle \mathbb {F} _{p^{2}}}$ ${\displaystyle \ell }$

Los grafos de isogenia supersingular son : grafos regulares , lo que significa que cada vértice tiene exactamente vecinos. Pizer demostró que eran grafos de Ramanujan , grafos con propiedades de expansión óptimas para su grado. ^{[1] [2] [4] [5]} La prueba se basa en la prueba de Pierre Deligne de la conjetura de Ramanujan-Petersson . ^[4] ${\displaystyle \ell +1}$ ${\displaystyle \ell +1}$

Aplicaciones criptográficas

Una propuesta para una función hash criptográfica implica partir de un vértice fijo de un grafo de isogenia supersingular, utilizar los bits de la representación binaria de un valor de entrada para determinar una secuencia de aristas a seguir en un recorrido por el grafo, y utilizar la identidad del vértice alcanzado al final del recorrido como valor hash para la entrada. La seguridad del esquema hash propuesto se basa en el supuesto de que es difícil encontrar caminos en este grafo que conecten pares arbitrarios de vértices. ^[1]

También se ha propuesto utilizar paseos en dos grafos de isogenia supersingular con el mismo conjunto de vértices pero diferentes conjuntos de aristas (definidos utilizando diferentes opciones del parámetro) para desarrollar una primitiva de intercambio de claves análoga al intercambio de claves de Diffie-Hellman , llamada intercambio de claves de isogenia supersingular , ^[2] sugerido como una forma de criptografía post-cuántica . ^[6] Sin embargo, una variante líder del intercambio de claves de isogenia supersingular se rompió en 2022 utilizando métodos no cuánticos. ^[7] ${\displaystyle \ell }$

Referencias

1. Charles, Denis X.; Lauter, Kristin E .; Goren, Eyal Z. (2009), "Funciones hash criptográficas a partir de gráficos expansores" (PDF) , Journal of Cryptology , 22 (1): 93–113, doi :10.1007/s00145-007-9002-x, MR  2496385, S2CID  6417679
2. De Feo, Luca; Jao, David; Plût, Jérôme (2014), "Hacia criptosistemas resistentes a los cuánticos a partir de isogenias de curvas elípticas supersingulares" (PDF) , Journal of Mathematical Cryptology , 8 (3): 209–247, doi :10.1515/jmc-2012-0015, MR  3259113, S2CID  10873244
3. Mestre, J.-F. (1986), "El método de los grafos. Ejemplos y aplicaciones", Actas de la conferencia internacional sobre números de clase y unidades fundamentales de campos numéricos algebraicos (Katata, 1986) , Universidad de Nagoya, págs. 217-242, MR  0891898
4. Pizer, Arnold K. (1990), "Gráficos de Ramanujan y operadores de Hecke", Boletín de la Sociedad Matemática Americana , Nueva serie, 23 (1): 127–137, doi : 10.1090/S0273-0979-1990-15918-X , MR  1027904
5. Pizer, Arnold K. (1998), "Gráficos de Ramanujan", Perspectivas computacionales sobre la teoría de números (Chicago, IL, 1995) , AMS/IP Stud. Adv. Math., vol. 7, American Mathematical Society, págs. 159–178, MR  1486836
6. Eisenträger, Kirsten ; Hallgren, Sean; Lauter, Kristin ; Morrison, Travis; Petit, Christophe (2018), "Gráficos de isogenia supersingular y anillos de endomorfismo: reducciones y soluciones" (PDF) , en Nielsen, Jesper Buus; Rijmen, Vincent (eds.), Avances en criptología – EUROCRYPT 2018: 37.ª Conferencia internacional anual sobre la teoría y las aplicaciones de las técnicas criptográficas, Tel Aviv, Israel, 29 de abril - 3 de mayo de 2018, Actas, Parte III (PDF) , Notas de clase en informática, vol. 10822, Cham: Springer, págs. 329–368, doi :10.1007/978-3-319-78372-7_11, MR  3794837, S2CID  4850644
7. Goodin, Dan (2 de agosto de 2022), "El contendiente del cifrado poscuántico es derrotado por una PC de un solo núcleo y 1 hora: dejemos que los matemáticos arruinen lo que parecía un nuevo algoritmo impresionante", Ars Technica