An Improved Physical ZKP for Nonogram

06/26/2021
by   Suthee Ruangwises, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset