How to Covertly and Uniformly Scramble the 15 Puzzle and Rubik’s Cube

A combination puzzle is a puzzle consisting of a set of pieces that can be rearranged into various combinations, such as the 15 Puzzle and Rubik’s Cube. Suppose a speedsolving competition for a combination puzzle is to be held. To make the competition fair, we need to generate an instance (i.e., a state having a solution) that is chosen uniformly at random and unknown to anyone. We call this problem a secure random instance generation of the puzzle. In this paper, we construct secure random instance generation protocols for the 15 Puzzle and for Rubik’s Cube. Our method is based on uniform cyclic group factorizations for finite groups, which is recently introduced by the same authors, applied to permutation groups for the puzzle instances. Specifically, our protocols require 19 shuffles for the 15 Puzzle and 43 shuffles for Rubik’s Cube.