Efficient Generation of a Card-Based Uniformly Distributed Random Derangement

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.

1 Introduction

Let $n\, (\ge 3)$ be a natural number, and consider a situation, known as Secret Santa, where n players $P_{1}, P_{2}, \ldots , P_{n}$ wish to exchange gifts such that each player receives exactly one gift and no one receives a gift from oneself. Every player wants to know in advance for whom he/she should purchase a gift. Mathematically, an assignment of a gift exchange can be regarded as a permutation, i.e., an element in $S_{n}$, which is the symmetric group of degree n; in this context, a permutation $\pi \in S_{n}$ indicates that a player $P_{i}$ for every i, $1 \le i \le n$, will purchase a gift for $P_{\pi (i)}$. Such a permutation $\pi \in S_{n}$ must not have any fixed points, i.e., $\pi (i) \ne i$ for every i, $1 \le i \le n$, to prevent each player from receiving a gift from himself/herself. Note that a permutation is called a derangement if it has no fixed point. Therefore, the players want to generate a uniformly distributed random derangement. Furthermore, to make the exchange fun, it is necessary for each player $P_{i}$ to know only the value of $\pi (i)$. Thus, we aim to generate a “hidden” uniformly distributed random derangement.

Physical cryptographic protocols are suitable for resolving this type of problem because they can be easily executed by using familiar physical tools without relying on complicated programs or computers.

1.1 Background

The problem of generating a hidden derangement was first studied by Crépeau and Kilian [2] in 1993. Since then, several solutions with physical tools have been proposed. (Refer to [17] for the non-physical solutions.) As practical protocols, Heather et al. [6] proposed a protocol with envelopes and fill-in-the-blank cards in 2014; Ibaraki et al. [7] proposed a protocol with two sequences of cards representing player IDs and gift IDs in 2016. The common feature of these two practical protocols is that the generated derangement is not uniformly distributed; it always includes a cycle of a specific length.

Let us focus on generating a uniformly distributed random derangement. A protocol that generates a uniformly distributed random derangement was proposed by Crépeau and Kilian [2] with a four-colored deck of $4n^{2}$ cards. Ishikawa, Chida, and Mizuki [8] subsequently improved the aforementioned protocol by introducing a pile-scramble shuffle that “scrambles” piles of cards. Their improved protocol, which we refer to as the ICM protocol hereinafter, uses a two-colored deck of $n^{2}$ cards. It is described briefly as follows. (Further details will be presented in Sect. 2.5).

• 1. Prepare n piles of cards, each of which corresponds to a player.

• 2. Apply a pile-scramble shuffle to the n piles to permute them randomly.

• 3. Check whether there are fixed points in the n piles somehow.

  • If there is at least one fixed point, restart the shuffle process, i.e., go back to Step 2.

  • If there is no fixed point, the piles serve as a hidden random derangement.

Thus, the ICM protocol is not guaranteed to terminate within a finite runtime, because it restarts the shuffle process whenever a fixed point arises. The probability that at least one fixed point appears in Step 3 is $1-\sum ^n_{k=0}{(-1)^{k}}/{k!}\approx 1-{1}/{e}\approx 0.63$ (where e is the base of the natural logarithm), which will be described later in Sect. 2.5.

In 2018, Hashimoto et al. [4] proposed the first finite-runtime protocol for generating a uniformly distributed random derangement by using the properties of the types of permutations. While their proposed protocol is innovative, its feasibility to be performed by humans has not been studied, as it requires a shuffle operation with a nonuniform probability distribution.

1.2 Contributions

In this study, we also deal with generating a uniformly distributed random derangement and propose a new card-based protocol by improving the ICM protocol. Specifically, we devise a method to reduce the probability of the need to restart in the ICM protocol. Recall that, after one shuffle is applied in Step 2, the ICM protocol returns to Step 2 with a probability of approximately 0.6. In card-based protocols, it is preferable to avoid repeating shuffle operations because players manipulate the deck of physical cards by hand. Here, we prepare more piles of cards than the number n of players, i.e., we prepare $n+t$ piles for some $t \ge 1$. This potentially helps us remove fixed points (if they arise); hence, we can reduce the probability of the need to restart the shuffle. In the same manner as the ICM protocol, the proposed protocol generates a hidden uniformly distributed random derangement. The probability of the need to restart the shuffle is reduced by increasing the number t of additional piles. Specifically, the probability of the need for such a restart can be reduced to approximately 0.1 by setting $t=3$.

