1 Introduction
Topswops is a one-player card game in which one randomly arranges n cards, numbered 1 to n. Given such an initial sequence of n cards, the player rearranges the sequence as follows. After looking at the number written on the first card, denoted as k, the player rearranges the first k cards into their reverse order while leaving the remaining \(n-k\) cards unchanged. The player repeatedly applies such prefix reversals to the current sequence until the number on the first card in the sequence becomes 1. For example, consider the case where \(n=5\), and let (3, 1, 4, 5, 2) be an initial sequence. In Topswops, the player rearranges the sequence asso the game ends in seven steps (namely, seven prefix reversals). In this example, the cards are finally sorted in ascending order. Note that the number of steps depends on an individual initial sequence and that the n cards may not be finally sorted in ascending order. For instance, if the initial sequence is (2, 1, 3, 5, 4), the game ends with (1, 2, 3, 5, 4) after one step, so that the cards are unsorted.
$$\begin{aligned}&(\underline{\textbf{3},1,4},5,2) \rightarrow (\underline{\textbf{4},1,3,5},2) \rightarrow (\underline{\textbf{5},3,1,4,2}) \rightarrow (\underline{\textbf{2},4},1,3,5) \rightarrow (\underline{\textbf{4},2,1,3},5) \\ {}&\rightarrow (\underline{\textbf{3},1,2},4,5) \rightarrow (\underline{\textbf{2},1},3,4,5) \rightarrow (1,2,3,4,5) , \end{aligned}$$
1.1 Open Problems in Topswops
Topswops is said to be invented by J.H. Conway (see the Introduction in [2] or p. 116 of [3]). Historically, the problem of which initial sequences produce the maximum number of steps has been investigated. For example, recall that the initial sequence (3, 1, 4, 5, 2) shown above requires exactly seven steps; it is known that in the case of \(n=5\), there is no initial sequence that results in more than seven steps, and hence, seven is the maximum number of steps for Topswops with five cards. Therefore, letting f(n) denote the maximum number of steps for Topswops with n cards, we have \(f(5)=7\).
Anzeige
Generally, the currently known upper bound on f(n) is \(O(1.62^n)\) [3, 4] and the currently known lower bound is \(\Omega (n^2)\) [2]. Thus, there is an exponential gap between the (currently known) upper and lower bounds on f(n), and finding better bounds to reduce that gap is an open problem.
Table 1
Values for f(n) (OEIS A000375) and g(n) (OEIS A123398)
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
f(n) | 0 | 1 | 2 | 4 | 7 | 10 | 16 | 22 | 30 | 38 | 51 | 65 | 80 | 101 | 113 | 139 | 159 | 191 | 221 |
g(n) | 1 | 1 | 2 | 2 | 2 | 1 | 5 | 2 | 1 | 1 | 1 | 1 | 1 | 4 | 6 | 1 | 2 | 1 | 4 |
Since there is no known efficient algorithm for finding the values of f(n), several studies have used brute-force searches to report values for f(n) and the corresponding initial sequences (e.g., [5, 6]). Specifically, values are known up to \(n \le 19\). Table 1 shows known values for f(n), which are registered as OEIS A0003751 in The On-Line Encyclopedia of Integer Sequences (OEIS). That table also shows as g(n) the number of initial sequences requiring f(n) steps, which are registered as OEIS A123398.2 The most recent result was that Kimura et al. [6] obtained values for f(18), f(19) (and g(18), g(19)) in 2021, using 172 threads on nine computers over about six days.3 Finding values of f(n) and g(n) for \(n \ge 20\) has remained an important open problem for many years, along with narrowing the gap between the upper and lower bounds on f(n), as described above.
1.2 Zero-Knowledge Proof Protocol for Topswops
As mentioned above, the computational complexity of Topswops has been insufficiently revealed, and many open problems related to Topswops remain. In particular, for any positive integers n and \(\ell \) (such that \(1 \le \ell \le f(n)\)), there is no known efficient algorithm for finding an initial sequence of n cards that requires exactly \(\ell \) steps. Therefore, there are possible situations where it is invaluable that only a single person knows a particular initial sequence (and its number of steps) while the others do not know anything about it. Hence, let us try to apply the concept of zero-knowledge proof [7] to Topswops. In other words, let us consider a zero-knowledge proof protocol for Topswops whereby a prover P can convince a verifier V that P knows an initial sequence requiring exactly \(\ell \) steps without leaking any information about the sequence. The following illustrates two such situations.
-
Suppose that prover P has discovered an initial sequence of 20 cards requiring 250 steps, which is longer than the currently known lower bound \(f(20)\ge 249\),4 and wants to publish it as a new achievement. However, if P shows the initial sequence to a (possibly malicious) third party, that party might claim it as its own achievement. If, however, a zero-knowledge proof protocol could be applied to Topswops, P could prove that P discovered the initial sequence while still keeping it secret. After gaining sufficient recognition, P could claim the initial sequence by disclosing it without any trouble.
-
Suppose that several players want to play a game in which they try to find an initial sequence of Topswops. The rules of the game state that the winner is the player who finds an initial sequence with a larger number of steps, or one with a predetermined number of steps. Assume that the game may be played many times, with different players and different conditions. If the initial sequences are disclosed every time to determine a game winner, those sequences lead to another sequence corresponding to a smaller number of steps, or it will serve as a clue for finding another sequence having a larger number of steps, which makes it impossible to fairly or enjoyably play subsequent games. Using a zero-knowledge proof protocol to determine the game winner, however, would make it possible to enjoy the game.
1.3 Botdrops and Zero-Knowledge Proof Protocol
“Botdrops” (a.k.a. Bottomdrops) [8] is a variant of Topswops and is also a one-player card game. In this game, given an initial sequence of n cards numbered 1 to n, the player rearranges the sequence as follows. The player first looks at the number written on the bottom card, denoted as k, the player rearranges the first k cards into the reverse order and puts the reversed sub-sequence on the bottom. The player repeats such an operation to the current sequence. After such an operation is performed several times, the sequence falls into an \(\ell \)-cycle loop (for some integer \(\ell \)).
Anzeige
Similar to the case of Topswops, there is no known efficient algorithm to find an initial sequence which leads to an \(\ell \)-cycle loop for given \(\ell \). Hence, a solution (namely, an initial sequence) of Botdrops is also invaluable and we will construct a zero-knowledge proof protocol for Botdrops.
1.4 Contribution
In this paper, we propose a zero-knowledge proof protocol for Topswops. Namely, assuming that positive integers n and \(\ell \) (such that \(1 \le \ell \le f(n)\)) are public, when a prover P knows an initial sequence of n cards requiring exactly \(\ell \) steps, P can convince a verifier V that P knows the initial sequence without disclosing it. Our protocol is a so-called physical zero-knowledge proof protocol that can be executed using a physical deck of cards.
In addition, we deal with “Botdrops.” To our knowledge, Botdrops itself has not been investigated so much in the literature. Thus, we first analyze this game for the case of \(n\le 13\) comprehensively, where n is the size of the game. Consequently, we find that the sequences produced by Botdrops are very different from the ones produced by Topswops, and hence, we believe that this game itself is worthwhile investigating. After such investigation, we construct a zero-knowledge proof protocol for Botdrops. The rediscovery of Botdrops itself is considered one of the main contributions.
1.5 Related Work
In the literature, many physical zero-knowledge proof protocols have been constructed using a physical deck of cards, especially those for pencil puzzles such as Sudoku. Examples include ABC End View [9, 10], Akari [11], Ball Sort Puzzle [12], Cryptarithmetic [13], Five Cells [14], Goishi Hiroi [10], Kurodoko [15], Hashiwokakero (Bridges) [16], Heyawake [17], Hitori [17, 18], Juosan [19], Kakuro [11, 20], KenKen [11], Makaro [21, 22], Masyu [23], Moon-or-Sun [24], Nonogram [25‐27], Norinori [28], Numberlink [29, 30], Nurikabe [17, 18], Nurimisaki [15, 31], Ripple Effect [32, 33], Shikaku [34], Slitherlink [23, 35], Sudoku [36‐40], Suguru [41, 42], Takuzu [11, 19], Usowan [43], and Pancake sorting [44].
Since our protocol uses a physical deck of cards, this study falls into the research area of card-based cryptography (refer to [45‐47] for surveys), which has been rapidly growing recently, e.g., [48, 49]. The recent results on card-based cryptography include proposing efficient protocols for symmetric functions [50, 51], analyzing information leakage due to operative errors [52], introducing graph automorphism shuffles [53], designing a secure sorting protocol [54], lowering the numbers of required cards [55] and shuffles [56], constructing multi-valued protocols with a direction encoding [57], introducing new encoding schemes for integers [58], exploring half-open-action protocols [59], applications of Garbled circuits [60‐62], and determining the landscape of card-minimal protocols in terms of running time requirements [63].
2 Preliminaries
In this section, we first explain the notations used in this paper, then describe how and what physical cards are utilized, and introduce the “pile-scramble shuffle [64]” and the “sort sub-protocol [65],” both of which are used in our protocols as sub-protocols.
2.1 Notations
Let n denote the Topswops size (i.e., the number of cards in an initial sequence), as in Sect. 1.
We regard any initial sequence of n cards and its succeeding sequences that appear in Topswops as permutations on \(\{1,2,\dots ,n\}\). That is, a permutation \(\pi \in S_n\), i.e.,represents a sequence of n cardswhere \(S_n\) denotes the symmetric group of degree n.
$$\begin{aligned} \pi =\left( \begin{array}{ccccc} 1 &{} 2 &{} 3 &{} \cdots &{} n \\ \pi (1) &{} \pi (2) &{} \pi (3) &{} \cdots &{} \pi (n) \end{array} \right) , \end{aligned}$$
$$\begin{aligned} (\pi (1), \pi (2), \pi (3), \dots , \pi (n)), \end{aligned}$$
For the initial sequence corresponding to a permutation \(\pi \in S_n\), denote by \(\alpha (\pi )\) the number of steps required in Topswops. Using this notation \(\alpha (\pi )\), we formally define f(n), which is the maximum number of steps for n cards, asUsing a permutation, let us represent each prefix reversal operation in Topswops, which rearranges the first i cards in their reverse order: Define a permutation
for every i, \(2\le i\le n\), as
which is sometimes referred to as the swap
. Note that
is equal to its inverse permutation
. That is, for every i such that \(2\le i\le n\),
holds.
$$\begin{aligned} f(n):=\max \left\{ \alpha (\pi )\;|\;\pi \in S_n\right\} . \end{aligned}$$
for every i, \(2\le i\le n\), as
. Note that
is equal to its inverse permutation
. That is, for every i such that \(2\le i\le n\),
(1)
2.2 Commitment Based on Physical Cards
The goal of this paper is to construct a zero-knowledge proof protocol for Topswops, which should keep an initial sequence and its subsequent sequences secret. Therefore, as usual in card-based cryptography, we place cards face down and perform a series of operations such as shuffling, rearranging, and turning over cards.
In this paper, we use a deck of physical cards numbered 1 to n, denoted by
, whose backs are all identical
. We assume that cards
having the same number i are all indistinguishable. By
we denote a face-down card whose face is
for a number i.
, whose backs are all identical
. We assume that cards
having the same number i are all indistinguishable. By
for a number i.As explained in the previous subsection, an initial sequence of n cards can be represented by a permutation \(\pi \in S_n\), so a prover P can take n physical cards
and place them face down according to the initial sequence \(\pi \):
It thus seems possible to keep the initial sequence and its succeeding sequences secret. However, it is difficult to apply a swap
to such a physical sequence while keeping the integer i secret, and hence, such a simple representation does not work.
and place them face down according to the initial sequence \(\pi \):
to such a physical sequence while keeping the integer i secret, and hence, such a simple representation does not work.We therefore introduce a novel encoding of integers based on swaps
: an integer \(x \in \{2, 3, \dots , n\}\) is encoded with n cards as
In other words, each integer \(x \in \{2, 3, \dots , n\}\) is represented by
In addition, \(x=1\) is represented with n cards of
as
We call a sequence of n face-down cards encoding an integer \(x \in \{1,2, \dots , n\}\) (according to the encoding rules (2) and (3) above) a ts-commitment to x. Therefore, a ts-commitment to 1 is a sequence of n face-down cards
and a commitment to x such that \(x\ge 2\) is
Without distinguishing between the case \(x=1\) and the case \(x>1\), a ts-commitment to x is denoted by
: an integer \(x \in \{2, 3, \dots , n\}\) is encoded with n cards as
(2)
as
(3)
2.3 Pile-Scramble Shuffle
A pile-scramble shuffle [64] is a shuffling operation by which several piles of cards of the same size are shuffled.
As an example, suppose that we have n commitments and a sequence of n face-down cards corresponding to a permutation \(\pi \in S_n\) as follows:
where numbers above the commitments represent indexes for convenience. Considering each commitment and the card below it as a single pile, apply a pile-scramble shuffle to the n piles. The transition is
where \(r\in S_n\) is a uniformly distributed random permutation generated by the pile-scramble shuffle.
(4)
(5)
To implement a pile-scramble shuffle, we fix each pile of cards and shuffle the piles [64].
2.4 Sort Sub-protocol
Recall arrangement (4) above, where we have a sequence of n commitments and a sequence of cards corresponding to a permutation \(\pi \in S_n\). Suppose that, after applying a pile-scramble shuffle to them as in transition (5), we turn over all n cards on the second row. Each number 1 to n should appear. We then sort the piles (keeping the order within each pile unchanged) so that the revealed numbers are in ascending order. We now obtain the sequence of piles
(because, for example, if \(\pi (r^{-1}(i))=1\), then \(r^{-1}(i)=\pi ^{-1}(1)\) and the commitment at position \(\pi ^{-1}(1)\) moves to the first). We have thus rearranged the sequence of n commitments according to the permutation \(\pi \in S_n\) while keeping \(\pi \) secret.
This technique has been commonly used in constructions of zero-knowledge proof protocols for pencil puzzles since the introduction of a zero-knowledge proof protocol for Sudoku [36] that made full use of card-based cryptography. Koch and Walzer [65] formulated this technique and named it the sort sub-protocol. Note that the idea of applying a pile-scramble shuffle to two sequences of cards corresponding to some permutations originally comes from [66], followed by [67].
3 Proposed Protocol for Topswops
In this section, we propose a zero-knowledge proof protocol for Topswops. Let positive integers n and \(\ell \) (such that \(1 \le \ell \le f(n)\)) be public information. Suppose that a prover P knows \(\sigma \in S_n\) such that \(\alpha (\sigma )=\ell \), i.e., an initial sequence \(\sigma \) of n cards requiring exactly \(\ell \) steps. P wants to convince a verifier V that P knows an initial sequence requiring \(\ell \) steps without revealing any information about the initial sequence \(\sigma \). We will construct a card-based protocol to achieve this.
First, Sect. 3.1 describes the idea behind the proposed protocol. Then, Sects. 3.2 and 3.3 present a copy protocol (that we use as a sub-protocol) and our protocol, respectively. Finally, Sect. 3.4 discusses security and performance of our protocol.
3.1 Idea
This subsection describes the idea behind the proposed protocol using the initial \(n=5\) sequence (3, 1, 4, 5, 2) (which has seven steps) as a working example.
First, prover P, who knows the initial sequence, secretly creates a sequence of commitments corresponding to (3, 1, 4, 5, 2):
Recall that each commitment follows the encoding (2) and (3) defined in Sect. 2.2. For example, the first commitment
i.e., the ts-commitment to 3, is
which is a permutation corresponding to the swap
.
(6)
.Suppose that we can somehow copy this ts-commitment to 3. We then place the five copied face-down cards below the sequence of commitments as
Considering each commitment and the card below as a single pile, we apply a pile-scramble shuffle. After that, as in the sort sub-protocol described in Sect. 2.4, we turn over the five cards in the second row and sort the piles so that the five cards are rearranged in ascending order. We thus obtain the following:
The order of the first three commitments is reversed in the resulting sequence of commitments, which means that the swap
was applied to the initial sequence without leaking any information about
.
was applied to the initial sequence without leaking any information about
.The first commitment in the current sequence is a ts-commitment to 4, which corresponds to the swap
. Hence, similar to the case of
above, after we copy
, if we place the cards of
below the sequence of commitments (to which
was just applied) and apply the sort sub-protocol, the swap
can be applied while the integer corresponding to the first commitment remains secret. If we repeat such operations seven times, the first commitment in the sequence should be a ts-commitment to 1. By turning over the first commitment, we can finally confirm that the prover P placed a correct initial sequence.
. Hence, similar to the case of
above, after we copy
, if we place the cards of
below the sequence of commitments (to which
was just applied) and apply the sort sub-protocol, the swap
can be applied while the integer corresponding to the first commitment remains secret. If we repeat such operations seven times, the first commitment in the sequence should be a ts-commitment to 1. By turning over the first commitment, we can finally confirm that the prover P placed a correct initial sequence.This is the idea behind our protocol. However, the above procedure cannot guarantee that the sequence of commitments (6) secretly set by P correctly satisfies the encoding rules. Thus, the proposed protocol, shown in Sect. 3.3, requires another step to ensure that the sequence is correctly rearranged.
3.2 Copy Protocol
As mentioned in Sect. 3.1, our main protocol requires a copied commitment. The following describes how to make two identical commitments from a single commitment while its value is kept secret.
Given a ts-commitment to x such that \(2\le x\le n\),
along with two sets of
through
as additional cards, our copy protocol proceeds as follows.
through
as additional cards, our copy protocol proceeds as follows.Protocol 1
(Copy protocol)
1.
Commitments and additional cards are placed as follows:
2.
Turn over the cards in the first and second rows and apply a pile-scramble shuffle:
Then, a uniformly distributed random permutation \(r\in S_n\) corresponding to this pile-scramble shuffle occurs, and the resulting cards can be represented as
3.
Turn over all the cards in the third row. If cards 1 through n appear without omission, sort the piles so that the revealed numbered cards are in ascending order, resulting in the following:
Since
from Equation (1), the first and second rows are commitments to x and we have copied commitments
from Equation (1), the first and second rows are commitments to x and we have copied commitments
In the last step, the n cards in the third row are turned over, but no information about x is leaked because these cards were uniformly randomized by the random permutation r in Step 2. Note also that if an input sequence is a ts-commitment to 1, or if it is not a valid commitment, this protocol detects such an error when the cards are turned over in Step 3.
3.3 Our Protocol for Topswops
We are now ready to describe our protocol, which is a so-called non-interactive physical zero-knowledge proof protocol that requires no knowledge of the prover after the prover places an input card sequence (see [68] for details).
According to an initial sequence \(\sigma \) such that \(\alpha (\sigma )=\ell \), the prover P places n face-down cards on the table without anyone seeing the order as
The input to our protocol is this sequence (7) along with additional 2n cards of
and n cards from each of
to
. (The protocol may be executed by a prover or a verifier, or even by a third party.5)
(7)
and n cards from each of
to
. (The protocol may be executed by a prover or a verifier, or even by a third party.5)Protocol 2
(Physical zero-knowledge proof protocol for Topswops)
1.
Using \(2n-1\) cards of
and \(n-1\) number cards of each from
to
from the additional cards, make a ts-commitment to each of 1 through n and place them above the input sequence (7) as follows:
and \(n-1\) number cards of each from
to
from the additional cards, make a ts-commitment to each of 1 through n and place them above the input sequence (7) as follows:
2.
Apply a pile-scramble shuffle:
3.
In the manner of the sort sub-protocol described in Sect. 2.4, turn over and sort the cards in the bottom row so that the cards in the bottom row are in ascending order:
(If any card from 1 to n does not appear in the bottom row, the protocol halts.) Set \(\pi := \sigma \).
4.
Repeat the following Steps 4(a) and 4(b) \(\ell \) times.
(a)
We have two number cards each from
to
(i.e., the cards revealed in Step 3 above or 4(b) below and the remaining additional cards not used in Step 1). Using these as additional cards, copy the first commitment, \(\pi (1)\), by executing the copy protocol described in Sect. 3.2 and place the copied commitment below the sequence of commitments. Hereinafter, we use x for \(\pi (1)\) in subscripts for simplicity:
(If an illegal card appears during the copy protocol, the protocol halts.)
to
(i.e., the cards revealed in Step 3 above or 4(b) below and the remaining additional cards not used in Step 1). Using these as additional cards, copy the first commitment, \(\pi (1)\), by executing the copy protocol described in Sect. 3.2 and place the copied commitment below the sequence of commitments. Hereinafter, we use x for \(\pi (1)\) in subscripts for simplicity:
(b)
Apply a pile-scramble shuffle, turn over the cards in the bottom row, and sort the cards in the bottom row in ascending order:
After this operation, the first row is a sequence of commitments such that the order of the first x commitments is reversed, i.e., the swap
operation has been applied to the previous sequence of commitments. (If any card from 1 to n does not appear, the protocol aborts.) Set
.
operation has been applied to the previous sequence of commitments. (If any card from 1 to n does not appear, the protocol aborts.) Set
.5.
Turn over the first commitment
and return ‘accept’ if
appears. Otherwise, return ‘reject.’
and return ‘accept’ if
appears. Otherwise, return ‘reject.’3.4 Security and Performance
We first prove that our protocol is a zero-knowledge proof protocol. In other words, we show that our protocol satisfies requirements for completeness, soundness, and zero knowledge.
Completeness: Suppose that a prover P correctly sets as input a sequence of n cards encoding an initial sequence \(\sigma \in S_n\) such that \(\alpha (\sigma )=\ell \). Then, as can be seen from the construction of the protocol, the sequence is not rejected at any step, but accepted at the final step.
Soundness: Assume that an input sequence of n cards is not the encoding of an initial sequence requiring exactly \(\ell \) steps. There are three cases to consider; (i) the initial sequence is invalid, namely, it is not a sequence consisting of n cards, \(1, 2, \ldots , n\), (ii) the initial sequence requires exactly \(\ell '~(< \ell )\) steps, and (iii) the initial sequence requires exactly \(\ell '~(> \ell )\) steps. Our goal is to prove that the protocol eventually rejects each and the following answers it. Zero knowledge: Suppose that the sequence set by prover P corresponds to \(\sigma \in S_n\) such that \(\alpha (\sigma )=\ell \). During the protocol (except for the final step), no information about \(\sigma \) is leaked because the order of revealed cards
to
is always randomized by a pile-scramble shuffle, which is applied immediately before the cards are turned over. In addition, the ts-commitment to 1 opened in the final step is public information (from the definition of Topswops). Thus, the proposed protocol is information-theoretically secure.
(i)
If the input sequence is not encoded for any initial sequence, for example, an input sequence contains two
’s, such an invalid sequence is detected and rejected because not every card from 1 to n appears when the cards are turned up in Step 3.
’s, such an invalid sequence is detected and rejected because not every card from 1 to n appears when the cards are turned up in Step 3.(ii)
Suppose that the input sequence requires exactly \(\ell '~(< \ell )\) steps. When Steps 4 of our protocol are executed \(\ell '\) times, the first commitment will be a ts-commitment to 1, and Step 4(a) of iteration \((\ell '+1)\) will duplicate the ts-commitment to 1, and hence, our protocol rejects the first commitment because n cards of 1 appear in the final step of the copy protocol.
(iii)
If the input sequence requires \(\ell '~(> \ell )\) steps, the first commitment in the last step is rejected because the first commitment is something other than a ts-commitment to 1.
to
is always randomized by a pile-scramble shuffle, which is applied immediately before the cards are turned over. In addition, the ts-commitment to 1 opened in the final step is public information (from the definition of Topswops). Thus, the proposed protocol is information-theoretically secure.We then discuss the performance of our protocol by counting the number of cards and the number of shuffles required in our protocol.
Regarding the number of cards, we use
to
for the input card sequence, as described at the beginning of Sect. 3.3, with additional 2n cards of
and n cards each of
to
. Thus, \(2n+1\) cards of
and \(n+1\) cards of each of
to
are required, which add up to \(n^2+2n\).
to
for the input card sequence, as described at the beginning of Sect. 3.3, with additional 2n cards of
and n cards each of
to
. Thus, \(2n+1\) cards of
and \(n+1\) cards of each of
to
are required, which add up to \(n^2+2n\).Our protocol uses only the pile-scramble shuffle as a shuffling operation. We therefore count the number of pile-scramble shuffles. In our protocol, Step 2 is executed once, and Steps 4(a) and 4(b) are repeated \(\ell \) times. These steps include one pile-scramble shuffle, so our protocol requires \(2\ell +1\) pile-scramble shuffles in total.
4 Zero-Knowledge Proof for Botdrops
In this section, we deal with another game called Botdrops [8]; we propose a physical zero-knowledge proof protocol for Botdrops. Although little is known about Botdrops and it has been little analyzed to date, we display in this paper that Botdrops is a very interesting one-player game, having quite different features from Topswops.
In Sect. 4.1, we introduce Botdrops and investigate it comprehensively for the case of \(n \le 13\) (where n is the size of the game). In Sect. 4.2, we customize the commitments according to the operations used in Botdrops. In Sect. 4.3, we present the idea behind our protocol. In Sect. 4.4, we present a couple of sub-protocols used in our protocol as building blocks. In Sect. 4.5, we construct a zero-knowledge proof protocol for Botdrops. Finally, Sect. 4.6 discusses the security and performance of the protocol.
4.1 Botdrops
Botdrops (a.k.a. Bottomdrops) [8] is a variant of Topswops and is also a one-player card game in which one randomly arranges n cards, numbered 1 to n. Given such an initial sequence of n cards, the player rearranges the sequence as follows. The player first looks at the number written on the bottom card, denoted as k, the player rearranges the first k cards into the reverse order and puts the reversed sub-sequence on the bottom. The player repeats such an operation, which we call a botdrops operation, to the current sequence.
Take (3, 1, 4, 5, 2) as an example of an initial sequence with \(n=5\); then, a player rearranges the sequence asand the player finds himself/herself in a loop because \((\underline{5,2,3,1},\textbf{4})\) appears again, which leads to a 2-cycle loop of \((\underline{5,2,3,1},\textbf{4})\) and \((\underline{4,1,3,2,\textbf{5}})\). In general, as easily imagined, Botdrops always produces a loop (unlike Topswops). We are now interested in what kinds of cycles appear in Botdrops.
$$\begin{aligned}&(\underline{3,1},4,5,\textbf{2}) \rightarrow (\underline{4,5,2},1,\textbf{3}) \rightarrow (\underline{1,3,2,5},\textbf{4}) \rightarrow (\underline{4},5,2,3,\textbf{1}) \rightarrow (\underline{5,2,3,1},\textbf{4}) \\&\rightarrow (\underline{4,1,3,2,\textbf{5}}) \rightarrow (\underline{5,2,3,1},\textbf{4}) \rightarrow \cdots , \end{aligned}$$
According to Martin Gardner’s book [8], for the case of \(n=13\), “Roland Silver of San Cristobal, N.M., exploring the Botdrops for cycles, discovered why the game usually terminates in a king-queen loop. There are no other 2-cycles and none of 3 and 4. Although 5 cycles exist, the probability of entering one is low.” As Gardner wrote “on rare occasions other loops possible. (Can you find one?)” in the same book [8], finding an initial sequence which leads to a cycle of length more than two is an intriguing and challenging problem6.
Since the above book [8] (introducing Botdrops) was written in 1988, we thought that there would have been many existing results on cycle lengths. However, we cannot find any such known results in the literature. Hence, we first tackle the question of what initial sequences produce a loop of length more than two, and especially, we seek for the longest cycles. Actually, for example, for the case of \(n=13\), we find that (1, 4, 3, 6, 12, 5, 8, 13, 7, 9, 2, 11, 10) produces a cycle of length 30:We have investigated the cycle lengths for the case of \(n \le 13\) comprehensively. To display our obtained results, we first introduce some notations. For an initial sequence corresponding to a permutation \(\sigma \in S_n\), denote the length of a loop (i.e., the cycle length) generated from the sequence by \(\beta (\sigma )\). Let \({\mathcal {B}}(n)\) be the set of cycle lengths with n cards, i.e.,Let h(n) be the maximum number in \({\mathcal {B}}(n)\), i.e.,Tables 2 and 3 show \({\mathcal {B}}(n)\) and h(n) for \(n=1,2, {\ldots }, 13\), respectively. Interestingly, there are loops with other than 2-cycles or 5-cycles for \(n=13\), and the maximum length h(n) for n seems to vary irregularly. The sets \({\mathcal {B}}(n)\) are also interesting; for example, \({\mathcal {B}}(10) \subset {\mathcal {B}}(11)\) while \({\mathcal {B}}(11) \not \subset {\mathcal {B}}(12)\). Such properties would make it difficult to find an initial sequence which produces the longest cycle.
$$\begin{aligned}&(\underline{1, 4, 3, 6, 12, 5, 8, 13, 7, 9}, 2, 11, \textbf{10}) \rightarrow (\underline{2}, 11, 10, 9, 7, 13, 8, 5, 12, 6, 3, 4, \textbf{1}) \\ {}&\rightarrow (\underline{11, 10}, 9, 7, 13, 8, 5, 12, 6, 3, 4, 1, \textbf{2}) \rightarrow (\underline{9, 7, 13, 8, 5, 12, 6, 3, 4, 1, 2}, 10, \textbf{11}) \\ {}&\rightarrow (\underline{10, 11, 2, 1, 4, 3, 6, 12, 5}, 8, 13, 7, \textbf{9}) \rightarrow (\underline{8, 13, 7, 9, 5, 12, 6, 3, 4, 1}, 2, 11, \textbf{10}) \\ {}&\rightarrow (\underline{2, 11, 10, 1, 4, 3, 6, 12}, 5, 9, 7, 13, \textbf{8}) \rightarrow (\underline{5, 9}, 7, 13, 8, 12, 6, 3, 4, 1, 10, 11, \textbf{2}) \\ {}&\rightarrow (\underline{7, 13, 8, 12, 6}, 3, 4, 1, 10, 11, 2, 9, \textbf{5}) \rightarrow (\underline{3, 4, 1, 10, 11, 2, 9}, 5, 6, 12, 8, 13, \textbf{7}) \\ {}&\rightarrow (\underline{5, 6, 12}, 8, 13, 7, 9, 2, 11, 10, 1, 4, \textbf{3}) \rightarrow (\underline{8, 13, 7, 9, 2}, 11, 10, 1, 4, 3, 12, 6, \textbf{5}) \\ {}&\rightarrow (\underline{11, 10, 1, 4, 3, 12, 6, 5}, 2, 9, 7, 13, \textbf{8}) \rightarrow (\underline{2, 9, 7, 13, 8, 5, 6, 12, 3, 4, 1}, 10, \textbf{11}) \\ {}&\rightarrow (\underline{10, 11}, 1, 4, 3, 12, 6, 5, 8, 13, 7, 9, \textbf{2}) \rightarrow (\underline{1, 4, 3, 12, 6, 5, 8, 13, 7, 9}, 2, 11, \textbf{10}) \\&\rightarrow (\underline{2}, 11, 10, 9, 7, 13, 8, 5, 6, 12, 3, 4, \textbf{1}) \rightarrow (\underline{11, 10}, 9, 7, 13, 8, 5, 6, 12, 3, 4, 1, \textbf{2}) \\ {}&\rightarrow (\underline{9, 7, 13, 8, 5, 6, 12, 3, 4, 1, 2}, 10, \textbf{11}) \rightarrow (\underline{10, 11, 2, 1, 4, 3, 12, 6, 5}, 8, 13, 7, \textbf{9}) \\ {}&\rightarrow (\underline{8, 13, 7, 9, 5, 6, 12, 3, 4, 1}, 2, 11, \textbf{10}) \rightarrow (\underline{2, 11, 10, 1, 4, 3, 12, 6}, 5, 9, 7, 13, \textbf{8}) \\ {}&\rightarrow (\underline{5, 9}, 7, 13, 8, 6, 12, 3, 4, 1, 10, 11, \textbf{2}) \rightarrow (\underline{7, 13, 8, 6, 12}, 3, 4, 1, 10, 11, 2, 9, \textbf{5}) \\ {}&\rightarrow (\underline{3, 4, 1, 10, 11, 2, 9}, 5, 12, 6, 8, 13, \textbf{7}) \rightarrow (\underline{5, 12, 6}, 8, 13, 7, 9, 2, 11, 10, 1, 4, \textbf{3}) \\ {}&\rightarrow (\underline{8, 13, 7, 9, 2}, 11, 10, 1, 4, 3, 6, 12, \textbf{5}) \rightarrow (\underline{11, 10, 1, 4, 3, 6, 12, 5}, 2, 9, 7, 13, \textbf{8}) \\ {}&\rightarrow (\underline{2, 9, 7, 13, 8, 5 ,12, 6, 3, 4, 1}, 10, \textbf{11}) \rightarrow (\underline{10, 11}, 1, 4, 3, 6, 12, 5, 8, 13, 7, 9, \textbf{2}) \\ {}&\rightarrow (1, 4, 3, 6, 12, 5, 8, 13, 7, 9, 2, 11, 10). \end{aligned}$$
$$\begin{aligned} {\mathcal {B}}(n):= \{\beta (\sigma ) \;|\; \sigma \in S_n\}. \end{aligned}$$
$$\begin{aligned} {h}(n):= \max ({\mathcal {B}}(n)). \end{aligned}$$
Table 2
Values of \({\mathcal {B}}(n)\) for Botdrops
n | \({\mathcal {B}}(n)\) |
|---|---|
1 | 1 |
2 – 6 | 2 |
7 | 2, 5 |
8 | 2, 5, 10 |
9 | 2, 5, 12 |
10 | 2, 5, 10, 20 |
11 | 2, 5, 8, 9, 10, 12, 20 |
12 | 2, 5, 8, 10, 12, 20, 30 |
13 | 2, 5, 6, 8, 9, 10, 12, 16, 20, 24, 30 |
Table 3
Values of h(n) for Botdrops
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
h(n) | 1 | 2 | 2 | 2 | 2 | 2 | 5 | 10 | 12 | 20 | 20 | 30 | 30 |
As in the case of Topswops explained in Sect. 1.1, there are possible situations where it is invaluable that only a single person knows a particular initial sequence (and its cycle length) while the others do not know anything about it. This is a motivation that we construct a zero-knowledge proof protocol for Botdrops.
4.2 Commitment for Botdrops
In this subsection, we first define permutations corresponding to the botdrops operations (appearing in Botdrops). We then define commitments for Botdrops. In the sequel, let n denote the Botdrops size (namely, the number of elements in an initial sequence).
Using a permutation in \(S_n\), let us represent each botdrops operation in Botdrops, which rearranges the first i cards in their reverse order and moves them to the bottom: Define a permutation \(\textsf{bd}_i \in S_n\) for every i, \(1\le i\le n\), asUnlike
, note that \(\textsf{bd}_i\) is not equal to its inverse permutation \(\textsf{bd}_i^{-1}\).
$$\begin{aligned} \textsf{bd}_i=\left( \begin{array}{ccccccccccccc} 1 &{} 2 &{} \cdots &{} i-1 &{} i &{} i+1 &{} i+2 &{} \cdots &{} n-1 &{} n \\ n &{} n-1 &{} \cdots &{} n-i+2 &{} n-i+1 &{} 1 &{} 2 &{} \cdots &{} n-i-1 &{} n-i \end{array} \right) . \end{aligned}$$
, note that \(\textsf{bd}_i\) is not equal to its inverse permutation \(\textsf{bd}_i^{-1}\).Similar to the protocol for Topswops, for an integer x such that \(1\le x\le n\), we call a sequence of n face-down cards
a bd-commitment to x.
4.3 Goal and Idea
Assume that n and \(\ell \) (such that \(2 \le \ell \le {h}(n)\)) are public information, and that a prover wants to convince a verifier that the prover knows an initial sequence \(\sigma \) such that \(\beta (\sigma )=\ell \). Without loss of generality, we assume that the initial sequence \(\sigma \) immediately falls into an \(\ell \)-cycle loop at the beginning.
At first glance, a zero-knowledge proof protocol seems to be naturally derived, in a similar way to the protocol for Topswops (namely, Protocol 2), by arranging bd-commitments to from 1 to n and permuting them based on the bottom bd-commitment \(\ell \) times. However, a protocol for Botdrops needs to check that the transition surely forms a loop (of length \(\ell \)). To this end, it suffices to verify that the final sequence is identical to the initial sequence as well as every other sequence is not the same as the initial sequence.
Let us explain the overall flow of our protocol. Similar to Protocol 2, first, a prover and a verifier arrange a sequence of bd-commitments corresponding to the initial sequence \(\sigma \in S_n\) somehow:
Unlike the protocol for Topswops in which the first card indicates the amount of a prefix reversal, in Botdrops, the bottom card indicates the size of a botdrops operation. Therefore, using the last bd-commitment to \(\sigma (n)\), we secretly apply the permutation \(\textsf{bd}_x\) to the sequence, where \(x=\sigma (n)\):
We repeatedly apply such a transformation \(\ell \) times, in a similar way to Protocol 2.
As mentioned above, we have to check that the final sequence, namely the \(\ell \)-th sequence, is identical to the initial sequence and every other sequence, namely every i-th sequence with \(1 \le i< \ell \), is not the same as the initial sequence. To this end, we attach a tag-commitment to each bd-commitment, as illustrated below:
Here, each tag-commitment represents the same value as that of the bd-commitment below it. During the botdrops operations, we make each tag-commitment follow the corresponding bd-commitment. Thus, instead of bd-commitments, we use such tag-commitments to check that the transition surely forms an \(\ell \)-cycle loop.
If we attempt to use numbered cards as tag-commitments, it seems difficult to verify whether given two tag-commitments (or two sequences of tag-commitments) are identical without leaking any information other than that. Therefore, we consider making use of the typical encoding rule used in card-based cryptography [45, 74]: we use black and red cards to represent a one-bit value:
We call two face-down cards following the above encoding a bit-commitment. Since we have to prepare n tag-commitments corresponding to integers from 1 to n, we use \(2 \lceil \log _2 n \rceil \) cards to make each tag-commitment, as follows:
Thus, we attach such a sequence of bit-commitments as a tag-commitment to each bd-commitment:
4.4 Sub-protocols
To construct a zero-knowledge proof protocol for Botdrops, we require a way for checking whether two sequences of tag-commitments are identical or not. For this, in this subsection, we present two sub-protocols along with a general copy protocol.
We first prepare a bit-wise check sub-protocol. Given two bit-commitments
and
to bits a and b, respectively, let us introduce a sub-protocol which outputs (copies of) bit-commitments to a, b as well as a bit-commitment to \(a \oplus b \oplus 1\). Note that \(a \oplus b \oplus 1=1\) if \(a=b\) holds; otherwise, \(a \oplus b \oplus 1=0\). This sub-protocol is based on the existing bit-commitment copy protocol [75] together with the idea behind the existing input-preserving XOR protocol for polarizing cards [76]. The following sub-protocol uses four additional cards
aside from two input bit-commitments to \(a,b\in \{0,1\}\).
and
to bits a and b, respectively, let us introduce a sub-protocol which outputs (copies of) bit-commitments to a, b as well as a bit-commitment to \(a \oplus b \oplus 1\). Note that \(a \oplus b \oplus 1=1\) if \(a=b\) holds; otherwise, \(a \oplus b \oplus 1=0\). This sub-protocol is based on the existing bit-commitment copy protocol [75] together with the idea behind the existing input-preserving XOR protocol for polarizing cards [76]. The following sub-protocol uses four additional cards
aside from two input bit-commitments to \(a,b\in \{0,1\}\).Protocol 3
(\(\textsf{Sub}\)-\(\textsf{protocol}_1\))
1.
Place
and bit-commitments to a, b, and turn over the additional cards, as follows:
and bit-commitments to a, b, and turn over the additional cards, as follows:
2.
Apply a pile-scramble shuffle to the first three rows:
where \(r\in \{0,1\}\) is a uniformly distributed random bit.
3.
Turn over the cards in the third row. If
appears, swap the cards in the first through third rows (namely, bit-commitments) and turn over the cards in the third row to be face-down. Otherwise, do nothing. Then, we have:
appears, swap the cards in the first through third rows (namely, bit-commitments) and turn over the cards in the third row to be face-down. Otherwise, do nothing. Then, we have:
4.
After turning over the cards in the third row, apply a pile-scramble shuffle to the last three rows:
5.
Turn over the cards in the fourth row. If
appears, swap cards in the second through fourth rows. Otherwise, do nothing. Then, we have:
appears, swap cards in the second through fourth rows. Otherwise, do nothing. Then, we have:
6.
Swap the cards in the second row, resulting in:
We next introduce the second sub-protocol which checks whether two sequences of tag-commitments are identical or not. Given two sequences of tag-commitments A and B each consisting of 2mn cards as inputs, the following sub-protocol returns ‘true’ or ‘false’ using six additional cards
, where \(m:= \lceil \log _2 n \rceil \) in the sequel.
, where \(m:= \lceil \log _2 n \rceil \) in the sequel.Protocol 4
(\(\textsf{Sub}\)-\(\textsf{protocol}_2\))
1.
Place additional cards
and turn over them to be face-down. We call this bit-commitment ans:
and turn over them to be face-down. We call this bit-commitment ans:
2.
Repeat the following Steps 2(a) and 2(b) for \(i = 1, 2, {\ldots }, n\).
(a)
Pick the i-th tag-commitments of A and B each consisting of 2m cards:
(b)
Repeat the following Steps 2(b)(i) through 2(b)(iv) for \(j=1,2, \ldots , m\).
(i)
Pick the jth bit-commitments from both the tag-commitments; name them bit-commitments to a and b:
(ii)
Run \(\textsf{Sub}\)-\(\textsf{protocol}_1\) with the above two bit-commitments to obtain copies of the two bit-commitments to \(a, b \in \{0,1\}\) along with a bit-commitment to \(a \oplus b \oplus 1\), which is referred to as match. We also obtain two free cards .
(iii)
Place the copies of two bit-commitments back to each of the i-th tag-commitments of A and B.
3.
Turn over the cards for ans, and return ‘true’ if
appears. Otherwise, return ‘false.’
appears. Otherwise, return ‘false.’Finally, we introduce the general copy protocol [36]. The copy protocol presented in Sect. 3.2 makes copies of a commitment \(\sigma \) satisfying \(\sigma ^{-1}=\sigma \). However, a bd-commitment in our protocol for Botdrops does not satisfy \(\sigma ^{-1}=\sigma \). Therefore, the following general copy protocol is required.
Protocol 5
(General copy protocol [36])
(a)
All cards of a bd-commitment and additional numbered cards are placed as follows:
(b)
Turn over the cards in the first row and apply a pile-scramble shuffle:
Then, a uniformly distributed random permutation \(r\in S_n\) corresponding to this pile-scramble shuffle occurs, and the resulting cards can be represented as
(c)
Turn over all the cards in the second row. If cards of 1 through n appear without omission, place cards of the same number in the third row. Then, turn over all cards in the second and third rows, resulting in the following:
(d)
Apply a pile-scramble shuffle:
Then, a uniformly distributed random permutation \(r'\in S_n\) corresponding to this pile-scramble shuffle occurs, and the resulting cards can be represented as
(e)
Turn over all the cards in the first row, and sort the piles so that the revealed numbered cards are in ascending order, resulting in the following:
Hence, two copies of the bd-commitment are obtained in the second and third rows.
4.5 Our Protocol for Botdrops
In this subsection, we present our zero-knowledge proof protocol for Botdrops.
According to an initial sequence \(\sigma \) such that \(\beta (\sigma )=\ell \), the prover P places n face-down cards on the table without anyone seeing the order as
The input to our protocol is the above sequence along with additional \((n+2)\) cards from each of
to
and \((2mn+3)\) cards each of
and
. (The protocol may be executed by a prover or a verifier, or even by a third party.)
to
and \((2mn+3)\) cards each of
and
. (The protocol may be executed by a prover or a verifier, or even by a third party.)Protocol 6
(Physical zero-knowledge proof protocol for Botdrops)
1.
Using 2mn pairs of
and
, make two identical tag-commitments to every number from 1 to n:
and
, make two identical tag-commitments to every number from 1 to n:
2.
Using n number cards of each from
to
from the additional cards, make a bd-commitment to each of 1 through n. Place them above the input sequence. Moreover, place the tag-commitments (made in Step 1) above them as follows:
to
from the additional cards, make a bd-commitment to each of 1 through n. Place them above the input sequence. Moreover, place the tag-commitments (made in Step 1) above them as follows:
3.
Apply a pile-scramble shuffle:
4.
In the manner of the sort sub-protocol described in Sect. 2.4, turn over and sort the cards in the bottom row so that the cards in the bottom row are in ascending order:
(If any card from 1 to n does not appear in the bottom row, the protocol halts.) Put the first row (namely, a sequence of tag-commitments corresponding to \(\sigma \)) aside, which will be used as the initial sequence when checking whether a succeeding sequence is the same or not. Set \(\pi := \sigma \).
5.
Repeat following Steps 5(a) to 5(c) for \(i = 1, 2, \ldots , \ell \).
(a)
We have two number cards each from
to
(i.e., the cards revealed in Step 4 or 5(b) below and the remaining additional cards not used in Step 2). Using these as additional cards, copy the last bd-commitment, \(\pi (n)\), by executing the general copy protocol described in Sect. 4.4 and place it below the sequence of bd-commitments. Hereinafter, we use x for \(\pi (n)\) in subscripts for simplicity:
(If an illegal card appears during the copy protocol, the protocol halts.)
to
(i.e., the cards revealed in Step 4 or 5(b) below and the remaining additional cards not used in Step 2). Using these as additional cards, copy the last bd-commitment, \(\pi (n)\), by executing the general copy protocol described in Sect. 4.4 and place it below the sequence of bd-commitments. Hereinafter, we use x for \(\pi (n)\) in subscripts for simplicity:
(b)
Apply a pile-scramble shuffle, turn over the cards in the bottom row, and sort the cards in the bottom row in ascending order:
After this operation, the second row is a sequence of bd-commitments where the order of the first x bd-commitments was reversed and moved to the bottom, i.e., the botdrops operation \(\textsf{bd}_x\) has been applied to the previous sequence of bd-commitments. (If any card from 1 to n does not appear, the protocol aborts.) Set \(\pi := \textsf{bd}_x \circ \pi \).
(c)
If \(\ell \) is divisible by i, check whether the current sequence of tag-commitments is identical to that of the initial sequence or not: Run \(\textsf{Sub}\)-\(\textsf{protocol}_2\) described in Sect. 4.4 with the current sequence and the sequence of tag-commitments corresponding to \(\sigma \) (made in Step 4). If they are identical and \(i < \ell \), the protocol aborts. When \(i = \ell \), if they are identical, return ‘accept.’ Otherwise, return ‘reject.’
In Step 5(c) above, we use \(\textsf{Sub}\)-\(\textsf{protocol}_2\) to check whether a current sequence of tag-commitments for each i is identical to that of the initial sequence or not. Note that \(\textsf{Sub}\)-\(\textsf{protocol}_2\) checks only two sequences of tag-commitments, we can check all sequences of tag-commitments for \(i=1,2,\ldots , \ell \) sequentially. (It should be noted that Botdrops produces exactly one loop for any initial sequence, and hence, a loop never contains a smaller loop within it.) Also note that, we can modify \(\textsf{Sub}\)-\(\textsf{protocol}_2\) to another sub-protocol which checks all sequences of tag-commitments at once, but, in this case, each sequence of tag-commitments should be stored and the number of required cards increases.
4.6 Security and Performance
We first prove that our protocol is a zero-knowledge proof protocol.
Completeness: Suppose that a prover P correctly places as input a sequence of n cards encoding an initial sequence \(\sigma \in S_n\) such that \(\beta (\sigma )=\ell \). Then, as can be seen from the construction of the protocol, the sequence is not rejected at any step, but accepted at the final step.
Soundness: Assume that an input sequence of n cards is not the encoding of an initial sequence \(\sigma \) producing an \(\ell \)-cycle. There are four cases to consider; we will show that the protocol eventually rejects each. Zero knowledge: Suppose that the sequence set by prover P corresponds to \(\sigma \in S_n\) such that \(\beta (\sigma )=\ell \). During the protocol (except for the final step), no information about \(\sigma \) is leaked because the order of revealed cards
to
is always randomized by a pile-scramble shuffle, which is applied immediately before the cards are turned over. In addition, sub-protocols \(\textsf{Sub}\)-\(\textsf{protocol}_1\) and \(\textsf{Sub}\)-\(\textsf{protocol}_2\) which check whether two sequences of tag-commitments are identical or not are also zero-knowledge protocols and leak no information of tags. Thus, the proposed protocol is information-theoretically secure.
(i)
If the input sequence is not encoded for any initial sequence, for example, an input sequence consists of n
’s, such an invalid input sequence is detected and rejected because not every card from 1 to n appears when the cards are turned up in Step 4.
’s, such an invalid input sequence is detected and rejected because not every card from 1 to n appears when the cards are turned up in Step 4.(ii)
If the input sequence is not an origin of a loop, the \(\ell \)-th sequence is never the same as the input sequence, and hence, such an invalid input sequence does not pass the check in Step 5(c) for \(i=\ell \).
(iv)
Suppose that the input sequence produces an \(\ell '~(< \ell )\)-cycle loop. In order for a malicious P to cheat that the input sequence leads to an \(\ell \)-cycle loop, \(\ell \) should be multiple of \(\ell '\). However, such a cheat is detected in Step 5(c) for \(i=\ell '\) because the initial sequence is the same as the current sequence for \(i=\ell '\).
(v)
If the input sequence produces an \(\ell '~(> \ell )\)-cycle loop, such an invalid input sequence does not pass the check in Step 5(c) for \(i=\ell \) because the input sequence is different from the current sequence for \(i=\ell \).
to
is always randomized by a pile-scramble shuffle, which is applied immediately before the cards are turned over. In addition, sub-protocols \(\textsf{Sub}\)-\(\textsf{protocol}_1\) and \(\textsf{Sub}\)-\(\textsf{protocol}_2\) which check whether two sequences of tag-commitments are identical or not are also zero-knowledge protocols and leak no information of tags. Thus, the proposed protocol is information-theoretically secure.We then discuss the performance of our protocol by counting the number of cards and the number of shuffles required in our protocol.
Regarding the number of cards, as described at the beginning of Sect. 4.5, we use \((n+2)\) cards from each of
to
and \((2mn+3)\) colored cards of each of
and
. Thus, the total number of cards required in our protocol is \(n^2+4mn+2n+6\).
to
and \((2mn+3)\) colored cards of each of
and
. Thus, the total number of cards required in our protocol is \(n^2+4mn+2n+6\).Our protocol uses the pile-scramble shuffle and the random bisection cut (within the AND protocol at Step 2(b)(iv) of Protocol 4) as shuffling operations. Note that the random bisection cut is a special case of the pile-scramble shuffle. In our protocol, Step 3 is executed once, Steps 5(a) and 5(b) are repeated \(\ell \) times, and Steps 5(c) is executed \(d(\ell )\) times where \(d(\ell )\) represents the number of divisors for integer \(\ell \). Step 5(a) and 5(b) include two pile-scramble shuffles (Steps 2 and 4 in Protocol 5) and one pile-scramble shuffle, respectively. Step 5(c) includes 2mn pile-scramble shuffles (Step 2(b)(ii) of Protocol 4) and 2mn random bisection cuts (Step 2(b)(iv) of Protocol 4). Hence, our protocol requires \(4mn d(\ell )+3\ell +1\) shuffles in total.
5 Conclusion
In this paper, we proposed a physical zero-knowledge proof protocol for Topswops. The main idea is that the permutation corresponding to “the operation of reversing the first i cards” encodes a positive integer i, which enables us to efficiently and secretly perform prefix reversals in Topswops. The main idea can be applicable to construct a zero-knowledge proof protocol for other problems, such as the pancake sorting problem [44].
In addition, we rediscovered Botdrops, which is a variant of Topswops; after investigating the cycle lengths, we proposed a physical zero-knowledge proof protocol for Botdrops. Unlike the protocol for Topswops, the protocol for Botdrops requires tag-commitments. The tag-commitments are used to check that the transition in the game surely forms a loop while this check should be zero-knowledge. To this end, we proposed sub-protocols. Constructing more efficient protocols is future work.
Acknowledgements
This work was supported by JSPS KAKENHI Grant numbers JP18H05289, JP21K11881, JP23H00479, JP24K14951, JP24K02938.
Declarations
Conflict of interest
This work was supported by JSPS KAKENHI Grant Numbers JP18H05289, JP21K11881, JP23H00479, JP24K14951, JP24K02938. Takaaki Mizuki is a Guest Editor-in-Chief of this special issue of the journal.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Consent of publication
Not applicable.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
