# A Rubik’s Cube puzzle relevant for post-quantum cryptography ### 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 Mediterranean
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.