# 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...

• Please see this. crypto.stackexchange.com/questions/72237/… Jul 29 '19 at 23:38
• If there are multiple answers and you can not narrow them down to one, it may not be an attack. Jul 30 '19 at 23:12
• If you have some program,please upload to gist of GitHub. Jul 30 '19 at 23:17
• Is this a total search version of an algorithm for solving simultaneous equations? Aug 10 '19 at 9:27
• @cryptomania: nah, instead, it makes a guess at how X permutes one element, and then immediately deduces a rather large number of other element permutations (or finds a contradiction); it turns out that only a handful of correct guesses gives you the entire permutation... Aug 10 '19 at 11:26