The search was a little easier than that, as we knew how to solve every state in 20 moves, so the problem was proving some move that could be solved in 20 moves couldn't be done quicker in some unusual way. While that still took a while, the fact you knew the start and end limits how many moves you have to search.

Except that the transform is relatively easy to reverse (compared to prime factorization) because of the properties of edge and corner pieces and limitations on piece movement that make a kind of spectral analysis possible. Things get a little better if you increase the size of the cube. Things get interesting if you allow un-solvable states (there's a 2:1 ratio of positions that are not naturally reachable) if you include in the protocol something like "always encode any corner rotations first" but it still wouldn't really be strong enough for modern compute.

If you mean to use it exclusively as a real-world key transmission like with Cryptonomicon's Solitaire decks, the problem becomes finding the shortest path or whatever the protocol determines is the normalized form.

Not to rain on your parade, it's a fun approach to think about, like maybe if the properties of a specific face determine which rotations to perform next, and which face to look at next, in addition to being the nonce for decoding the next letter. But even something like that would be too complicated to expect a person to remember all of while not being complicated enough to fluster a computational approach. The nice thing about Solitaire is that it's reasonable to perform the algorithm in your head.

For me, any position which requires the full maximum 20 moves to solve would qualify as the perfect shuffle.

I wonder how many positions qualify (perhaps only 1 discounting symmetry as there is 1 fully solved cube, again discounting symmetry). But that’s a rabbit hole that I am not going down.

But I can appreciate the choice made in the article.