## What can I say about the permutation $\alpha\beta$ if I know the permutation $\beta\alpha$?

I'm looking into a secret sharing scheme that has a secret permutation $\theta$ which has the cycle structure (n/2)+(n/2) (i.e. two (n/2)-cycles).

The permutation $\theta$ is decomposed into two permutations $\alpha$ and $\beta$, where $\alpha$ is generated uniformly at random. So with knowledge of both $\alpha$ and $\beta$, we can find $\theta$, while with knowledge of $\alpha$ xor $\beta$, we cannot find $\theta$ (although, we could guess).

At this point, I want to make public $\beta\alpha(L)$ (L is actually a Latin square, but this is not too relevant for the question I want to ask). It is possible that an attacker could find $\beta\alpha$ from $\beta\alpha(L)$. However, I worry that knowledge of $\beta\alpha$ might give information about $\theta$.

If I know $\theta=\alpha\beta$, and I'm given the permutation $\beta\alpha$, what can I say about $\theta$? (without a priori knowledge of $\alpha$, $\beta$ or $\theta$)

-

## 1 Answer

$\theta$ could be any permutation of the form $\alpha (\beta \alpha) \alpha^{-1}$; in other words, it could be any permutation conjugate to $\beta \alpha$, so knowing $\beta \alpha$ tells you only the cycle type of $\theta$, no more and no less. Since you already specified the cycle type this means an attacker gains no information (assuming $\alpha$ and $\beta$ really are chosen randomly).

-
Possibly also worth noting that each conjugate occurs the same number of times, so it really is 0 information gained. – Harry Altman Aug 21 2010 at 3:31
Excellent, that's good news for me! (and thanks for the great answer!) – Douglas S. Stones Aug 21 2010 at 5:29
@DSS: If you like it, put a ring on...um, I mean please accept it. (If it helps, in my opinion this is indubitably the correct answer.) – Pete L. Clark Aug 21 2010 at 11:05