Est-il difficile de résoudre dans ?

De l'isomorphisme des graphes, nous savons que deux graphes A et B sont isomorphes s'il existe une matrice de permutation P telle que $A = P \times B \times P^{-1}$

Donc, pour résoudre le problème, si deux graphes sont isomorphes, nous devons trouver une telle matrice de permutation P. Le problème est supposé être NP (et NP complet pour le cas de l'isomorphisme sous-graphique). Cependant, j'ai trouvé un exemple à résoudre pour P qui me semblait prometteur et peut être trouvé dans http://en.wikipedia.org/wiki/Permutation_matrix dans la section: résoudre pour P.

La confusion que j'ai maintenant est, cela fonctionne-t-il pour des matrices plus grandes? très grand? ai-je raison, l'équation ci-dessus est difficile à résoudre et peut être candidate à un système cryptographique?

L'isomorphisme des graphes a été bien étudié. Un bref résumé: le problème d'isomorphisme du graphe n'est pas connu pour être en P (il n'y a pas d'algorithmes connus en temps polynomial), mais il n'est pas supposé être NP-complet. Il existe des algorithmes heuristiques pour l'isomorphisme des graphes qui fonctionnent extrêmement bien sur la plupart des instances qui surviennent dans la pratique. Lisez la page Wikipedia sur l'isomorphisme des graphes pour en savoir plus.

Quant à votre approche particulière proposée: la page Wikipédia à laquelle vous avez lié explique déjà pourquoi cette méthode ne fonctionne pas en général. Cette méthode ne fonctionne que s'il n'y a pas de valeurs propres répétées dans la matrice correspondant au graphe d'adjacence. Par conséquent, il échouera pour les graphiques où il y a des valeurs propres répétées. Ces graphiques ne peuvent pas être ignorés. Par conséquent, cette méthode peut fonctionner pour certains graphiques mais elle échouera (ou fonctionnera mal) pour d'autres graphiques, donc ce n'est pas une solution générale.

L'isomorphisme graphique n'est pas un bon candidat pour une base pour un système cryptographique, pour deux raisons. Premièrement, les algorithmes heuristiques existants sont très efficaces pour résoudre le problème dans la pratique, et il n'est pas clair comment générer des instances dures d'isomorphisme de graphe. Deuxièmement, et plus sérieusement, pour être utile à la cryptographie, nous devons non seulement avoir un problème difficile; nous devons avoir une "trappe cachée" que le créateur de la clé publique peut intégrer, ce qui rend le problème facile pour le créateur, mais difficile à détecter pour quiconque. Personne ne sait comment intégrer une telle "trappe cachée" dans le problème d'isomorphisme du graphe.

Comme le note à juste titre DW, l'isomorphisme des graphes n'est pas connu pour être en P, et ne serait pas dur NP. De plus, beaucoup pensent qu'il s'agit de BQP, mais cela n'a pas été prouvé. Cela le place dans la même catégorie que d'autres problèmes sur lesquels les cryptosystèmes s'appuient généralement pour leur sécurité, tels que l'affacturage principal et le problème de journal discret, tous deux connus pour être dans BQP. (Je ne sais pas où se situe le problème de multiplication inverse de la courbe elliptique ou quelque chose comme ça en ce qui concerne le BQP, mais cela ne me surprendrait pas le moins si tous ces problèmes utiles sur le plan cryptographique se révélaient équivalents dans un certain sens.)

Il est vrai que nous ne connaissons pas les problèmes d'isomorphisme des graphes pour lesquels la solution est "difficile". Cependant, supposons un instant que nous l'avons fait. Alors oui, vous pouvez l'utiliser pour la cryptographie.

À titre d'exemple, regardons un système de clé à l'épreuve de la connaissance zéro basé sur l'isomorphisme des graphes.

La clé privée d'Alice est un graphe étiqueté (les étiquettes peuvent simplement être des entiers) qui a été construit de telle sorte qu'il est "difficile" de vérifier l'isomorphisme d'un graphe, et il contient un cycle hamiltonien qu'il est "difficile" de trouver. Sa clé publique n'est que le graphe étiqueté, sans aucune information sur le cycle hamiltonien. Notez que dériver la clé privée de la clé publique nécessite de résoudre le problème du cycle hamiltonien, qui est NP-difficile et, nous supposons, est difficile pour ce graphique en particulier.

Alice veut convaincre Bob qu'elle connaît un cycle hamiltonien dans le graphique, sans lui donner le cycle hamiltonien. Voici comment elle le fait.

Alice envoie à Bob un graphique non étiqueté. Elle lui offre un choix: soit elle dévoilera les étiquettes, soit elle révélera un cycle hamiltonien dans le graphique. Bob lance une pièce (ou prend une décision par un autre moyen) quant à celle qu'il veut, et Alice fait celle des deux que Bob demande.

Si Bob a demandé que les étiquettes soient révélées, il peut facilement vérifier (en temps linéaire) que le graphique étiqueté resuling est le même que la clé publique d'Alice, mais ne peut pas trouver un cycle hamiltonien car ce serait NP-difficile. Si, d'autre part, Bob a demandé le cycle hamiltonien, il peut facilement vérifier (encore une fois, en temps linéaire) que le graphe non étiqueté résultant contient bien un cycle hamiltonien, mais il ne peut pas vérifier qu'il s'agit du graphe à clé publique d'Alice, parce que l'isomorphisme du graphe est (vraisemblablement) difficile.

Du point de vue de Bob, Alice aurait pu essayer de tromper Bob soit en donnant un graphique qui a un cycle hamiltonien connu mais qui n'est pas isomorphe à sa clé publique, soit en lui donnant son graphique de clé publique avec les étiquettes supprimées mais sans connaître le Cycle hamiltonien. Elle parierait que Bob ferait le mauvais choix. En supposant que Bob ait vraiment fait son choix au hasard, cette astuce aurait 50% de chances de succès.

L'échange ci-dessus est donc répété avec un graphique différent sans étiquette. Après rounds du protocole, la probabilité qu'Alice réussisse à tromper Bob sur tous les rounds est de , ce qui converge très rapidement vers "aussi certain que vous devez l'être".$n$$2^{-n}$

Bien entendu, ce n'est pas du tout un système pratique en l'état. De plus, vous pouvez faire certaines choses évidentes pour le rendre plus sûr. Par exemple, au lieu d'Alice d'envoyer à Bob un graphique non étiqueté, elle pourrait simplement en envoyer un hachage. Lorsque Bob répond, elle peut alors envoyer le graphique, et Bob peut vérifier que le graphique correspond.

Néanmoins, vous pouvez en principe créer un cryptosystème, même s'il n'est pas terriblement utile.