Diffie Hellman cryptography based on graph isomorphism? 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?

Per comments I have posted the implementation at https://pastebin.com/DSmYkdfC you can run it in a browser at sagemath.org
 A: This protocol as it is stated is broken using a quotient attack. I am going to explain this technique in as general of a context that I can (this idea should also break generalizations of this protocol).
Suppose that $X$ is a set. Let $G,H$ be monoids that act on $X$. Here
$G$ acts on $X$ on the left so that $gx\in X$ whenever $g\in G,x\in X$, and $H$ acts on $X$ on the right so that $xh\in X$ whenever $x\in X,h\in H.$ Suppose furthermore that if $g\in G,x\in X,h\in H$, then $(gx)h=g(xh)$.
Suppose $A_{L},B_{L}$ are submonoids of $G$ and $A_{R},B_{R}$ are submonoids of $H$ such that $ab=ba$ whenever $a\in A_{L},b\in B_{L}$ and $ab=ba$ whenever $a\in A_{R},b\in B_{R}$.
Consider the following key exchange algorithm. Here $x_{0}$ will be a publicly available element of $X$. Alice and Bob perform the following steps:

*

*Alice selects $a_{L}\in A_{L},a_{R}\in A_{R}$ and sends $a_{K}=a_{L}x_{0}a_{R}$ over a public channel to Bob.


*Bob selects $b_{L}\in B_{L},b_{R}\in B_{R}$ and sends $b_{K}=b_{L}x_{0}b_{R}$ over a public channel to Alice.


*The common key between Alice and Bob is $k=a_{L}b_{L}x_{0}a_{R}b_{R}$. Alice and Bob are able to produce this common key but (at least in principle) no other party should be able to produce this common key.
For security it is best that the structure $(G,X,H)$ is simple or at least subdirectly irreducible.
Suppose that there is a set $\simeq_{1},\dots,\simeq_{r}$ of congruences on the $3$-sorted structure $(X,G,H)$, and let $[v]_{r}$ denote the equivalence class containing $v$. Suppose furthermore that the mapping
$$\iota:X\rightarrow X/\simeq_{1}\times\dots\times X/\simeq_{r}$$ is injective. Then (except in the very unlikely case that $\iota$ is a one-way function) one can recover $k$ from the $([k]_{1},\dots,[k]_{r})$. Since each $(X,G,H)/\simeq_{i}$ is a quotient structure, it will be easier to compute $[k]_{i}$ and then recover $k$ from
$([k]_{1},\dots,[k]_{r})$.
In the case that $G,H$ are cyclic groups of the subgroup of $n\times n$- permutation matrices and where $X$ is a submonoid of $M_{n}(F)$ for some field $F$, then there are at most $n^{2}$ congruences $\simeq_{1},\dots,\sigma_{w}$ on $(G,X,H)$ where
$A_{L}/\simeq_{i},B_{L}/\simeq_{i},A_{R}/\simeq_{i},B_{R}/\simeq_{i}$ all have cardinality at most $n$ (these congruences correspond to the pairs $(c,d)$ where $c$ is a cycle in the generator of $G$ and $d$ is a cycle in the generator of $H$). In this case, the problem of solving for $[k]_{i}$ for $1\leq i\leq w$ is easy and the process of recovering $k$ from $([k]_{1},\dots,[k]_{w})$ is also easy.
A: One can also completely break this key exchange (and a more general key exchange algorithm) using linear algebra. Consider the following key exchange algorithm.
Suppose that $\mathcal{A}_{L},\mathcal{B}_{L}$ are sets of $m\times m$-matrices and
$\mathcal{A}_{R},\mathcal{B}_{R}$ are sets of $n\times n$-matrices. Let
$C$ be a publicly available $m\times n$-matrix. Suppose furthermore that $AB=BA$ whenever $A\in\mathcal{A}_{L},B\in\mathcal{B}_{L}$.

*

*Alice selects $A_{L}\in\mathcal{A}_{L},A_{R}\in\mathcal{A}_{R}$ and sends
$K_{a}=A_{L}CA_{R}$ to Bob over a public channel.


*Bob selects $B_{L}\in\mathcal{B}_{L},B_{R}\in\mathcal{B}_{R}$ and sends
$K_{b}=B_{L}CB_{R}$ to Bob over a public channel.
The secret key is $K=A_{L}B_{L}CA_{R}B_{R}$. Both Alice and Bob are able to produce the secret key.
I claim that one can compute $K$ from the public information just by knowing a little bit of linear algebra.
Define bilinear mappings
$$L_{a}:\langle\mathcal{A}_{L}\rangle\times\langle\mathcal{A}_{R}\rangle\rightarrow 
\text{Hom}(M_{m,n}(K),M_{m,n}(K))$$ by letting $L(A_{L},A_{R})(C)=A_{L}CA_{R}$.
Then $L_{a}$ is a linear mapping. Therefore, there is a linear mapping
$$M_{a}:\langle\mathcal{A}_{L}\rangle\otimes\langle\mathcal{A}_{R}\rangle\rightarrow\text{Hom}(M_{m,n}(K),M_{m,n}(K))$$ defined by letting
$M_{a}(A_{L}\otimes A_{R})=L_{a}(A_{L},A_{R})$
There is also a linear mapping $$M_{b}:\langle\mathcal{A}_{L}\rangle\otimes\langle\mathcal{A}_{R}\rangle\rightarrow\text{Hom}(M_{m,n}(K),M_{m,n}(K))$$ defined by $M_{b}(B_{L}\otimes B_{R})(C)=B_{L}CB_{R}$ whenever $B_{L}\in\langle\mathcal{B}_{L}\rangle$ and $B_{R}\in\langle\mathcal{B}_{R}\rangle.$
Then observe that $L_{a}(\mathbf{x})M_{b}(\mathbf{y})=M_{b}(\mathbf{y})L_{a}(\mathbf{x})$ whenever $\mathbf{x}\in\langle\mathcal{A}_{L}\rangle\otimes\langle\mathcal{A}_{R}\rangle$,
$\mathbf{y}\in\langle\mathcal{B}_{L}\rangle\otimes\langle\mathcal{B}_{R}\rangle$.
One then uses linear algebra to find
$\mathbf{x}\in\langle\mathcal{A}_{L}\rangle\otimes\langle\mathcal{A}_{R}\rangle$ and
$\mathbf{y}\in\langle\mathcal{B}_{L}\rangle\otimes\langle\mathcal{B}_{R}\rangle$ that satisfy the equations $L_{a}(\mathbf{x})(C)=K_{a}$ and
$L_{b}(\mathbf{y})(C)=K_{b}$.
Therefore, one can recover the key $K$ two ways since
$$K=L_{a}(\mathbf{x})(K_{b})=L_{b}(\mathbf{y})(K_{a}).$$
