# Would a Rubik's cube be a trapdoor function?

It's easy to scramble a Rubik's cube but it is hard to solve, unless you know the algorithms for solving it. This makes it a trapdoor function, correct?

• No, it does not. Scrambling a Rubik is the same as symmetrical encryption. – ThoriumBR Feb 1 '16 at 14:02
• But I know an algorithm to solve it without knowing the "encryption key" of the scramble. – Hurricane996 Feb 1 '16 at 14:06
• The algorithm to solve the Rubik can be considered bruteforcing it, while doing the shuffle backwards would be the proper decryption. – ThoriumBR Feb 1 '16 at 14:22
• Really? I thought you would do – Hurricane996 Feb 1 '16 at 15:16
• The algorithm to solve a cube is not brute forcing it — trying every possible permutation is. The algorithm to solve a cube is equivalent to a catastrophic known-plaintext cryptanalytic attack against the "Rubiks cipher". – Stephen Touset Feb 1 '16 at 22:54

## 2 Answers

It might be a viable example for explaining the concept of a trapdoor function to a layman without a computer science or math background. But from a CS standpoint this is only half-true.

For a low number of n where n is the number of rotate-operations performed on the cube, it is true that finding a solution for the cube is more computationally expensive than applying the rotations. But with very high values of n this might change. It was proven that any rubic's cube configuration can be solved with 20 moves or less, and finding that 20 move sequence might in fact be faster than applying the "correct" sequence.

A rubik's cube is an NP problem. It is difficult to find a solution to the problem but it is very easy to verify correctness of the solution, by just rotating the cube and checking that all sides have matching colours.

Yes, there is a widely known solution for the 3 * 3 * 3 rubik's cube. You can solve it in 20 moves because you have memorised the solution. However, there is no general solution for an n * n * n rubik's cube and finding one is terribly difficult.