Question

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

Answer 1

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