En matemáticas, los gráficos de isogenia supersingular son una clase de gráficos expansores que surgen en la teoría de números computacionales y se han aplicado en criptografía de curva elíptica . Sus vértices representan curvas elípticas supersingulares sobre campos finitos y sus bordes representan isogenias entre curvas.
Definición y propiedades
Un gráfico de isogenia supersingular se determina eligiendo un número primo grande y un pequeño número primo , y considerando la clase de todas las curvas elípticas supersingulares definidas sobre el campo finito . Hay aproximadamentetales curvas, cada dos de las cuales pueden estar relacionadas por isogenias. Los vértices en el gráfico 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]
Los gráficos de isogenia supersingular son - gráficos regulares , lo que significa que cada vértice tiene exactamentevecinos. Pizer demostró que eran gráficos de Ramanujan , gráficos con propiedades de expansión óptimas para su grado. [1] [2] [4] [5] La demostración se basa en la demostración de Pierre Deligne de la conjetura de Ramanujan-Petersson . [4]
Aplicaciones criptográficas
Una propuesta para una función hash criptográfica implica comenzar desde un vértice fijo de un gráfico de isogenia supersingular, usar 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 gráfico y usar la identidad de el vértice alcanzado al final de la caminata como valor hash para la entrada. La seguridad del esquema de hash propuesto se basa en el supuesto de que es difícil encontrar caminos en este gráfico que conecten pares arbitrarios de vértices. [1]
También se ha propuesto utilizar paseos en dos grafos de isogenia supersingulares con el mismo conjunto de vértices pero diferentes conjuntos de aristas (definidos usando diferentes opciones de la parámetro) para desarrollar un intercambio de claves primitivo análogo al intercambio de claves Diffie-Hellman , llamado intercambio de claves de isogenia supersingular . [2]
Los métodos criptográficos adicionales basados en estos gráficos incluyen esquemas de firmas y criptografía de clave pública. Se han sugerido como una forma de criptografía post-cuántica : a partir de 2018[actualizar], no se conocen métodos de tiempo subexponencial para romper estos esquemas, incluso en computadoras cuánticas . [6]
Referencias
- ^ a b c Charles, Denis X .; Lauter, Kristin E .; Goren, Eyal Z. (2009), "Funciones hash criptográficas de gráficos de expansión" (PDF) , Journal of Cryptology , 22 (1): 93–113, doi : 10.1007 / s00145-007-9002-x , MR 2496385 , S2CID 6417679
- ^ a b c De Feo, Luca; Jao, David; Plut, Jérôme (2014), "Hacia criptosistemas cuántica resistente de isogenies supersingular curva elíptica" (PDF) , Journal of Mathematical criptología , 8 (3): 209-247, doi : 10.1515 / JMC-2.012-0015 , MR 3.259.113 , S2CID 10873244
- ^ Mestre, J.-F. (1986), "La méthode des graphes. Exemples et applications", 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
- ^ a b Pizer, Arnold K. (1990), "Gráficos de Ramanujan y operadores de Hecke", Bulletin of the American Mathematical Society , New Series, 23 (1): 127-137, doi : 10.1090 / S0273-0979-1990-15918-X , Señor 1027904
- ^ 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., 7 , American Mathematical Society, págs. 159-178, MR 1486836
- ^ 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.), Advances in Cryptology - EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 29 de abril - 3 de mayo de 2018, Actas, Parte III (PDF) , Conferencia Notes in Computer Science, 10822 , Cham: Springer, págs. 329–368, doi : 10.1007 / 978-3-319-78372-7_11 , MR 3794837