$\DeclareMathOperator\ora{ora}$Let $A\_0$ be the adjacency matrix of graph $G$ and $P\_0$
permutation matrix of multiplicative order $\rho$.


Let $X$ be positive integer and $B\_0=P\_0^X A\_0 P\_0^{-X}$.



> 
> Q1 Given $A\_0,P\_0,B\_0$ can we find $X$ efficiently?
> 
> 
> 


Positive answer need not mean graph isomorphism is efficient,
since in GI we don't know $P\_0$.


Related problem:


Given $P\_0$ and $C\_0=P\_0^Y$ we can find $Y$ efficiently since
$\rho$ is divisor of factorial $n$ and $n$-smooth.


Another relation:
Assume $\ora(U)$ is an oracle which computes $P\_0^{U X} A\_0 P\_0^{-U X}$
given integer $U$.
Assume $X=d d'$ where $d$ is factor of $\rho$.
Then $\ora(\frac{\rho}{d})=P\_0^{\rho d'} A\_0 P\_0^{-\rho d'}=A\_0$ and we have information about $X$.
Repeat the same idea for other factors of $\rho$ and multiplying
by small powers of $P\_0$ to get congruences and $X$ via crt.


In an [answer](https://mathoverflow.net/questions/408757/diffie-hellman-cryptography-based-on-graph-isomorphism) Joseph Van Name appears to claim the following
which is very close to computational diffie-hellman problem (CDH).


Given $P\_0^X A\_0 P\_0^{-X}$ and $P\_0^Y A\_0 P\_0^{-Y}$, he can efficiently
compute $P\_0^{X+Y} A\_0 P\_0^{-X-Y}$


Setting $X=Y$, he can double $P\_0^X, P\_0^{2X},P\_0^{4X} \ldots P\_0^{2^kX}$ and by repeated doublings,
he can compute $\ora(U)$.



> 
> Q2 Does Joseph's attack works for Q1?
> 
> 
> 



> 
> Q3 Can we drop knowing $P\_0$ and find $P\_0^X$ efficiently from only $A\_0,B\_0$?
> 
> 
> 



Relation graph isomorphism to discrete logarithm
Yes. We can efficiently find all integer solutions $X$ to the equation $B\_{0}=P\_{0}^{X}A\_{0}P\_{0}^{-X}$ since we can either conclude that there is no integer $X$ with $B\_{0}=P\_{0}^{X}A\_{0}P\_{0}^{-X}$ or we can show that $B\_{0}=P\_{0}^{X}A\_{0}P\_{0}^{-X}$ precisely when $X$ satisfies a system of linear congruence equations.


Suppose that the permutation corresponding to $P\_{0}$ can be written as a product of $r$ disjoint cycles of lengths $n\_{1},\dots,n\_{r}$. Without loss of generality, we may therefore assume that $P\_{0}$ is a block matrix $(P\_{i,j})\_{1\leq i\leq r,1\leq j\leq r}$ where each entry $P\_{i,j}$ is the $n\_{i}\times n\_{j}$-zero matrix whenever $i\neq j$ and where each $P\_{i,i}$ is an $n\_{i}\times n\_{i}$-permutation matrix corresponding to the cycle permutation.


Let us make $A\_{0},B\_{0}$ as well into block matrices. Suppose that $A\_{0}=(A\_{i,j})\_{1\leq i\leq r,1\leq j\leq r}$ and
$B\_{0}=(B\_{i,j})\_{1\leq i\leq r,1\leq j\leq r}$ where each $A\_{i,j},B\_{i,j}$ is an $n\_{i}\times n\_{j}$-matrix.


Then $$P\_{0}^{X}A\_{0}P\_{0}^{-X}=(P\_{i,i}^{X}A\_{i,j}P\_{j,j}^{-X})\_{1\leq i\leq r,1\leq j\leq r}.$$ Therefore, $P\_{0}^{X}A\_{0}P\_{0}^{-X}=B\_{0}$ if and only if
$B\_{i,j}=P\_{i,i}^{X}A\_{i,j}P\_{j,j}^{-X}$ for each $i,j$.


If there exists $i,j$ where $B\_{i,j}\neq P\_{i,i}^{X}A\_{i,j}P\_{j,j}^{-X}$ for all integers $X$ with $0\leq X<\text{Lcm}(m\_{i},m\_{j})$, then there does not exist an integer $X$ with $B\_{i,j}\neq P\_{i,i}^{X}A\_{i,j}P\_{j,j}^{-X}$, and therefore the equation $B\_{0}=P\_{0}^{X}A\_{0}P\_{0}^{-X}$ has no solution.


On the other hand, if for each pair $i,j$, there exists an integer $X\_{0}$ with $0\leq X\_{0}<\text{Lcm}(m\_{i},m\_{j})$ where $B\_{i,j}=P\_{i,i}^{X\_{0}}A\_{i,j}P\_{j,j}^{-X\_{0}}$, then
$$H=\{Y\in\mathbb{Z}\mid B\_{i,j}=P\_{i,i}^{X}B\_{i,j}P\_{j,j}^{-X}\}$$ is a subgroup of $\mathbb{Z}$ of index at most $\text{Lcm}(m\_{i},m\_{j})$. If $v\_{i,j}$ is the index of $H$, and $u\_{i,j}=X\_{0}$, then
$B\_{i,j}=P\_{i,i}^{X}A\_{i,j}P\_{j,j}^{-X}$ if and only if $X=u\_{i,j}\mod v\_{i,j}.$ Therefore, $P\_{0}^{X}A\_{0}P\_{0}^{-X}=B\_{0}$ if and only if
$X=u\_{i,j}\mod v\_{i,j}$ for $1\leq i\leq r,1\leq j\leq r.$ One can easily find the (possibly empty) set of all integer solutions $X$ to the equation $B\_{0}=P\_{0}^{X}A\_{0}P\_{0}^{-X}$.


