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

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$$?

• I assume that "easy" here means something like "polynomial in $\log r$"? – Ilmari Karonen Jul 29 '19 at 11:05
• r is large integer.and if it is easy to find r,I want to know how to solve this problem. – cryptomania Jul 29 '19 at 11:15
• My point was that there's an obvious brute force solution method that requires $\Theta(r)$ matrix multiplications. Presumably that doesn't qualify as "easy", or you wouldn't be asking this, so I was just trying to get you to clarify what does count as "easy" for you. (On the other hand, $A^r B^r$ can be calculated from $A$, $B$ and $r$ in $\Theta(\log r)$ multiplications using e.g. the square-and-multiply algorithm, so presumably that is "easy".) – Ilmari Karonen Jul 29 '19 at 11:21
• We apologize for not being an accurate question. I would like to know r when A, B, C = A ^ r B ^ r is public and r is a secret integer. – cryptomania Jul 29 '19 at 11:32

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.

• That means that $A ^ rB ^ r$ can not be used for public key cryptography. Thank you very much. – cryptomania Jul 30 '19 at 12:48

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

• Please see this too.crypto.stackexchange.com/questions/72260/… – cryptomania Jul 30 '19 at 4:26
• Actually, because permutations do not commute, given an Oracle to find $r$ for $A^r$, that doesn't immediately give you an Oracle to find $r$ for $A^r B^r$ (as the cycles for $A$ and $B$ generally don't line up). That said, it turns out that the separate cycle structures of $A$ and $B$ are useful to deducing $k_i$ for the various cycles (and thus $r$ as you indicated); it's just not quite as straight-forward as you indicated. – poncho Jul 30 '19 at 12:02
• Good point. Either some earlier revision of the question mentioned $(AB)^r$ or I dreamed it. – Mikero Jul 30 '19 at 14:46