The remainder of this paper is organized as follows. In Sect. 2, we introduce the notions of card-based cryptography, the properties of permutations, and the ICM protocol. In Sect. 3, we present our protocol. In Sect. 4, we demonstrate the relationship between the number t of additional piles and the probability of the need to restart the shuffle; we illustrate how the probability can be reduced by increasing the number t.

1.3 Related Works

Card-based cryptography involves performing cryptographic tasks, such as secure multi-party computations, using a deck of physical cards; since den Boer [1] first proposed a protocol for a secure computation of the AND function with five cards, many elementary computations have been devised (e.g., [11, 14]). For more complex tasks, millionaire protocols [9, 12, 13] that securely compare the properties of two players, a secure grouping protocol [5] that securely divides players into groups, and zero-knowledge proof protocols for pencil puzzles [3, 10, 15, 16, 18] were also proposed.

2 Preliminaries

In this section, we introduce the notions of cards and the pile-scramble shuffle used in this study, and the properties of permutations. Furthermore, we introduce the ICM protocol proposed by Ishikawa et al. [8].

2.1 Cards

In this study, we use a two-colored (black and red ) deck of cards. The rear sides of the cards have the same pattern . The cards of the same color are indistinguishable. Using n cards consisting of $n-1$ black cards and one red card, we represent a natural number i, $1 \le i \le n$, using a sequence such that the i-th card is red and the remaining cards are black:

If a sequence of face-down cards represents a natural number i according to the above encoding rule, we refer to it as a commitment to i and express it as follows:

2.2 Pile-scramble Shuffle

A pile-scramble shuffle is a shuffle operation proposed by Ishikawa et al. [8]. Let $(\mathsf {pile}_{1},\mathsf {pile}_{2},\ldots ,\mathsf {pile}_{n})$ be a sequence of n piles, each consisting of the same number of cards. By applying a pile-scramble shuffle to the sequence, we obtain a sequence of piles $(\mathsf {pile}_{\pi ^{-1}(1)},\mathsf {pile}_{\pi ^{-1}(2)},\ldots ,\mathsf {pile}_{\pi ^{-1}(n)})$ where $\pi \in S_{n}$ is a uniformly distributed random permutation. Humans can easily implement a pile-scramble shuffle by using rubber bands or envelopes.

2.3 Properties of Permutations

An arbitrary permutation can be expressed as a product of disjoint cyclic permutations. For example, the permutation

$$ \tau =\begin{pmatrix} 1 &{} 2 &{} 3 &{} 4 &{} 5 &{} 6 &{} 7 \\ 3 &{} 5 &{} 6 &{} 4 &{} 2 &{} 7 &{} 1 \end{pmatrix} $$

can be expressed as the product of three disjoint cyclic permutations $\tau _{1}=(4),\tau _{2}=(2 5),\tau _{3}=(1 3 6 7)$: $\tau =\tau _{1}\tau _{2}\tau _{3}=(4)(2 5)(1 3 6 7)$. The lengths of the cyclic permutations $\tau _{1},\tau _{2}$, and $\tau _{3}$ are 1, 2, and 4, respectively. A cycle of length one is a fixed point.

Let $d_{n}$ denote the number of all derangements in $S_{n}$; then, $d_{n}$ can be expressed as follows:

$$ d_{n}=n! \sum ^n_{k=0}\frac{(-1)^{k}}{k!} $$

for $n\ge 2$, and $d_{1}=0$. The number of permutations (in $S_{n}$) having exactly f fixed points is ${}_n \mathrm {C}_{f} \cdot d_{n-f}$, where we define $d_{0}=1$.

2.4 Expression of Permutation Using Cards

Hereinafter, we use the expression [1 : m] to represent the set $\{1,2,\ldots ,m\}$ for a positive integer m. Remember that a commitment to $i \in [1:n]$ consists of one red card at the i-th position and $n-1$ black cards at the remaining positions. In this paper, we represent a hidden permutation $\pi \in S_{n}$ using a sequence of n distinct commitments $(X_{1},\ldots ,X_{n})$ such that

(1)

Given a hidden permutation $\pi \in S_{n}$ in the above form (1), to check whether an element $i \in \pi$ is a fixed point, it suffices to reveal the i-th card of the i-th commitment: if the revealed card is red, the element is a fixed point, i.e., $\pi (i)=i$.

2.5 The Existing Protocol

