1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I assume that "easy" here means something like "polynomial in $\log r$"? $\endgroup$ – Ilmari Karonen Jul 29 at 11:05
  • $\begingroup$ r is large integer.and if it is easy to find r,I want to know how to solve this problem. $\endgroup$ – cryptomania Jul 29 at 11:15
  • 1
    $\begingroup$ 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".) $\endgroup$ – Ilmari Karonen Jul 29 at 11:21
  • $\begingroup$ 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. $\endgroup$ – cryptomania Jul 29 at 11:32
3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Please see this too.crypto.stackexchange.com/questions/72260/… $\endgroup$ – cryptomania Jul 30 at 4:26
  • $\begingroup$ 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. $\endgroup$ – poncho Jul 30 at 12:02
  • $\begingroup$ Good point. Either some earlier revision of the question mentioned $(AB)^r$ or I dreamed it. $\endgroup$ – Mikero Jul 30 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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