patternMinor
How hard is it to solve for $P$ in $A = PBP^{-1}$?
Viewed 0 times
pbphardforsolvehow
Problem
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?
$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?
Solution
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 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.
Context
StackExchange Computer Science Q#11553, answer score: 6
Revisions (0)
No revisions yet.