We introduce the ICM protocol [8], which generates a uniformly distributed random derangement using $n^{2}$ cards with the pile-scramble shuffle, as follows.

• 1. Arrange n distinct commitments corresponding to the identity permutation (in $S_{n}$) according to the form (1). That is, all the cards on the diagonal are red $\heartsuit$ and the remaining cards are black $\clubsuit$.

• 2. Apply a pile-scramble shuffle to the sequence of n commitments. Note that the resulting n commitments correspond to a certain permutation $\pi \in S_{n}$; moreover, $\pi$ is uniformly randomly distributed.

• 3. Turn over the n cards on the diagonal to check whether there are fixed points in the permutation $\pi$.

  • If at least one red card appears, return to Step 2.

  • If all the revealed cards are black, $\pi$ has no fixed point; hence, $\pi$ is a uniformly distributed random derangement.

After n players $P_{1},P_{2},\ldots ,P_{n}$ obtain a hidden derangement (consisting of n commitments) through this protocol, Secret Santa can be implemented by $P_{i}$ receiving the i-th commitment; he/she reveals the commitment privately to confirm the value of $\pi (i)$, and then purchases a gift for $P_{\pi (i)}$.

Whenever a generated permutation $\pi$ is not a derangement, the protocol returns to Step 2. The probability that a generated permutation uniformly randomly chosen from $S_{n}$ is a derangement is ${d_{n}}/{n!}=\sum ^n_{k=0}{(-1)^{k}}/{k!}$. As $\lim _{n \rightarrow \infty } \sum ^n_{k=0}{(-1)^{k}}/{k!}={1}/{e}$, the probability of the need to restart the shuffle in the ICM protocol is approximately $1-{1}/{e}\approx 0.63$.

Note that Ishikawa et.al. [8] also showed that the number of required cards can be reduced from $n^{2}$ to $2n\lceil \log _{2} n \rceil +6$ by arranging each pile of cards corresponding to a player based on a binary number.

3 Proposed Protocol for Generating a Derangement

In this section, we improve the ICM protocol [8] described in Sect. 2.5 so that the probability of the need to restart the shuffle is decreased. Here, we prepare more piles of cards than the number n of players.

3.1 Overview of the Proposed Protocol

Let us provide an overview of the proposed protocol.

We first prepare $n+t$ commitments instead of n commitments, and apply a pile-scramble shuffle to them. These t additional commitments provide a buffer that absorbs any fixed points that may arise. By revealing the cards on the diagonal, we determine all the fixed points; let f be their number. If the fixed points are too many to be absorbed, i.e., $f\,\>\,t$, restart the shuffle. If $f \le t$, we apply the “fixed-point removal” operation (described in Sect. 3.2), resulting in $n+t-f$ commitments. Subsequently, we apply the “reduction” operation (described in Sect. 3.2) to eliminate the $t-f$ extra commitments.

We explain both the fixed-point removal and reduction operations in the following subsection.

3.2 Definitions of the Two Operations

Suppose that we execute Steps 1 and 2 in the ICM protocol (shown in Sect. 2.5), starting with the identity permutation of degree ${n+t}$ (instead of degree n). Then, we obtain a sequence of $n+t$ commitments corresponding to a uniformly distributed random permutation in $S_{n+t}$: we refer to such a sequence of commitments as a committed permutation on $[1:n+t]$.

• Fixed-point Removal Operation. For the above committed permutation on $[1:n\,+\,t]$, let us reveal all the $n\,+\,t$ cards on the diagonal as in Step 3 of the ICM protocol. Subsequently, we determine all the fixed points in the permutation. Let $I_{\mathrm {FP}}$ be the set of indices of these fixed points. Ignoring the commitments corresponding to the fixed points, namely, the commitments whose positions are in $I_{\mathrm {FP}}$, the sequence of the remaining commitments corresponds to a derangement uniformly distributed on $[1:n\,+\,t]\backslash I_{\mathrm {FP}}$: we refer to this sequence as a committed derangement on $[1:n\,+\,t]\backslash I_{\mathrm {FP}}$.

Fig. 1.

Example of execution of the proposed protocol

Through the fixed-point removal operation, a committed permutation of degree $n+t$ is transformed into a committed derangement on $[1:n+t]\backslash I_{\mathrm {FP}}$ of degree $n+t-|I_{\mathrm {FP}}|$.

