10
$\begingroup$

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

$\endgroup$
0

1 Answer 1

25
$\begingroup$

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

$\endgroup$
3
  • 9
    $\begingroup$ Possibly also worth noting that each conjugate occurs the same number of times, so it really is 0 information gained. $\endgroup$ Aug 21, 2010 at 3:31
  • $\begingroup$ Excellent, that's good news for me! (and thanks for the great answer!) $\endgroup$ Aug 21, 2010 at 5:29
  • 3
    $\begingroup$ @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.) $\endgroup$ Aug 21, 2010 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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