Physical Zero-Knowledge Proof Protocols for Topswops and Botdrops

Suppose that a sequence of \({\varvec{n}}\) $\mathit{n}$ cards, numbered 1 to \({\varvec{n}}\) $\mathit{n}$ , is placed face up in random order. Let \({\varvec{k}}\) $\mathit{k}$ be the number on the first card in the sequence. Then take the first \({\varvec{k}}\) $\mathit{k}$ cards from the sequence, rearrange that subsequence of \({\varvec{k}}\) $\mathit{k}$ cards in reverse order, and return them to the original sequence. Repeat this prefix reversal until the number on the first card in the sequence becomes 1. This is a one-player card game called Topswops. The computational complexity of Topswops has not been thoroughly investigated. For example, letting \({\varvec{f}}({\varvec{n}})\) $\mathit{f}(\mathit{n})$ denote the maximum number of prefix reversals for Topswops with \({\varvec{n}}\) $\mathit{n}$ cards, values of \({\varvec{f}}({\varvec{n}})\) $\mathit{f}(\mathit{n})$ for \({\varvec{n}}\ge 20\) $\mathit{n}\ge 20$ remain unknown. In general, there is no known efficient algorithm for finding an initial sequence of \({\varvec{n}}\) $\mathit{n}$ cards that requires exactly \(\ell \) $\ell$ prefix reversals for any integers \({\varvec{n}}\) $\mathit{n}$ and \({\varvec{\ell }}\) $\mathit{\ell }$ . In this paper, using a deck of cards, we propose a physical zero-knowledge proof protocol that allows a prover to convince a verifier that the prover knows an initial sequence of \({\varvec{n}}\) $\mathit{n}$ cards that requires \({\varvec{\ell }}\) $\mathit{\ell }$ prefix reversals without leaking knowledge of that sequence. We also deal with Botdrops, a variant of Topswops.