Consider the case of $(n,t)=(4,3)$ as an example. Let us transform a committed permutation shown in Fig. 1a. Then, after the fixed-point removal operation is applied to the committed permutation of degree seven, all the seven cards on the diagonal are revealed as shown in Fig. 1b. In this example, the commitment $X_{2}$ is a fixed point; hence, we have $I_{\mathrm {FP}}=\{2\}$ and the sequence of the remaining six commitments $(X_{1},X_{3},X_{4},X_{5},X_{6},X_{7})$ is a committed derangement on $[1:7] \backslash \{2\}=\{1,3,4,5,6,7\}$ of degree six.

As $n=4$, the current committed derangement (depicted in Fig. 1b) has two “extra” commitments, i.e., we aim to reduce the degree by two. To this end, we turn over the last commitment, i.e., the seventh commitment $X_{7}$. Assume that the revealed value of $X_{7}$ is 4 as illustrated in Fig. 1c, indicating a mapping $7\mapsto 4$, which we refer to as a bypass. That is, let us ignore the seventh revealed commitment and regard mapping to 7 as virtually mapping to 4 (via the bypass $7 \mapsto 4$). Consequently, we obtain a committed permutation on $\{1,3,4,5,6\}$ of degree five, which has been reduced by one.

We now have the committed permutation of degree five (as in Fig. 1c). It may not be a derangement because if $4\mapsto 7$, it (virtually) has a fixed point (due to the cycle $7 \mapsto 4 \mapsto 7$). Therefore, we turn over the seventh card of the fourth commitment $X_{4}$ to check whether it is a fixed point.

• If a red card appears as shown in Fig. 1d, we have the cycle $7 \mapsto 4 \mapsto 7$, indicating a fixed point. Let $I_{\mathrm {cycle}}$ denote the set of all the indices of the cycle, i.e., $I_{\mathrm {cycle}}=\{4,7\}$. Ignoring this cycle, namely, the commitments $X_{4}$ and $X_{7}$, the sequence of the remaining commitments $(X_{1},X_{3},X_{5},X_{6})$ becomes a committed derangement uniformly distributed on $[1:7]\backslash (I_{\mathrm {FP}} \cup I_{\mathrm {cycle}})=\{1,3,5,6\}$. Thus, we obtain a committed derangement of degree four, as desired. Note that, in this case, the degree decreases by two.

• If a black card appears as shown in Fig. 1e, there is no fixed point; hence, this committed permutation $(X_{1},X_{3},X_{4},X_{5},X_{6})$ is a uniformly distributed derangement of degree five under the bypass $7\mapsto 4$. In this case, the degree decreases by one.

In the above example, if a black card appears, we obtain a derangement of degree five; hence, we need to reduce the degree further (because $n=4$). Therefore, we are expected to reveal another commitment (in this case, we reveal the fourth commitment $X_{4}$ because of the bypass $7\mapsto 4$, as illustrated in Fig. 1f; we will revisit it later).

In general, we define the reduction operation for a committed derangement on $[1:n+t]\backslash (I_{\mathrm {FP}}\cup I_{\mathrm {cycle}}\cup I_{\mathrm {BP}})$ as follows, where $I_{\mathrm {FP}}$ is the set of fixed points, $I_{\mathrm {cycle}}$ is the set of indices in cycles, there is a bypass $i_{1} \mapsto i_{2} \mapsto \cdots \mapsto i_{\ell -1} \mapsto i_{\ell }$, and $I_{\mathrm {BP}}=\{i_{1},i_{2},\ldots ,i_{\ell -1}\}$.

