Card-Based ZKP Protocol for Nurimisaki

Overview & Synopsis

Proving to someone else the knowledge of a secret without revealing any of its information is an interesting feature in cryptography. The best solution to solve this problem is a Zero-Knowledge Proof (ZKP) protocol. Nurimisaki is a Nikoli puzzle. The goal of this game is to draw a kind of abstract painting ("Nuri") that represents the sea with some capes ("Misaki") of an island (represented by white cells). For this, the player has to fulfill cells of a grid in black (representing the sea) in order to draw some capes while respecting some simple rules. One of the specificity of the rules of this game is that the cells called "Misaki" can only have one white neighbour and all white cells need to be connected. In 2020, this puzzle has been proven to be NP-complete. Using a deck of cards, we propose a physical ZKP protocol to prove that a player knows a solution of a Nurimisaki grid without revealing any information about the solution.