The conjgacy problem

To solve an equation of the kind X+A-X=B in a non-commutative group is referred to as the conjugacy problem. Finding a solution to an instance of the conjugacy problem can be quite difficult, if we deal with a large group. The conjugacy problem represents the revearsal of a one-way function, similar to computing the descrete logarithm or factorizing a prime number product.

It is possible to define a key exchange algorithm similar to Diffie-Hellman based on the conjugacy problem. Contrary to Diffie-Hellman, this algorithm is considered secure against quantum computer attacks.

It is out of scope to explain the non-commutative key exchange algorithm in this article. However, I will certainly cover it in my 44CON talk.

Further reading: How to Use a Rubik’s Cube for Encryption


Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

1 / 2

Kommentare (3)

  1. #1 Norbert
    29. Juli 2018

    It is clear, however, that a solution always exists.

    Why is that clear? At first glance, I cannot see why there must be a solution X for any given A, B. Very interesting problem, though!

  2. #2 Armin
    29. Juli 2018

    @Klaus: Did you choose A and B to be conjugate? Because a solution X only exists if A and B are conjugate.

    Counter example: let A=0, then B = X+A-X = X+0-X = X-X = 0. So you can’t choose B arbitrarily, B has to be also 0, which is the only conjugate of 0.

  3. #3 Klaus Schmeh
    29. Juli 2018

    @Armin: Sorry, you are right. The problem described is not solvable for all move sequences, but only for special ones. So, the puzzles are (probably) unsolvable.
    I will rethink this issue and write a new blog post soon.