An Improved Physical ZKP for Nonogram

Nonogram is a logic puzzle consisting of a rectangular grid with an objective to color every cell black or white such that the lengths of blocks of consecutive black cells in each row and column are equal to the given numbers. In 2010, Chien and Hon developed the first physical zero-knowledge proof for Nonogram, which allows 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 machine to seal the cards, which are difficult to find in everyday life. Their protocol also has a nonzero soundness error. In this paper, we propose a more practical physical zero-knowledge proof for Nonogram that uses only a deck of regular paper cards and also has perfect soundness.