# Are there any crypography schemes which rely on Graph Isomorphism not being in P?

Are there any cryptography schemes having correctness relying on Graph Isomorphism not being in P? If I should ask this question in the CS Theory area, I will migrate it.

Thanks.

• Nope, not that I know of. GI is not a great problem from which to build primitives, because it's been known for several decades that many (most) classes of graphs have a poly-time algorithm for deciding isomorphism. Apr 2, 2016 at 22:17
• Interestingly, though, graph non-isomorphism is a standard example of an interactive zero-knowledge proof for a language not in NP. If GI collapses to P, I think GNI goes with it, so we'll need a new example in our crypto textbooks. Apr 2, 2016 at 22:21
• As I understand it, GI is collapsed to P: dharwadker.org/tevet/isomorphism Apr 2, 2016 at 23:01
• @BrentKirkpatrick You may want to read cstheory.stackexchange.com/questions/32237/… before putting faith in random papers on the internet :) Apr 2, 2016 at 23:13
• Indeed, the paper at dharwadker.org/tevet/isomorphism is not credible. However, Babai - a highly respected theoretical computer scientist - has shown that Graph Isomorphism is in quasi-polynomial time arxiv.org/abs/1512.03547. This makes it very unsuitable for cryptographic applications (especially since the feeling is that it may very well be in $P$). Apr 3, 2016 at 6:32

There is an elegant example of zero knowledge proof for graph isomorphism. The prover sends a randomly relabled graph and the verifier requests mapping to one of the originals. It is a very simple to understand and prove zero knowledge proof. However I don't believe anyone ever used this for authentication or such. Obviously we now know graph isomorphism isn't hard after all making all these not very useful.

We got a cryptographic algorithm and computer implementation based on graph isomorphism.

An isomorphism between two graphs is a bijection between their vertices that pre serves the edges.

For a graph $$G$$, let $$M(G)$$ denote the adjacency matrix of $$G$$.

Two graphs $$G,H$$ are isomorphic iff there exist permutation matrix $$P$$ such that $$P M(G) P^{-1}=P M(G) P^T=M(H)$$.

Observe that $$P$$ need not be unique.

Consider the following Diffie Hellman key exchange scheme based on graph isomorphism.

Public parameters: graph $$G$$ of order $$n$$ with $$A=M(G)$$ and $$n \times n$$ permutation matrix $$P_0$$.

Alice chooses positive integer $$X_A$$ and set the private key the matrix $$privA=P_0^{X_A}$$. Alice make public her public key the matrix

$$pubA=privA \cdot A \cdot privA^T=P_0^{X_A} A P_0^{-X_A}$$.

Bob chooses positive integer $$X_B$$ and set the private key the matrix $$privB=P_0^{X_B}$$. Bob make public his public key the matrix $$pubB=privB \cdot A \cdot privB^T$$.

To compute shared secret, Allice computes $$M_1=privA \cdot pubB \cdot privA^T=P_0^{X_A+X_B} A P_0^{-X_A-X_B}$$.

To compute shared secret, Bob computes $$M_2=privB \cdot pubA \cdot privB^T=P_0^{X_A+X_B} A P_0^{-X_A-X_B}$$.

Since powers of permutation matrices commute, Allice and Bob know the shared secret $$M_1=M_2$$.

The public keys $$pubA,pubB$$ are adjacency matrices of isomorphic graphs, each of which is isomorphic to the public $$G$$.

Multiplicative discrete logarithm of permutation matrices is efficient since the group order is $$n$$-smooth, but we believe to break the algorithm adversary must solve $$X A X^T=pubA$$ for permutation matrix $$X$$

Q1 Is this algorithm at least as hard as graph isomorphism?

For permutation matrix $$X$$, the equation $$X A X^T = pubA$$ might have many solutions, which are isomorphism of the graph $$G$$ to itself. For example take $$G$$ to be the complete graph of order $$n$$. Then for all $$X$$, we have $$X A X^T=pubA=A$$. This case is trivial since the shared secret is $$A$$.

When experimenting, we got $$G=PaleyGraph(5)$$ and $$P_0$$ such that we had $$X A X^T=pubA$$, but the shared secret was incorrect.

Q2 are there choices of $$G$$, $$P_0$$ such the algorithm is harder than graph isomorphism?

• Crossposted to MO: mathoverflow.net/questions/408757/…
– joro
Nov 17, 2021 at 13:14
• This key exchange is insecure. The graph $M_{2}=(V_{2},E_{2})$ can be recovered since the edge sets $E_{2}\cap\{\{r,s\}\mid r\in R,s\in S\}$ can easily be produced by from the public information whenever $R,S$ are cycles in the permutation $P_{0}$. Nov 17, 2021 at 18:53
• On MO, I also posted an attack where a more general key exchange is broken using linear algebra. Nov 23, 2021 at 17:18
• mathoverflow.net/a/409594/22277 On MO, I have posted another attack that translates the problem of finding $X_{A}$ into a problem of solving a system of linear congruence equations. Nov 29, 2021 at 1:43

As far as I know there is no cryptographic scheme based on Graph isomorphism. The following is the key reasons.

The security of a cryptographic scheme largely depend on one-wayness of the underlying function. For a function to be one-way it's not just need to be hard for few NP instances but must be hard for a random instance. In other words it is very easy to find problems that are hard for very instance but easy for majority of instances . Such problems may not come under P but they arn't one way functions either. One such good example is the encryption scheme based on subset-sum problem, which was eventually broken due to the above specified reason.