Two Standard Decks of Playing Cards are Sufficient for a ZKP for Sudoku

Abstract

Sudoku is a famous logic puzzle where the player has to fill a number between 1 and 9 into each empty cell of a $9\times 9$ grid such that every number appears exactly once in each row, each column, and each $3\times 3$ block. In 2020, Sasaki et al. developed a physical card-based protocol of zero-knowledge proof (ZKP) for Sudoku, which enables a prover to convince a verifier that he/she knows a solution of the puzzle without revealing it. Their protocol uses 90 cards, but requires nine identical copies of some cards, which cannot be found in a standard deck of playing cards (consisting of 52 different cards and two jokers). Hence, nine identical standard decks are required to perform that protocol, making the protocol not very practical. In this paper, we propose a new ZKP protocol for Sudoku that can be performed using only two standard decks of playing cards, regardless of whether the two decks are identical or different. In general, we also develop the first ZKP protocol for a generalized $n\times n$ Sudoku that can be performed using a deck of all different cards.

A shortened version of this paper has appeared at COCOON 2021

References in corpus (3)

• Physical Zero-Knowledge Proof for Numberlink Puzzle and $k$ Vertex-Disjoint Paths Problem
• Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems
• Physical Zero-Knowledge Proof for Ripple Effect

Cited by in corpus (6)

• Physical Zero-Knowledge Proof for Ripple Effect
• Physical ZKP for Makaro Using a Standard Deck of Cards
• Physical Zero-Knowledge Proof for Ball Sort Puzzle
• An Improved Physical ZKP for Nonogram and Nonogram Color
• Printing Protocol: Physical ZKPs for Decomposition Puzzles
• Verifying the First Nonzero Term: Physical ZKPs for ABC End View, Goishi Hiroi, and Toichika