# Graph-based key exchange

Alice and Bob fix a largish $$n$$, say $$n = 1000$$, and they publish a simple, undirected graph $$G$$ on $$n$$ vertices (more precisely, its adjacency matrix, or a similar form of representation). Moreover they publicly agree on some hash function $$h:\{0,1\}^*\to \{0,1\}^{1024}$$ (or some other constant number of output bits).

They also publicly agree on a large commutative subgroup of $$U\subseteq S_n$$, the symmetric group of permutations $$\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$$. Then:

1. Alice and Bob privately choose members of $$U$$, say $$\varphi$$ and $$\psi$$, respectively.

2. Alice publishes the adjacency graph of $$\varphi(G)$$, and Bob does the same with $$\psi(G)$$. It is computationally infeasible to compute $$\varphi,\psi$$ given $$G, \varphi(G), \psi(G)$$.

3. Alice secretly computes $$G_0=\varphi(\psi(G))$$, Bob secretly computes $$G_0 = \psi(\varphi(G))$$ -- and they end up with the adjacency matrix $$M_0$$ of the same graph, since $$\varphi,\psi\in U$$ commute.

4. Each computes $$h(M_0)$$, and so they end up with a common $$1024$$-bit key.

Problems with this approach:

1. Identifying a large and good commutative subgroup $$U\subseteq S_n$$.

2. The object exchanged, that is $$\varphi(G), \psi(G)$$ have the size $${\cal O}(n^2)$$ if $$n$$ is the number of vertices used for the graph.

Question. Has such a key exchange system been tried / implemented?

• What are you trying to do is this; take a large array (of size $1000^2$) randomly fill to 0s and 1s. and generate a permutation on this array as your public key. A Graph is redundant here. Instead, we choose a group where discrete logarithm is hard ( $g^x$ is a permutation in some settings). Nov 7, 2023 at 12:36