Back to Search
Start Over
Physical Zero-Knowledge Proof Protocols for Topswops and Botdrops.
- Source :
-
New Generation Computing . Sep2024, Vol. 42 Issue 3, p399-428. 30p. - Publication Year :
- 2024
-
Abstract
- Suppose that a sequence of n cards, numbered 1 to n , is placed face up in random order. Let k be the number on the first card in the sequence. Then take the first k cards from the sequence, rearrange that subsequence of 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 f (n) denote the maximum number of prefix reversals for Topswops with n cards, values of f (n) for n ≥ 20 remain unknown. In general, there is no known efficient algorithm for finding an initial sequence of n cards that requires exactly ℓ prefix reversals for any integers n and ℓ . 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 n cards that requires ℓ prefix reversals without leaking knowledge of that sequence. We also deal with Botdrops, a variant of Topswops. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02883635
- Volume :
- 42
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- New Generation Computing
- Publication Type :
- Academic Journal
- Accession number :
- 179636077
- Full Text :
- https://doi.org/10.1007/s00354-024-00272-3