DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.30

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

Authors: Kazumasa Shinagawa, Kazuki Kanai, Kengo Miyamoto, and Koji Nuida

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

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.

Cite as

Kazumasa Shinagawa, Kazuki Kanai, Kengo Miyamoto, and Koji Nuida. How to Covertly and Uniformly Scramble the 15 Puzzle and Rubik’s Cube. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shinagawa_et_al:LIPIcs.FUN.2024.30,
  author =	{Shinagawa, Kazumasa and Kanai, Kazuki and Miyamoto, Kengo and Nuida, Koji},
  title =	{{How to Covertly and Uniformly Scramble the 15 Puzzle and Rubik’s Cube}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.30},
  URN =		{urn:nbn:de:0030-drops-199385},
  doi =		{10.4230/LIPIcs.FUN.2024.30},
  annote =	{Keywords: Card-based cryptography, Uniform cyclic group factorization, Secure random instance generation, The 15 Puzzle, Rubik’s Cube}
}

Search Results

Documents authored by Kanai, Kazuki

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

Abstract

Cite as

Thanks for your feedback!

Could not send message