An Improved Physical ZKP for Nonogram and Nonogram Color
This work addresses a niche problem in cryptographic puzzle protocols for enthusiasts and researchers, but it is incremental as it improves upon an existing method.
The paper tackled the impracticality and soundness error of a prior physical zero-knowledge proof protocol for Nonogram puzzles by developing a new card-based protocol that uses only regular paper cards and achieves perfect soundness, and extended it to support Nonogram Color with multiple colors.
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.