From the product of two permutation matrices raised to the same power, is it easy to find the power?

Question

Let $A$ and $B$ be two public permutation matrices. If $r$ is a secret power of large number, can we easily find $r$ from $A^rB^r$?

Answer 1

It's an easy problem; I'll give an outline of how it can be solved.

The key is the cycle structure. Let us look how one cycle in $A$ is handled.

This cycle is a set of $k$ elements $(a_1, a_2, …., a_k)$; when $A^r$ does is take each of these elements and advance them $r \bmod k$ places in the permutation. And, note that, no matter what the value of $r$ is, $a_i$ will be mapped to some $a_j$, for some $j$.

Now, $B$ has (likely) a completely distinct cycle structure; the value $a_1$ may be a part of some cycle $(b_1, b_2, …, b_x)$ (for $a_1 = b_1$), while the value $a_2$ may be part of some distinct cycle $(c_1, c_2, …, c_y)$ (for $(a_2 = c_1)$). And, again, no matter what the value of $r$ is, if we start $B$ in one particular cycle, we'll never leave it.

Now, we take the elements of the cycle $a_1, a_2, …, a_k$, and see:

• What cycles in $B$ they are a part of

• What cycles in $B$ is $A^r B^r (a_i)$ (for various $i$ are a part of

If a potential value of $r \bmod k$ makes a value $a_i$ to $a_j$, and $a_j$ is a part of one $B$-cycle, while $A^r B^r (a_i)$ is a part of a different one, that value $r \bmod k$ is impossible.

The above logic should eliminate most of the possible values of $r \bmod k$ (assuming that the permutations were generated randomly); there is a second check possible (which depends on the relative ordering of the elements in a cycle) - you should be able to figure out the details yourself.

Answer 2

The product of two permutation matrices is itself a permutation matrix. So there's nothing special about its "factors" being public. You should consider a single public permutation matrix $A$ and finding $r$ from $A^r$.

Edit: oops, this was based on a misinterpretation of the question.

And there's nothing particularly special about it being a matrix. If $A$ is a permutation matrix corresponding to permutation $\pi$, then $A^r$ is the permutation matrix corresponding to $\pi$ composed with itself $r$ times. Let's call this permutation $\pi^{(r)}$.

So the question boils down to to the "discrete log" problem in a permutation group: given $\pi$ and $\pi^{(r)}$, find $r$. This problem is easy.

• First, observe that if $\pi$ is a simple cycle on $n$ items then $\pi^{(r)} = \pi^{(r \bmod n)}$. Since $n$ must be small in this problem, you can easily just "brute force" to determine $r$ mod $n$.

• Second, any permutation can be uniquely decomposed into disjoint cycles. The operation $\pi^{(r)}$ acts independently on all the cycles of $\pi$. So if $\pi$ is composed of cycles of length $k_1, k_2, \ldots$ then we can use the above trick on each cycle and learn $r \bmod k_1, r \bmod k_2$ and so on. Then you can use the CRT to solve for $r \bmod \textrm{lcm}(k_1,k_2,\ldots)$. And indeed, the order of $\pi$ will also be $L=\textrm{lcm}(k_1,k_2,\ldots)$ in the sense that $\pi^{(L)}$ is the identity permutation.

So you can efficiently identify $r$ as uniquely as is possible (mod $L$).