Printing Protocol: Physical ZKPs for Decomposition Puzzles
arXiv:2302.01235 · doi:10.1007/s00354-024-00266-1
Abstract
Decomposition puzzles are pencil-and-paper logic puzzles that involve partitioning a rectangular grid into several regions to satisfy certain rules. In this paper, we construct a generic card-based protocol called printing protocol, which can be used to physically verify solutions of decompositon puzzles. We apply the printing protocol to develop card-based zero-knowledge proof protocols for two such puzzles: Five Cells and Meadows. These protocols allow a prover to physically show that he/she knows solutions of the puzzles without revealing them.
arXiv commentA preliminary version of this paper has appeared at LATINCRYPT 2023
References in corpus (7)
- Physical Zero-Knowledge Proof for Numberlink Puzzle and 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
- An Improved Physical ZKP for Nonogram and Nonogram Color
- Physical Zero-Knowledge Proof for Ball Sort Puzzle