An Improved Physical ZKP for Nonogram
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- How to construct physical zero-knowledge proofs for puzzles with a “single loop” conditionTheoretical Computer Science, 2021
- Efficient card-based zero-knowledge proof for SudokuTheoretical Computer Science, 2020
- Physical Zero-Knowledge Proof for Numberlink Puzzle and k Vertex-Disjoint Paths ProblemNew Generation Computing, 2020
- Proofs that yield nothing but their validity and a methodology of cryptographic protocol design2019
- Card-Based Physical Zero-Knowledge Proof for KakuroIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2019
- Secure implementations of a random bisection cutInternational Journal of Information Security, 2019
- Card-Based Protocols Using Regular Polygon CardsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2017
- Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku PuzzlesTheory of Computing Systems, 2008
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989