Suppose we have two permutations $\alpha$ and $\beta$ (of a set $S$ of size $|S|=n$), and I know $\alpha$ and the cycle structure of $\alpha\beta$. But I don't know $\beta$.
Can I find a permutation $\gamma \neq \alpha$ such that $\gamma\beta$ has the same cycle structure of $\alpha\beta$?
This is an avenue of attack for a secret sharing scheme I'm thinking about. Basically, I want to lie about my permutation to fool another participant.
If the above is not possible deterministically, I could pick one at random. I can improve my chance over picking uniformly at random, by choosing $\gamma$ to have the same sign as $\alpha$. Can I do better?
I have a particular cycle structure in mind (two $(n/2)$-cycles), if it makes any difference. In the secret sharing scheme $\beta$ is chosen uniformly at random from $\mathrm{Sym}(S)$.
No that is not possible except $\gamma$ being a cyclic shift of $\alpha$ (which is essentially the same permutation).
The reason is the set of all permutations form the symmetric group $S_n$ (where $n$ is the size of your alphabet set). Now you are trying for $\gamma \beta = \alpha \beta$. But $\beta$ will have an inverse (since it belongs to the group $S_n$) so cancellation law forces you to have $\alpha=\gamma$.
However if you want $\beta\gamma = \alpha \beta$, then you can go with any conjugates of $\alpha$.