Portal de Periódicos da CAPES

Physical Zero-Knowledge Proof Protocol for Topswops

2022; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-031-21280-2_30

1611-3349

Yuichi Komano, Takaaki Mizuki,

DNA and Biological Computing

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\ge 20$$ remain unknown. In general, there is no known efficient algorithm for finding an initial sequence of n cards that requires exactly $$\ell $$ prefix reversals for any integers n and $$\ell $$ . In this paper, 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 $$\ell $$ prefix reversals without leaking knowledge of that sequence.