Physical Zero-Knowledge Proof for Ball Sort Puzzle

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.

arXiv commentThis paper has appeared at CiE 2023. arXiv admin note: text overlap with arXiv:2302.01235

References in corpus (5)

• Physical Zero-Knowledge Proof for Numberlink Puzzle and $k$ Vertex-Disjoint Paths Problem
• Two Standard Decks of Playing Cards are Sufficient for a ZKP for Sudoku
• Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems
• Physical Zero-Knowledge Proof for Ripple Effect
• Physical ZKP for Makaro Using a Standard Deck of Cards

Cited by in corpus (3)

• Printing Protocol: Physical ZKPs for Decomposition Puzzles
• Verifying the First Nonzero Term: Physical ZKPs for ABC End View, Goishi Hiroi, and Toichika
• Simulating Virtual Players for UNO without Computers