# How hard is it to solve for $P$ in $A = PBP^{-1}$?

From graph isomorphism, we know that two graphs A and B are isomorphic if there is a permutation matrix P such that $A = P \times B \times P^{-1}$

So, to solve the problem, if two graphs are isomorphic, we need to find such a permutation matrix P. The problem is believed to be NP (and NP complete for the case of subgraph isomorphism). However, I found an example to solve for P which seemed promising to me and can be found in http://en.wikipedia.org/wiki/Permutation_matrix in section: solving for P.

The confusion I have now is, does that work for larger matrices? very large? am I right the above equation is hard to solve and can be candidate for a cryptographic system?

• Migrating to CS so you will hopefully get the answers you are looking for.
– mikeazo
Apr 25 '13 at 14:55

Graph isomorphism has been well-studied. A short summary: the graph isomorphism problem is not known to be in P (there are no known polynomial-time algorithms), but it is not believed to be NP-complete. There are heuristic algorithms for graph isomorphism that work extremely well on most instances that arise in practice. Read the Wikipedia page on graph isomorphism for more.

As for your particular proposed approach: the Wikipedia page you linked to already explains why that method does not work in general. That method only works if there are no repeated eigenvalues in the matrix corresponding to the adjacency graph. Therefore, it will fail for graphs where there are repeated eigenvalues. Such graphs cannot be ignored. Consequently, that method may work for some graphs but it will fail (or work poorly) for other graphs, so it is not a general solution.

Graph isomorphism is not a good candidate for a basis for a cryptographic system, for two reasons. First, existing heuristic algorithms are very good at solving the problem in practice, and it's not clear how to generate hard instances of graph isomorphism. Second, and more seriously, to be useful for cryptography, we need to not only have a hard problem; we need to have a "hidden trapdoor" that the creator of the public key can embed, which makes the problem easy for the creator, but which is hard for anyone else to detect. No one knows how to embed such a "hidden trapdoor" into the graph isomorphism problem.

As D.W. rightly notes, graph isomorphism is not known to be in P, and believed not to be NP-hard. Moreover, many believe it to be in BQP, but this has not been proven. That puts it in the same category as other problems on which cryptosystems typically rely for their security, such as prime factoring and the discrete log problem, both of which are known to be in BQP. (I don't know where the elliptic curve inverse multiplication problem or whatever it's called sits with respect to BQP, but it wouldn't surprise me in the least if all of these cryptographically useful problems turned out to be equivalent in some sense.)

It's true that we don't know of graph isomorphism problems for which the solution is "hard". However, let's assume for a moment that we did. Then yes, you can use it for cryptography.

As an example, let's look at a zero-knowledge proof key system based on graph isomorphism.

Alice's private key is a labelled graph (the labels can just be integers) which has been constructed such that it is "hard" to check a graph isomorphism for, and it contains a Hamiltonian cycle that it is "hard" to find. Her public key is just the labelled graph, with no information about the Hamiltonian cycle. Note that deriving the private key from the public key requires solving the Hamiltonian cycle problem, which is NP-hard and, we assume, is hard for this graph in particular.

Alice wants to convince Bob that she knows a Hamiltonian cycle in the graph, without actually giving him the Hamiltonian cycle. Here's how she does it.

Alice sends Bob an unlabelled graph. She offers him a choice: Either she will reveal the labels, or she will reveal a Hamiltonian cycle in the graph. Bob flips a coin (or makes a decision by some other means) as to which one he wants, and Alice does whichever of the two that Bob asks.

If Bob asked for the labels to be revealed, he can easily verify (in linear time) that the resuling labelled graph is the same as Alice's public key, but can't find a Hamiltonian cycle because that would be NP-hard. If, on the other hand, Bob asked for the Hamiltonian cycle, he can easily verify (again, in linear time) that the resulting unlabelled graph does indeed contain a Hamiltonian cycle, but he can't verify that it's Alice's public key graph, because graph isomorphism is (presumably) hard.

From Bob's point of view, Alice could have tried to trick Bob by either giving a graph which does have a known Hamiltonian cycle but is not isomorphic to her public key, or by giving him her public key graph with the labels removed but not knowing the Hamiltonian cycle. She would be betting on Bob making the wrong choice. Assuming that Bob really did make his choice randomly, then this trick would have a 50% chance of success.

So the above exchange is repeated with a different unlabelled graph. After $n$ rounds of the protocol, the probability of Alice successfully tricking Bob on all rounds is $2^{-n}$, which converges very quickly to "as certain as you need to be".

This is, of course, nowhere near a practical system as it stands. Moreover, there are some obvious things you can do to make it more secure. For example, instead of Alice sending Bob an unlabelled graph, she could just send a hash of it. When Bob replies, she could then send the graph, and Bob can check that the graph matches.

Nonetheless, you could create a cryptosystem out of it in principle, even if it's not terribly useful.

• there are no "hard instances" of problems - for every instance there is a linear time algorithm that solves it. what you need for crypto is a problem that's hard on average (and that's for minimal crypto); even if graph isomorphism turns out to be hard, it may not be hard on average. in fact P \neq NP is not known to imply the existence of problems which are hard on average for sampleable distributions. Apr 26 '13 at 12:06
• @Sasho Nikolov, thanks for the clarification. Apr 26 '13 at 23:37