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.

By admin