• Reduction Operation. If $I_{\mathrm {BP}}\ne \phi$, turn over the $i_{\ell }$-th commitment $X_{i_{\ell }}$ (which is the end of the bypass). If $I_{\mathrm {BP}}=\phi$, turn over the last of the remaining commitments, i.e., the $(\text{ max }([1:n\,+\,t]\backslash (I_{\mathrm {FP}}\cup I_{\mathrm {cycle}})))$-th commitment; in this case, we set $i_{\ell }=i_{1}=\text{ max }([1:n\,+\,t]\backslash (I_{\mathrm {FP}}\,\cup \, I_{\mathrm {cycle}}))$ for the sake of convenience. In either case, let $i_{\ell +1}$ be the value of the turned over commitment. Then, turn over the $i_{1}$-th card of the $i_{\ell +1}$-th commitment $X_{i_{\ell +1}}$.

  • If a red card appears, this committed permutation has the cycle $i_{1} \mapsto \cdots \mapsto i_{\ell +1} \mapsto i_{1}$. The indices $i_{1},\ldots ,i_{\ell +1}$ of this cycle, namely, all the elements in set $I_{\mathrm {BP}}\cup \{i_{\ell },i_{\ell +1}\}$, are added to the set $I_{\mathrm {cycle}}$, and the bypass disappears; hence, we set $I_{\mathrm {BP}}=\phi$. Ignoring all the commitments whose positions are in $I_{\mathrm {FP}}\cup I_{\mathrm {cycle}}$, the sequence of the remaining commitments becomes a committed derangement on $[1:n+t]\backslash (I_{\mathrm {FP}} \cup I_{\mathrm {cycle}})$. Note that the degree of the committed derangement has been reduced by two (because of ignoring $X_{i_{\ell }}$ and $X_{i_{\ell +1}}$).

  • If a black card appears, the sequence of the remaining commitments is a committed derangement uniformly distributed on $[1:n+t]\backslash (I_{\mathrm {FP}} \cup I_{\mathrm {cycle}} \cup I_{\mathrm {BP}})$ under the bypass $i_{1} \mapsto \cdots \mapsto i_{\ell } \mapsto i_{\ell +1}$ (where $I_{\mathrm {BP}}=\{i_{1},i_{2},\ldots ,i_{\ell }\}$). In this case, the degree of the committed derangement has been reduced by one.

3.3 Description of the Proposed Protocol

We describe the proposed protocol using the two aforementioned operations. This protocol uses $n+t$ piles (whereas the ICM protocol [8] uses n piles), as follows.

• 1. Arrange $n+t$ distinct commitments corresponding to the identity permutation (in $S_{n+t}$) according to the form (1). That is, all the $n+t$ cards on the diagonal are red $\heartsuit$ and the remaining cards are black $\clubsuit$.

• 2. Apply a pile-scramble shuffle to the sequence of $n+t$ commitments, and the resulting $n+t$ commitments become a committed permutation on $[1:n+t]$.

• 3. Apply the fixed-point removal operation described in Sect. 3.2 to the committed permutation obtained in Step 2. Let $I_{\mathrm {FP}}$ be the set of fixed points and $f=|I_{\mathrm {FP}}|$. We obtain a committed derangement on $[1:n+t]\backslash I_{\mathrm {FP}}$ of degree $n+t-f$.

  • In the case of $f\,\>\,t$, the committed derangement is insufficient because its degree is less than the number n of players. Therefore, turn all the cards face-down, and return to Step 2.

  • In the case of $f=t$, the degree of the committed derangement is n, as desired. Therefore, proceed to Step 5.

  • In the case of $f\,<\,t$, proceed to Step 4.

• 4. Repeatedly apply the reduction operation described in Sect. 3.2 to the committed derangement on $[1:n\,+\,t]\backslash I_{\mathrm {FP}}$ obtained in Step 3, until its degree becomes n or less. Recall that each application of the reduction operation reduces the degree by one or two.

  • If a committed derangement of degree $n-1$ is obtained, turn all the cards face-down, and return to Step 2.

  • If a committed derangement of degree n is obtained, proceed to Step 5.

• 5. We have a committed derangement of degree n on $[1:n+t]\backslash (I_{\mathrm {FP}} \,\cup \, I_{\mathrm {cycle}} \,\cup \, I_{\mathrm {BP}})$, as desired.

After we obtain a committed derangement in Step 5, we renumber the players based on the remaining n commitments. If there is a bypass $i_{1}\mapsto i_{2} \mapsto \cdots \mapsto i_{\ell }$, a player who turns over the commitment to $i_{1}$ should purchase a gift for the player corresponding to $i_{\ell }$. For example, consider the committed derangement illustrated in Fig. 1f, which is obtained from Fig. 1e by revealing $X_{4}$ and the seventh card of $X_{5}$. We renumber the four players such that $P_{1}=P'_{1}$, $P_{2}=P'_{3}$, $P_{3}=P'_{5}$, and $P_{4}=P'_{6}$, and make $P'_{1}$, $P'_{3}$, $P'_{5}$, and $P'_{6}$ receive commitments $X_{1}$, $X_{3}$, $X_{5}$, and $X_{6}$, respectively. Each player secretly turns over the assigned commitment to know for whom he/she should purchase a gift. Because of the bypass $7\mapsto 4 \mapsto 5$, the player who reveals the commitment to 7 should purchase a gift for $P'_{5}$.

