Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 23 down vote accepted

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

share|improve this answer
8  
Possibly also worth noting that each conjugate occurs the same number of times, so it really is 0 information gained. –  Harry Altman Aug 21 '10 at 3:31
    
Excellent, that's good news for me! (and thanks for the great answer!) –  Douglas S. Stones Aug 21 '10 at 5:29
3  
@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 '10 at 11:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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