Efficient Generation of a Card-Based Uniformly Distributed Random Derangement

Soma Murata, Daiki Miyahara, Takaaki Mizuki, Hideaki Sone

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)

Abstract

Consider a situation, known as Secret Santa, where n players wish to exchange gifts such that each player receives exactly one gift and no one receives a gift from oneself. Each player only wants to know in advance for whom he/she should purchase a gift. That is, the players want to generate a hidden uniformly distributed random derangement. (Note that a permutation without any fixed points is called a derangement.) To solve this problem, in 2015, Ishikawa et al. proposed a simple protocol with a deck of physical cards. In their protocol, players first prepare n piles of cards, each of which corresponds to a player, and shuffle the piles. Subsequently, the players verify whether the resulting piles have fixed points somehow: If there is no fixed point, the piles serve as a hidden random derangement; otherwise, the players restart the shuffle process. Such a restart occurs with a probability of approximately 0.6. In this study, we consider how to decrease the probability of the need to restart the shuffle based on the aforementioned protocol. Specifically, we prepare more piles of cards than the number n of players. This potentially helps us avoid repeating the shuffle, because we can remove fixed points even if they arise (as long as the number of remaining piles is at least n). Accordingly, we propose an efficient protocol that generates a uniformly distributed random derangement. The probability of the need to restart the shuffle can be reduced to approximately 0.1.

Original language English WALCOM Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Proceedings Ryuhei Uehara, Seok-Hee Hong, Subhas C. Nandy Springer Science and Business Media Deutschland GmbH 78-89 12 9783030682101 https://doi.org/10.1007/978-3-030-68211-8_7 Published - 2021 15th International Conference on Algorithms and Computation, WALCOM 2021 - Virtual, OnlineDuration: 2021 Feb 28 → 2021 Mar 2

Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12635 LNCS 0302-9743 1611-3349

Conference

Conference 15th International Conference on Algorithms and Computation, WALCOM 2021 Virtual, Online 21/2/28 → 21/3/2

Keywords

• Card-based cryptography
• Derangement (Permutation without fixed points)