If conjugate search problem of permutation is difficult , then there are next cryptosystem will appear.

A=XYX−1,B=XZX−1,Y and Z are public key.And X is secret permutation. then encryption is C=YZZYZYYZY... at random,and D=ABBABAABA follow to C. c=H(C)+m. Bob send D and c as cipher text.

decode Alice calculate XDX−1=C,and m=H(C)+c,m is plain text.

Is this cryptography insecure?

  • 2
    $\begingroup$ Hmmm.. fairly unreadable $\endgroup$ – Chipotle Jul 30 '19 at 14:34
  • 1
    $\begingroup$ Please refrain from editing a question to completely change its meaning after answers have already been posted and accepted. $\endgroup$ – Ella Rose Aug 6 '19 at 14:05

As I pointed out in my answer to Is Permutation conjugate problem hard? , finding an $X$ given permutations $A, Y$ such that $A = XYX^{-1}$ is an easy problem.

Finding an $X$ that satisfies both $A = XYX^{-1}$ and $B = XZX^{-1}$ simultaneously should not be any more difficult (you can use the same base algorithm to search through both equations at the same time).

Hence, it is insecure.

  • $\begingroup$ I once thought about linear algebra attacks. My answer is that the dimension of permutations in that dimension is 1988. I solved it with a sagemath and got many results. The problem was that the permutation matrix had fewer linear equations than needed to solve this problem.I could not narrow down to one of the many possible permutations that came out. Therefore, if there are many possible permutation matrices, can you narrow down all possible answers? If this linear algebra attack doesn't work, what size permutation matrix do you need? Can you still solve this problem easily? $\endgroup$ – cryptomania Jul 30 '19 at 23:06
  • $\begingroup$ If you write some programs ,please upload to gist of GitHub. $\endgroup$ – cryptomania Jul 30 '19 at 23:08

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