Thus, the proposed protocol generates a committed derangement. As there is a trade-off between the number t of additional piles and the probability of returning to Step 2, we comprehensively analyze the probability of the need to restart the shuffle in the following section.

4 Probability of the Need to Restart the Shuffle

In the proposed protocol presented in the previous section, the probability of the need to restart the shuffle depends on the number $t\,(\ge 1)$ of additional piles. In this section, we analyze this probability. Recall that the restart occurs when either more than t fixed points appear in Step 3 or a derangement of degree $n-1$ is obtained in Step 4.

Let f be the number of fixed points determined in Step 2. A restart from Step 3 occurs if $t+1 \le f \le n+t$. As the probability that a uniformly distributed random permutation in $S_{n+t}$ has exactly f fixed points is ${{}_{n+t} \mathrm {C}_{f} \cdot d_{n+t-f}}/{(n+t)!}$, the following equation holds:

$$\begin{aligned} \mathrm {Pr}[\text{ Restart } \text{ from } \text{ Step } \text{3 }]=\sum ^{n+t}_{f=t+1}\frac{{}_{n+t} \mathrm {C}_{f} \cdot d_{n+t-f}}{(n+t)!}. \end{aligned}$$

(2)

Next, we consider a restart from Step 4. Suppose that we have a committed derangement of degree $n+x$ for a non-negative integer x. Let $\epsilon (n,x)$ be the probability that repeated applications of the reduction operation result in a committed derangement of degree $n-1$ and we return to Step 2. Each application of the reduction operation to the committed derangement of degree $n+x$ produces a committed derangement of degree either $n+x-2$ or $n+x-1$. The former occurs when the commitment to be revealed is included in a cycle of length two; therefore, its occurrence probability is ${(n+x-1)d_{n+x-2}}/{d_{n+x}}$. The latter occurs with a probability of $1-{(n+x-1)d_{n+x-2}}/{d_{n+x}}$. Thus, $\epsilon (n,x)$ can be expressed recursively as follows:

$$\begin{aligned} \epsilon (n,x)=&\left( 1-\frac{(n+x-1)d_{n+x-2}}{d_{n+x}}\right) \cdot \epsilon (n,x-1) \\&+\frac{(n+x-1)d_{n+x-2}}{d_{n+x}}\cdot \epsilon (n,x-2), \end{aligned}$$

where $\epsilon (n,0)=0$ and $\epsilon (n,1)={n\cdot d_{n-1}}/{d_{n+1}}$. As Step 4 occurs when f lies between 0 and $t-1$ with a probability of ${{}_{n+t}\mathrm {C}_{f}\cdot d_{n+t-f}}/{(n+t)!}$, the following equation holds:

$$\begin{aligned} \mathrm {Pr}[\text{ Restart } \text{ from } \text{ Step } \text{4 }]=\sum ^{t-1}_{f=0}\frac{{}_{n+t}\mathrm {C}_{f}\cdot d_{n+t-f}}{(n+t)!}\cdot \epsilon (n,t-f). \end{aligned}$$

(3)

The probability of the need to return to Step 2 for the entire proposed protocol, denoted by $\mathrm {Pr}[\text{ Restart}^{(n,t)}]$, is the sum of Eqs. (2) and (3). Figure 2 shows the relationship between $t\,(\le 10)$ and the probability $\mathrm {Pr}[\text{ Restart}^{(n,t)}]$ for the number of players from $n=3$ to $n=20$. $\mathrm {Pr}[\text{ Restart}^{(n,0)}]$ is the same as the probability for the ICM protocol. The proposed protocol improves significantly as t increases. If we prepare t additional piles, the number of required cards increases by $t(t+2n)$; considering an unnecessarily large t is not realistic. Even if we set t to a small value such as 2 or 3, the probability can be reduced to approximately 0.1 compared with that of the ICM protocol (approximately 0.6).

Fig. 2.

Relationship between the number t of additional piles and the probability of the need to restart $\mathrm {Pr}[\text{ Restart}^{(n,t)}]$

5 Conclusion

In this paper, we proposed a new efficient protocol that generates a uniformly distributed random derangement. We prepared more piles of cards than the number n of players to suppress the need to restart the shuffle process. There is a trade-off between the number t of additional piles and the probability of the need to restart the shuffle. When executing the proposed protocol, it is better to set $t=2$ or $t=3$, as shown in Fig. 2.

The proposed technique can also be applied to the existing protocol based on the binary expression of the indices of players [8].