2026-07-26T17:14:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19938 2024-05-29T09:43:30Z ddc:004 open_access

How to Covertly and Uniformly Scramble the 15 Puzzle and Rubik’s Cube Shinagawa, Kazumasa Kanai, Kazuki Miyamoto, Kengo Nuida, Koji Card-based cryptography Uniform cyclic group factorization Secure random instance generation The 15 Puzzle 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kazumasa Shinagawa and Kazuki Kanai and Kengo Miyamoto and Koji Nuida 2024 Is Part Of LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2024.30 urn:nbn:de:0030-drops-199385 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.30 eng https://creativecommons.org/licenses/by/4.0/legalcode