What can I say about the permutation $\alpha\beta$ if I know the permutation $\beta\alpha$? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T03:28:57Z http://mathoverflow.net/feeds/question/36251 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/36251/what-can-i-say-about-the-permutation-alpha-beta-if-i-know-the-permutation-be What can I say about the permutation $\alpha\beta$ if I know the permutation $\beta\alpha$? Douglas S. Stones 2010-08-21T02:54:02Z 2010-08-21T03:26:54Z <p>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).</p> <p>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).</p> <p>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$.</p> <blockquote> <p>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$)</p> </blockquote> http://mathoverflow.net/questions/36251/what-can-i-say-about-the-permutation-alpha-beta-if-i-know-the-permutation-be/36252#36252 Answer by Qiaochu Yuan for What can I say about the permutation $\alpha\beta$ if I know the permutation $\beta\alpha$? Qiaochu Yuan 2010-08-21T03:26:54Z 2010-08-21T03:26:54Z <p>$\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).</p>