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

  • $\begingroup$ Please see this. crypto.stackexchange.com/questions/72237/… $\endgroup$ Jul 29 '19 at 23:38
  • $\begingroup$ If there are multiple answers and you can not narrow them down to one, it may not be an attack. $\endgroup$ Jul 30 '19 at 23:12
  • $\begingroup$ If you have some program,please upload to gist of GitHub. $\endgroup$ Jul 30 '19 at 23:17
  • $\begingroup$ Is this a total search version of an algorithm for solving simultaneous equations? $\endgroup$ Aug 10 '19 at 9:27
  • $\begingroup$ @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... $\endgroup$
    – poncho
    Aug 10 '19 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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