¿Qué tan difícil es resolverlo?

Por isomorfismo gráfico, sabemos que dos gráficos A y B son isomorfos si hay una matriz de permutación P tal que $A = P \times B \times P^{-1}$

Entonces, para resolver el problema, si dos gráficos son isomorfos, necesitamos encontrar una matriz de permutación de este tipo P. Se cree que el problema es NP (y NP completo para el caso del isomorfismo del subgrafo). Sin embargo, encontré un ejemplo para resolver P que me pareció prometedor y se puede encontrar en http://en.wikipedia.org/wiki/Permutation_matrix en la sección: resolución de P.

La confusión que tengo ahora es, ¿funciona eso para matrices más grandes? ¿muy grande? ¿Tengo razón, la ecuación anterior es difícil de resolver y puede ser candidato para un sistema criptográfico?

El isomorfismo gráfico ha sido bien estudiado. Un breve resumen: no se sabe que el problema de isomorfismo gráfico se encuentre en P (no se conocen algoritmos de tiempo polinomial), pero no se cree que sea NP completo. Existen algoritmos heurísticos para el isomorfismo gráfico que funcionan extremadamente bien en la mayoría de los casos que surgen en la práctica. Lea la página de Wikipedia sobre isomorfismo gráfico para obtener más información.

En cuanto a su enfoque propuesto particular: la página de Wikipedia a la que se vincula ya explica por qué ese método no funciona en general. Ese método solo funciona si no hay valores propios repetidos en la matriz correspondiente al gráfico de adyacencia. Por lo tanto, fallará para los gráficos donde hay valores propios repetidos. Tales gráficos no pueden ser ignorados. En consecuencia, ese método puede funcionar para algunos gráficos, pero fallará (o funcionará mal) para otros gráficos, por lo que no es una solución general.

El isomorfismo gráfico no es un buen candidato para una base para un sistema criptográfico, por dos razones. Primero, los algoritmos heurísticos existentes son muy buenos para resolver el problema en la práctica, y no está claro cómo generar instancias difíciles de isomorfismo gráfico. Segundo, y más seriamente, para ser útiles para la criptografía, necesitamos no solo tener un problema difícil; necesitamos tener una "trampilla oculta" que el creador de la clave pública pueda incrustar, lo que facilita el problema para el creador, pero que es difícil de detectar para cualquier otra persona. Nadie sabe cómo incrustar una "trampa oculta" en el problema del isomorfismo gráfico.

Como DW señala correctamente, no se sabe que el isomorfismo gráfico se encuentre en P, y se cree que no es NP-duro. Además, muchos creen que está en BQP, pero esto no ha sido probado. Eso lo coloca en la misma categoría que otros problemas en los que los criptosistemas suelen confiar para su seguridad, como la factorización principal y el problema de registro discreto, que se sabe que están en BQP. (No sé dónde se encuentra el problema de multiplicación inversa de la curva elíptica o como se llame con respecto a BQP, pero no me sorprendería en lo más mínimo si todos estos problemas criptográficamente útiles fueran equivalentes en algún sentido).

Es cierto que no conocemos los problemas de isomorfismo gráfico para los que la solución es "difícil". Sin embargo, supongamos por un momento que lo hicimos. Entonces sí, puedes usarlo para la criptografía.

Como ejemplo, veamos un sistema clave a prueba de conocimiento cero basado en el isomorfismo gráfico.

La clave privada de Alice es un gráfico etiquetado (las etiquetas pueden ser enteros) que se ha construido de manera tal que es "difícil" verificar el isomorfismo de un gráfico y contiene un ciclo hamiltoniano que es "difícil" encontrar. Su clave pública es solo el gráfico etiquetado, sin información sobre el ciclo hamiltoniano. Tenga en cuenta que derivar la clave privada de la clave pública requiere resolver el problema del ciclo hamiltoniano, que es NP-hard y, suponemos, es difícil para este gráfico en particular.

Alice quiere convencer a Bob de que conoce un ciclo hamiltoniano en el gráfico, sin realmente darle el ciclo hamiltoniano. Así es como ella lo hace.

Alice le envía a Bob un gráfico sin etiquetar. Ella le ofrece una opción: o revelará las etiquetas, o revelará un ciclo hamiltoniano en el gráfico. Bob lanza una moneda (o toma una decisión por algún otro medio) en cuanto a cuál quiere, y Alice hace cualquiera de las dos que Bob le pregunta.

Si Bob solicitó que se revelaran las etiquetas, puede verificar fácilmente (en tiempo lineal) que el gráfico etiquetado resultante es el mismo que la clave pública de Alice, pero no puede encontrar un ciclo hamiltoniano porque sería NP-hard. Si, por otro lado, Bob preguntó por el ciclo hamiltoniano, puede verificar fácilmente (nuevamente, en tiempo lineal) que el gráfico no marcado resultante contiene un ciclo hamiltoniano, pero no puede verificar que sea el gráfico de clave pública de Alice, porque el isomorfismo gráfico es (presumiblemente) difícil.

Desde el punto de vista de Bob, Alice podría haber intentado engañar a Bob dándole un gráfico que tiene un ciclo hamiltoniano conocido pero que no es isomorfo a su clave pública, o dándole su gráfico de clave pública con las etiquetas eliminadas pero sin saber el Ciclo hamiltoniano. Apostaría a que Bob tomaría la decisión equivocada. Suponiendo que Bob realmente hizo su elección al azar, entonces este truco tendría un 50% de posibilidades de éxito.

Por lo tanto, el intercambio anterior se repite con un gráfico diferente sin marcar. Después$n$ rondas del protocolo, la probabilidad de que Alice engañe exitosamente a Bob en todas las rondas es $2^{-n}$, que converge muy rápidamente a "tan seguro como sea necesario".

Esto, por supuesto, no está cerca de un sistema práctico tal como está. Además, hay algunas cosas obvias que puede hacer para que sea más seguro. Por ejemplo, en lugar de que Alice le envíe a Bob un gráfico sin etiquetar, podría enviarle un hash. Cuando Bob responde, ella puede enviar el gráfico, y Bob puede verificar que el gráfico coincida.

No obstante, en principio, podría crear un sistema criptográfico a partir de él, incluso si no es terriblemente útil.