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?

  • 2
    $\begingroup$ 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). $\endgroup$
    – kelalaka
    Nov 7, 2023 at 12:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.