Is Permutation conjugate problem hard? Let $x$,$y$,$z$ be permutations. Then public key is $z=xyx^{−1}$ and $y$. Is permutation conjugate search problem easy? if yes, how to find $x$ from $z$ and $y$?
Let be a is Alice's secret key as large number,and X,Y,A=XaYX−a is public key.

encryption Bob pick at random number r,s and B=XrYX−r,C=XrAsX−r,and c=H(C)+m, and (B,c) is cipher text send to Alice.

decryption Alice calculate C=XaBX−a. Cause the discrete logarithm problem of permutation groups is weak,so Alice can calculate C from B. Finally Alice get plain text as m=H(C)+c.

I assume permutation dimension of X is 1988 and permutation is represented as array form.X's order have 256-bit integer.

Is this cryptosystem insecure ?
It looks like it can be solved quickly using a branch-and-bound procedure, assuming that the number of elements in the permutation is not excessively large.

(Notation: I'll use capital letters to specify permutations, and lower case letters to specify individual elements of the permutation); in addition, I'll take the convention that $XY$ means "apply the permutation $X$ to the elements, and then apply the permutation $Y$)

The algorithm is straight-forward; we know that $XY = ZX$, so:


We pick an arbitrary element of the permutation $a$ and assume that $X(a) = b$ (where $b$ is a previously output of $X$).  We then can deduce the value $XY(a) = d$ (where $d = Y(b)$).  In addition, we have $Z(a) = c$ (for some element $c$), and so we can then deduce $X(c) = d$.


Assuming that $c, d$ are previously unknown inputs/outputs of $X$, we reiterate the same logic, which will give us another pair $X(e) = f$.

We keep on doing this until it gives us a pair that we've seen before, or it gives an inconsistent pair (that is, it assigned the same $X(g)$ value to two different outputs, or it gives us a set $g \ne h, i$ with $X(g) = X(h) = i$

If it gives us an inconsistent pair, we drop back to the previous assumption that $X(a) = b$, and modify $b$, and restart our computation from there.

If it gives us a pair that we've seen before, and there are still unassigned inputs/outputs to $X$, we restart at the beginning, arbitrarily selecting a previously unassigned input/output pair.

This won't give a unique value of $X$; that's because there are multiple solutions, and this will pick one arbitrarily.



Update: I just wrote a quick (and fairly suboptimal) C program to do this; it could find a conjugate (where one existed) given two permutations over 10,000 elements in under a second...