An Improved Physical ZKP for Nonogram and Nonogram Color

Abstract

Nonogram is a pencil puzzle consisting of a rectangular white grid where the player has to paint some cells black according to given constraints. In 2010, Chien and Hon constructed a physical card-based zero-knowledge proof protocol for Nonogram, which enables a prover to physically show that he/she knows a solution of the puzzle without revealing it. However, their protocol requires special tools such as scratch-off cards and a sealing machine, making it impractical to implement in real world. The protocol also has a nonzero soundness error. In this paper, we develop a more practical card-based protocol for Nonogram with perfect soundness that uses only regular paper cards. We also show how to modify our protocol to make it support Nonogram Color, a generalization of Nonogram where the player has to paint the cells with multiple colors.

A preliminary version of this paper has appeared at COCOA 2021

References in corpus (4)

• 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 (5)

• 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
• NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
• Tatami Printer: Physical ZKPs for Tatami Puzzles