5
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ Crossposted to crypto: crypto.stackexchange.com/questions/34198/… $\endgroup$
    – joro
    Nov 17, 2021 at 13:14
  • $\begingroup$ This is a special case of the Ko-Lee key exchange. iacr.org/archive/crypto2000/18800166/18800166.pdf $\endgroup$ Nov 17, 2021 at 14:04
  • $\begingroup$ This protocol can be trivially generalized in a couple of different ways: Alice can choose two integers $X_{A},Y_{A}$, and her public key will be $P_{0}^{X_{A}}M(G)P_{0}^{Y_{A}}$. Bob can do something similar. This generalization will no longer be based on graph isomorphism. $\endgroup$ Nov 17, 2021 at 14:08
  • $\begingroup$ @JosephVanName Thanks. Is the special case of Q2 also known? Even if we have a GI oracle the resulting X will not be solution to the crypto problem in general? Basically if we compute log(pubA) the log need not be power of P_0? $\endgroup$
    – joro
    Nov 17, 2021 at 14:14
  • 2
    $\begingroup$ So I think that I can break this protocol without using any linear algebra using the cycle structure of permutations. Can you post a link containing the public parameters and the public keys, so that I may break it? $\endgroup$ Nov 17, 2021 at 14:35

2 Answers 2

4
$\begingroup$

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:

  1. 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.

  2. 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.

  3. 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.

$\endgroup$
3
  • $\begingroup$ Thanks :) so you broke the computational Diffie Hellman problem (CDH) without breaking the private keys, right? $\endgroup$
    – joro
    Nov 19, 2021 at 9:58
  • $\begingroup$ I have another question about graph isomorphism and your result about the computational diffie-hellman: mathoverflow.net/questions/409045/… $\endgroup$
    – joro
    Nov 21, 2021 at 13:49
  • $\begingroup$ Sorry about questioning your answer, but I think solving CDH might break graph isomorphism: mathoverflow.net/questions/409116/… $\endgroup$
    – joro
    Nov 22, 2021 at 13:34
2
$\begingroup$

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}$.

  1. 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.

  2. 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}).$$

$\endgroup$
1
  • $\begingroup$ Thanks. Your answers are closely related to graph isomorphism (GI). GI is at most subexponential and it is open problem if it is polynomial. Have you tried to solve GI or some special cases of GI? $\endgroup$
    – joro
    Nov 23, 2021 at 15:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.