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

6more comments