Grafo de isogenia supersingular

En matemáticas, los grafos de isogenia supersingular son una clase de grafos expansores que surgen en la teoría computacional de números 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.

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

Los gráficos de isogenia supersingular son${\displaystyle \ell +1}$- grafos regulares , lo que significa que cada vértice tiene exactamente${\displaystyle \ell +1}$vecinos. Pizer demostró que son grafos de Ramanujan , grafos 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 ]}

Una propuesta para una función hash criptográfica consiste en partir de un vértice fijo de un grafo 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 grafo, y usar la identidad del vértice alcanzado al final del recorrido como valor hash para la entrada. La seguridad del esquema de hash propuesto se basa en la suposición de que es difícil encontrar caminos en este grafo que conecten pares arbitrarios de vértices. ^{[ 1 ]}

También se ha propuesto utilizar recorridos en dos grafos de isogenia supersingulares con el mismo conjunto de vértices pero diferentes conjuntos de aristas (definidos utilizando diferentes elecciones de la${\displaystyle \ell }$parámetro) para desarrollar una primitiva de intercambio de claves análoga al intercambio de claves Diffie-Hellman , denominada intercambio de claves de isogenia supersingular , ^{[ 2 ]} sugerida como una forma de criptografía postcuántica . ^{[ 6 ]} Sin embargo, una variante principal del intercambio de claves de isogenia supersingular fue vulnerada en 2022 utilizando métodos no cuánticos. ^{[ 7 ]}