Physical zero-knowledge proof for ball sort puzzle

DOI10.1007/978-3-031-36978-0_20MaRDI QIDQ6149049zbMATH OpenFDO

Authors Suthee Ruangwises

Publication date 12 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.07251

zbMATH Keywords

ball sort puzzlecard-based cryptographypuzzlezero-knowledge proof

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Abstract: Ball sort puzzle is a popular logic puzzle consisting of several bins containing balls of multiple colors. Each bin works like a stack; a ball has to follow the last-in first-out order. The player has to sort the balls by color such that each bin contains only balls of a single color. In this paper, we propose a physical zero-knowledge proof protocol for the ball sort puzzle using a deck of playing cards, which enables a prover to physically show that he/she knows a solution with $t$ moves of the ball sort puzzle without revealing it. Our protocol is the first zero-knowledge proof protocol for an interactive puzzle involving moving objects.

Recommendations

• Physical zero-knowledge proof for ripple effect
• Physical zero-knowledge proof for ripple effect
• Physical zero-knowledge proofs for Five Cells
• Interactive physical zero-knowledge proof for Norinori
• Physical Zero-Knowledge Proof for Suguru Puzzle

Cites work

• An improved physical ZKP for Nonogram
• Card-based ZKP protocol for Nurimisaki
• Card-based ZKP protocols for Takuzu and Juosan
• Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles
• Efficient card-based protocols for generating a hidden random permutation without fixed points
• Efficient card-based zero-knowledge proof for Sudoku
• Foundations for actively secure card-based cryptography
• Hide a liar: card-based ZKP protocol for Usowan
• How to construct physical zero-knowledge proofs for puzzles with a ``single loop condition
• Interactive physical zero-knowledge proof for Norinori
• Interactive physical ZKP for connectivity: applications to Nurikabe and Hitori
• Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle
• Physical zero-knowledge proof for Makaro
• Physical zero-knowledge proof for ripple effect
• Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen
• Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems
• Physical ZKP for Makaro using a standard deck of cards
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• The Knowledge Complexity of Interactive Proof Systems
• Two standard decks of playing cards are sufficient for a ZKP for Sudoku

Cited in

(6)

• Physically verifying the first nonzero term in a sequence: physical ZKPs for ABC End View and Goishi Hiroi
• Verifying the first nonzero term: physical ZKPs for ABC end view, Goishi Hiroi, and Toichika
• Physical zero-knowledge proofs for Five Cells
• How to play Old Maid with virtual players
• How to play Old Maid with virtual players
• Simulating virtual players for UNO without computers

This page was built for publication: Physical zero-knowledge proof for ball sort puzzle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149049)