Card-Based ZKP for Connectivity: Applications to Nurikabe, Hitori, and Heyawake

2380 Accesses
26 Citations
Explore all metrics

Abstract

During the last years, several card-based Zero-Knowledge Proof (ZKP) protocols for Nikoli’s puzzles have been designed. Although there are relatively simple card-based ZKP protocols for a number of puzzles, such as Sudoku and Kakuro, some puzzles face difficulties in designing simple protocols. For example, Slitherlink requires novel and elaborate techniques to construct a protocol. In this study, we focus on three Nikoli puzzles: Nurikabe, Hitori, and Heyawake. To date, no card-based ZKP protocol for these puzzles has been developed, partially because they have a relatively tricky rule that colored cells should form a connected area (namely a polyomino); this rule, sometimes referred to as “Bundan-kin” (in Japanese), complicates the puzzles, as well as facilitating difficulties in designing card-based ZKP protocols. We address this challenging task and propose a method for verifying the connectivity of hidden colored cells in a ZKP manner, such that we construct card-based ZKP protocols for the three puzzles.

Efficient Card-Based ZKP for Single Loop Condition and Its Application to Moon-or-Sun

Article Open access 19 August 2024

Interactive Physical ZKP for Connectivity: Applications to Nurikabe and Hitori

Card-Based Zero-Knowledge Proof Protocols for Graph Problems and Their Computational Model

Discover the latest articles, news and stories from top researchers in related subjects.

Artificial Intelligence

Use our pre-submission checklist

Avoid common mistakes on your manuscript.

Introduction

Zero-Knowledge Proofs (ZKP) were introduced by Goldwasser et al. [8]. This protocol involves two parties: a prover P and a verifier V. The prover P attempts to convince the verifier V that P possesses the solution s of a problem, without revealing any information about s. A ZKP protocol must satisfy the following three properties:

Completeness. If P knows the solution s, then P can convince V.
Soundness. If P does not know s, then P cannot convince V.
Zero-Knowledge. V learns nothing about s. Formally, simulated and actual protocol outputs follow the same probability distribution.

It was proven that for any NP-complete problem, there exists an interactive ZKP protocol [6]. Usually, ZKP protocols are executed on computers. In contrast, a physical ZKP protocol solely adopts physical algorithms with daily objects, such as cards, envelopes, and bags, while prohibiting large computations (i.e. no computer is allowed). In 2009, the first physical ZKP protocol was introduced for Sudoku [9], which is the most famous Nikoli^{Footnote 1} puzzle. Subsequently, efficient physical ZKP protocols for pencil puzzles have been proposed: Sudoku [25, 29], Nonogram [3, 24], Akari [1], Takuzu [1, 17], Kakuro [1, 16], Kenken [1], Makaro [2], Norinori [5], Slitherlink [15], Juosan [17], Suguru [23], Ripple Effect [27], Numberlink [26], Bridges [28], and Cryptarithmetic [13]. All these physical protocols employ a deck of cards as physical objects. Hence, we call such a protocol a card-based ZKP protocol hereinafter.^{Footnote 2}

In this study, we address three other Nikoli puzzles: Nurikabe, Hitori, and Heyawake^{Footnote 3}, with a common rule. Examples of their cases and solutions are illustrated in Figs. 1, 2, and 3. The common rule is about a geometric structure that requires white cells (in a solution) to form a connected area, namely, a polyomino. This rule, sometimes referred to as “Bundan-kin” (in Japanese), complicates the puzzles, and causes difficulties in designing simple card-based ZKP protocols.

Connectivity Constraint

Let us discuss this rule in a ZKP approach. Assume that a prover P has a polyomino in mind comprising white cells (as illustrated in the solutions in Figs. 1, 2, and 3), which we call a white-polyomino, on a grid, while a verifier solely knows the grid. The prover P attempts to convince the verifier V that P knows the white-polyomino without revealing it. Accordingly, a novel technique is required, as demonstrated later. Hereinafter, we refer to this common rule as the connectivity constraint.

Contributions

In this study, we construct card-based ZKP protocols for Nurikabe, Hitori, and Heyawake. To achieve this, we present a generic method to address the connectivity constraint. Specifically, after introducing some of the known techniques in Section 2, we present the generic method to verify the connectivity constraint, together with a simple observation. Then, using the generic method, we construct card-based ZKP protocols for Nurikabe, Hitori, and Heyawake in Sections 4, 5, and 6 , respectively. Finally, the paper is concluded in Section 7.

One might think that physical ZKP protocols for these three puzzles could be constructed by transforming a known physical ZKP protocol for an NP-complete problem, such as a lockable-box-based ZKP protocol for 3-Colorability [7]; however, such a transformation is infeasible because (1) the overhead must be included in the transformation, (2) it is challenging to construct a method for transforming an instance of a puzzle into a graph whose 3-colorability respects the solvability of the puzzle^{Footnote 4}, and (3) the transformed ZKP protocol does not capture the property of a puzzle. Therefore, we want to develop a direct (and specialized) card-based ZKP protocol for each of them.

This study is inspired by [15], which focused on Slitherlink and Masyu, where P has to convince V of a single loop property. We follow a similar strategy to [15]. That is, P first colors cells successively, such that the resulting cells are guaranteed to satisfy the connectivity constraint; then, V verifies all the remaining constraints. We note that the proposed protocols could not be constructed by simply adopting the existing technique [15].

An earlier version of this paper was presented and appeared as a conference paper [22]. The primary difference between the two is as follows. First, we have provided a generic method to address pencil puzzles with the connectivity constraint, including the idea behind our method in Section 3. Second, we have added Section 6 to present a card-based ZKP protocol for Heyawake using the generic method (whereas the conference paper solely handled Nurikabe and Hitori). Third, Sections 4.3 and 5.3 have been enhanced to provide full-security proofs (whereas the conference paper just provided sketches).

Nurikabe’s Rule

This puzzle^{Footnote 5} is played on a rectangular grid, where some cells contain numbers (Fig. 1). The objective is to color some cells^{Footnote 6} in black, such that the following conditions are met:

1.
Each numbered cell identifies the number of continuous black cells (separated by white cells). This region comprising black cells is called an island.
2.
An island must contain only one numbered cell.
3.
The white cells form a white-polyomino (called a sea).
4.
The sea cannot form a $2\times 2$ area.

Hitori’s Rule

This puzzle^{Footnote 7} comprises a grid and numbers where each cell contains a single number, as demonstrated in Fig. 2. The objective is to color some cells in black, with the following constraints:

1.
Each row and each column must contain only one occurrence of a number (on white cells).
2.
Two black cells cannot share a side; however, they can share a corner vertex.
3.
The numbered cells (white cells) must form a white-polyomino.

Heyawake’s Rule

This puzzle^{Footnote 8} (as illustrated in Fig. 3) is a grid comprising white cells and numbered cells. The grid is delimited by regions called rooms. The objective is to color some cells in black with the following constraints:

1.
Each room with a number has the corresponding number of black cells in it. A room with no number can have any number of black cells.
2.
Two black cells cannot share a side; however, they can share a corner vertex.
3.
The white cells must form a white-polyomino.
4.
White cells cannot stretch across more than two rooms in a straight line.

Preliminaries

In this section, we introduce some card and shuffle notations, and explain some of the existing card-based sub-protocols adopted in our constructions later.

Card

In our protocols, a deck of cards comprises clubs $\boxed {\clubsuit }\,\boxed {\clubsuit }\,\cdots$, hearts $\boxed {\heartsuit }\,\boxed {\heartsuit }\,\ldots$, and number cards $\boxed {1}\,\boxed {2}\,\ldots$, whose backs are all identical $\boxed {\varvec{?}}\,$. We encode three colors $\{\text {black}, \text {white}, \text {red}\}$ with the order of two cards as follows:

$$\begin{aligned} \boxed {\clubsuit }\,\boxed {\heartsuit }\, \rightarrow \ \text {black}, \quad \boxed {\heartsuit }\,\boxed {\clubsuit }\, \rightarrow \ \text {white}, \quad \boxed {\heartsuit }\,\boxed {\heartsuit }\, \rightarrow \ \text {red} . \end{aligned}$$

(1)

We call a pair of face-down cards $\boxed {\varvec{?}}\,\boxed {\varvec{?}}$ corresponding to a color according to the above encoding rule a commitment to the respective color. We also use the terms, black commitment, white commitment, and red commitment. We sometimes regard black and white commitments as bit values, based on the following encoding:

$$\begin{aligned} \boxed {\clubsuit }\,\boxed {\heartsuit }\, \rightarrow \ 0, \quad \boxed {\heartsuit }\,\boxed {\clubsuit }\, \rightarrow \ 1. \end{aligned}$$

(2)

For a bit $x\in \{0,1\}$, if a pair of face-down cards satisfies the encoding (2), we say that it is a commitment to x, denoted by

$$\begin{aligned} \underbrace{\boxed {\varvec{?}}\,\boxed {\varvec{?}}}_{x}\,. \end{aligned}$$

Pile-Shifting Shuffle [20, 30]

This shuffling action means to cyclically shuffle piles of cards. More formally, given m piles, each of which consists of the same number of face-down cards, denoted by $(\mathbf{p} _1, \mathbf{p} _2,\ldots , \mathbf{p} _{m})$, applying a pile-shifting shuffle (denoted by $\langle \cdot \Vert \cdots \Vert \cdot \rangle$), results in $(\mathbf{p} _{s\!+\!1},\mathbf{p} _{s\!+\!2},$ $\ldots ,\mathbf{p} _{s\!+\!m})$:

where s is uniformly and randomly selected from $\mathbb {Z}/m\mathbb {Z}$. Implementing a pile-shifting shuffle is simple: we adopt physical cases that can store a pile of cards, such as boxes and envelopes. Here, a player (or players) cyclically shuffles them manually until everyone (i.e. P and V) loses track of the offset. Note that “everyone” is an essential assumption for security.

Chosen Pile Protocol [5]

This protocol is an extended version of the “chosen pile cut” proposed in [14]. This protocol allows a prover P and a verifier V to obtain a pile of cards P chose from multiple piles, without V knowing which one it is. Some operations can be manipulated on this pile, and all the piles, including this pile, can be replaced in their initial order.

Precisely, given m piles $(\mathbf{p} _1,\mathbf{p} _2,\ldots ,\mathbf{p} _m)$ with 2m additional cards, the chosen pile protocol enables P and V to obtain the i-th pile $\mathbf{p} _i$ P chose (without revealing the index i) and reverts the sequence of m piles to their original order after applying other operations to $\mathbf{p} _i$.

1.
Using $m-1$ $\boxed {\clubsuit }\,$s and one $\boxed {\heartsuit }\,$, P places m face-down cards (denoted by row 2) below the given piles, such that only the i-th card is $\boxed {\heartsuit }\,$. We further position m cards (denoted by row 3) below the cards, such that only the first card is $\boxed {\heartsuit }\,$:
2.
Considering the cards in the same column as a pile, apply a pile-shifting shuffle to the sequence of piles.
3.
Reveal all the cards in row 2. Consequently, exactly one $\boxed {\heartsuit }$ appears, and the pile above the revealed $\boxed {\heartsuit }$ is the i-th pile (hence, P can obtain $\mathbf{p} _i$). After this step is invoked, other operations are applied to the chosen pile. Then, the chosen pile is reverted back to the i-th position in the sequence.
4.
Remove the revealed cards, i.e. the cards in row 2. (Note that we do not use the card $\boxed {\heartsuit }$ revealed in Step 3.) Subsequently, apply a pile-shifting shuffle.
5.
Reveal all the cards in row 3. Consequently, one $\boxed {\heartsuit }$ appears, and the pile above the revealed $\boxed {\heartsuit }$ is $\mathbf{p} _1$. Therefore, by shifting the sequence of piles (such that $\mathbf{p} _1$ becomes the leftmost pile in the sequence), we can obtain a sequence of piles whose order is the same as the original one without revealing any information about the order of the input sequence.

Input-Preserving Five-Card Trick [17]

Given two commitments to $a,b\in \{0,1\}$ based on the encoding rule (2), this sub-protocol [4, 17] reveals only the value of $a\vee b$ and restores commitments to a and b:

$$\begin{aligned} \underbrace{\boxed {\varvec{?}}\,\boxed {\varvec{?}}}_{a} \ \underbrace{\boxed {\varvec{?}}\,\boxed {\varvec{?}}}_{b} \ \rightarrow \ a\vee b \ \& \ \underbrace{\boxed {\varvec{?}}\,\boxed {\varvec{?}}}_{a} \ \underbrace{\boxed {\varvec{?}}\,\boxed {\varvec{?}}}_{b}\,; \end{aligned}$$

the original sub-protocol [4, 17] was designed to compute AND ($a \wedge b$); however, we adjust it to compute OR $(a \vee b)$ in Sections 5 and 6 .

The sub-protocol proceeds as follows:

1.
Add helping cards and swap the two cards of the commitment to b to obtain the negation $\overline{b}$, as follows:
$$\begin{aligned} \underbrace{\boxed {\varvec{?}}\,\boxed {\varvec{?}}}_{a} \ \underbrace{\boxed {\varvec{?}}\,\boxed {\varvec{?}}}_{b} \ \rightarrow \ \underbrace{\boxed {\varvec{?}}\,\boxed {\varvec{?}}}_{a} \ \boxed {\heartsuit }\ \underbrace{\boxed {\varvec{?}}\,\boxed {\varvec{?}}}_{\overline{b}} \ \boxed {\heartsuit }\,\boxed {\clubsuit }\,\boxed {\clubsuit }\,\boxed {\clubsuit }\,\boxed {\clubsuit }\,. \end{aligned}$$
2.
Rearrange the sequence of cards and turn over the face-up cards as:
$$\begin{aligned} {\boxed {\varvec{?}}\,\boxed {\varvec{?}}} \, \boxed {\heartsuit }\, {\boxed {\varvec{?}}\,\boxed {\varvec{?}}} \ \boxed {\heartsuit }\,\boxed {\clubsuit }\,\boxed {\clubsuit }\,\boxed {\clubsuit }\,\boxed {\clubsuit }\ \rightarrow \ \underset{\boxed {\heartsuit }}{\boxed {\varvec{?}}}\, \underset{\boxed {\clubsuit }}{\boxed {\varvec{?}}}\, \underset{\boxed {\clubsuit }}{\boxed {\heartsuit }} \, \underset{\boxed {\clubsuit }}{\boxed {\varvec{?}}}\, \underset{\boxed {\clubsuit }}{\boxed {\varvec{?}}} \ \rightarrow \ \underset{\boxed {\varvec{?}}}{\boxed {\varvec{?}}}\, \underset{\boxed {\varvec{?}}}{\boxed {\varvec{?}}}\, \underset{\boxed {\varvec{?}}}{\boxed {\varvec{?}}}\, \underset{\boxed {\varvec{?}}}{\boxed {\varvec{?}}}\, \underset{\boxed {\varvec{?}}}{\boxed {\varvec{?}}}\,. \end{aligned}$$
3.
Regarding cards in the same column as a pile, apply a pile-shifting shuffle to the sequence:
4.
Reveal all the cards in the first row.
1. (a)
  If the resulting sequence is $\boxed {\clubsuit }\,\boxed {\clubsuit }\,\boxed {\heartsuit }\,\boxed {\heartsuit }\,\boxed {\heartsuit }$ (up to cyclic shifts), then $a\vee b=0$.
2. (b)
  If it is $\boxed {\heartsuit }\,\boxed {\clubsuit }\,\boxed {\heartsuit }\,\boxed {\clubsuit }\,\boxed {\heartsuit }$ (up to cyclic shifts), then $a\wedge b=1$.
5.
After turning over all the face-up cards, apply a pile-shifting shuffle.
6.
Reveal the two cards in the second row; then, the revealed cards should include exactly one $\boxed {\heartsuit }\,$.
7.
Shift the sequence of piles, such that the revealed $\boxed {\heartsuit }$ is the leftmost card, and swap the two cards of the commitment to $\overline{b}$, to restore commitments to a and b.

How to Form a White Polyomino

In this section, we present a generic method to support constructions of a card-based ZKP protocol for a pencil puzzle with the connectivity constraint, i.e. white cells must form a white-polyomino. Using our method, we construct card-based ZKP protocols for our targets, i.e. Nurikabe, Hitori, and Heyawake, in Sections 4, 5, and 6 , respectively.

Idea

The idea behind our novel technique emerges from a simple observation. Suppose that we are given a rectangle grid where only one cell is white and the remaining cells are black. We will change the color of a black cell to white successively, as follows. If we color one of the four neighbor cells white around the initial white cell, then the resulting white cells should be connected and not separated. Therefore, if we repeatedly color one of the four neighbors white around any white cell, then we obtain a white-polyomino because we color only an adjacent cell around a white cell. We let the prover P perform this transformation of colors and make a desired polyomino to convince the verifier V that the resulting cells satisfy the connectivity constraint.

Subprotocol: 4-Neighbor Protocol

Before comprehensively describing our method, we present a subprotocol, called the 4-neighbor protocol that is beneficial to our generic construction. This protocol enables a prover P to indicate a specific commitment from commitments on a grid, including one of the four commitments next to the specific commitment without a verifier V knowing their exact positions.

Precisely, given pq commitments placed on a $p\times q$ grid, a prover P has an intended commitment, which we call a target commitment. The prover P attempts to reveal the target commitment and another one that lies next to the target commitment (without revealing their exact positions). Here, a verifier V should be convinced that the second commitment is a neighbor of the first one (without knowing which one), and V should be able to confirm the colors of both commitments. To handle the case where the target commitment is at the edge of the grid, we place commitments to red (as “dummy” commitments) on the left of the first column and below the last row, to prevent P from choosing a commitment that is not a neighbor. Accordingly, the size of the expanded grid is $(p+1)\times (q+1)$ (not $(p+2)\times (q+2)$, as will be explained in Step 3).

This subprotocol proceeds as follows:

1.
P and V pick the $(p+1)(q+1)$ commitments on the grid from left-to-right and top-to-bottom to make a sequence of commitments:
$$\begin{aligned} \boxed {\varvec{?}}\,\boxed {\varvec{?}}\ \ \boxed {\varvec{?}}\,\boxed {\varvec{?}}\ \ \boxed {\varvec{?}}\,\boxed {\varvec{?}}\ \ \boxed {\varvec{?}}\,\boxed {\varvec{?}}\ \cdots \ \boxed {\varvec{?}}\,\boxed {\varvec{?}}\,. \end{aligned}$$
2.
P uses the chosen pile protocol (Section 2) to reveal the target commitment.
3.
P and V pick all the four neighbors of the target commitment. Because a pile-shifting shuffle is a cyclic reordering, the distance between commitments is maintained (up to a given modulo). In other words, for a target commitment (not at the edge), the possible four neighbors are at a distance for the left or right one, and $p+1$ for the bottom or top one. Therefore, P and V can determine the positions of all the four neighbors. Recall that dummy commitments are placed in the leftmost column and bottom row. If a target commitment is at the edge, for instance, top rightmost, its right commitment is the dummy at the second from the top leftmost, while its top commitment is the dummy at the bottom rightmost position. Consequently, a $(p+1)\times (q+1)$ grid suffices.
4.
Among these four neighbors, P chooses one commitment using the chosen pile protocol and reveals it.
5.
P and V end the second and first chosen pile protocols.

Methods

Using the 4-neighbor protocol presented in Section 3.2, we present a generic method to perform the transformation of colors mentioned in Section 3.1, without revealing any information on the resulting cells.

Assume that there is a grid with $p\times q$ cells. P attempts to arrange white commitments on the grid, such that they form a white-polyomino while V is convinced that the placement of commitments is certainly a white-polyomino. Our generic method is as follows:

1.
P and V place a commitment to black (i.e. $\boxed {\clubsuit }\,\boxed {\heartsuit }\,$) on every cell and commitments to red as mentioned in Section 3.2, such that they have $(p+1)(q+1)$ commitments on the board.
2.
P uses the chosen pile protocol to choose one black commitment that P attempts to change.
1. (a)
  V swaps the two cards constituting the chosen commitment, such that it becomes a white commitment (recall the encoding (1)).
2. (b)
  P and V end the chosen pile protocol to return the commitments to their original positions.
3.
P and V repeat the following steps exactly $pq-1$ times.
1. (a)
  P chooses one white commitment as a target and one black commitment among its neighbors using the 4-neighbor protocol; the neighbor is chosen such that P attempts to make it white.
2. (b)
  V reveals the target commitment. If it corresponds to white, then V continues; otherwise V aborts.
3. (c)
  V reveals the neighbor commitment (chosen by P). If it corresponds to black, then P makes the neighbor white or keeps it black (depending on P’s choice) by executing the following steps; otherwise V aborts.
  1. (i)
    If P attempts to change the commitment, P places face-down club-to-heart pair below it; otherwise, P places a heart-to-club pair:
  2. (ii)
    Regarding cards in the same column as a pile, V applies a pile-shifting shuffle to the sequence of piles:
  3. (iii)
    V reveals the two cards in the second row. If the revealed right card is $\boxed {\heartsuit }\,$, then V swaps the two cards in the first row; otherwise V does nothing.
4. (d)
  P and V end the 4-neighbor protocol.

After this process, V is convinced that all the white commitments represent a white polyomino. Therefore, this method enables a prover P to make a solution that only P has, guaranteed to satisfy the connectivity constraint.

If the number of white cells in the final polyomino, e.g., k, is public to a verifier V, it is sufficient that in Step 3, P and V repeat $k-1$ times and in Step 3c, V simply swaps the two cards comprising the neighbor commitment to make it white (without P’s choice).

ZKP Protocol for Nurikabe

In this section, we propose a card-based ZKP protocol for Nurikabe. Our protocol comprises two phases: the setup and verification phases, which are presented in Sections 4.1 and 4.2 , respectively. Its security proof is provided in Section 4.3.

Consider a puzzle instance of a $p\times q$ grid containing m numbered cells, such that the i-th numbered cell (in any order) has a number $x_i$ for every i, $1\le i\le m$. Recall that an island of a Nurikabe puzzle must contain exactly one numbered cell, and the number of black cells inside the island is indicated by the number written on the numbered cell. Therefore, the number of white cells in the solution (namely, in the white-polyomino), denoted by $N_w$, is the difference between the number of total and black cells (including the numbered cells). Therefore, we have

$$\begin{aligned} N_w=pq-\displaystyle \sum _{i=1}^mx_i. \end{aligned}$$

This number $N_w$ can be regarded as public information, and indeed, we explicitly use the number $N_w$ in our protocol.

Setup Phase

The prover P (having a polyomino in mind as a solution) and the verifier V adopt the generic method presented in Section 3, where $N_w$ is used as public information, such that Step 3 is repeated $N_w-1$ times. The resulting configuration is a placement of $(p+1)(q+1)$ commitments on the board where the commitments in the leftmost column and the bottom row correspond to red, and the remaining commitments represent the solution according to the encoding (1) (because P makes the white-polyomino corresponding to the solution). Subsequently, V is convinced that all the white commitments form a white-polyomino, i.e. the connectivity constraint is satisfied.

Verification Phase

V first verifies that the current commitments placed on the grid (after the setup phase) satisfy the rule 4 (forbidden $2\times 2$ area). Then, V verifies the rules 1 and 2 , relative to the black commitments (island constraints).

Sea rule: Forbidden area (rule 4). The prover P attempts to convince V that any $2\times 2$ area contains at least one black cell. Note that all $2\times 2$ areas are determined, given an initial grid. Indeed, for a given $p\times q$ grid, there are $(p-1)(q-1)$ possible areas.

Hence, P and V consider each $2\times 2$ area (consisting of four commitments) successively (in any order), and will repeat the following for each possible area.

1.
P chooses a black commitment on this $2\times 2$ area via the chosen-pile protocol applied to the four commitments.
2.
V reveals the commitment chosen by P. If the revealed commitment corresponds to black, then V is convinced that the $2\times 2$ area is not solely formed by white commitments. Otherwise, V aborts:

Island rules (rule 1, 2). P attempts to convince V that the black cells respect the constraints. There are two verifications to consider: solely one-numbered cell for a given region (island) and all black commitments are connected inside the island. These two constraints are verified in the following protocol.

Let $n\ge 2$ be the number written on a given numbered cell.^{Footnote 9} We are going to change the n continuous black commitments (on the island) into red ones successively using the 4-neighbor protocol. Notice that we use red commitments to ensure that each black cell is checked exactly once.

1.
V reveals the commitment on the numbered cell. If it corresponds to black, V replaces it with a red commitment; otherwise V aborts.
2.
Repeat the following steps exactly $n-1$ times.
1. (a)
  P uses the 4-neighbor protocol to choose a red commitment as a target, and one black commitment among its neighbors.
2. (b)
  V reveals the target commitment. If it corresponds to red, then V continues; otherwise V aborts.
3. (c)
  V reveals the neighbor commitment (chosen by P). If it corresponds to black, V replaces it with a red commitment; otherwise V aborts.
4. (d)
  P and V end the 4-neighbor protocol to return the commitments to their original positions.

Now, V is convinced that the size of the island comprising black cells is greater than or equal to n because Step 2 just indicates that there are $n-1$ continuous black cells adjacent to the number cell. To verify that the size of the island is equal to n, it suffices to prove that there exists no black cell around the island. Accordingly, we change all the n red commitments into white ones successively, and confirm that there is no black commitment around them. Notice that we can check each red commitment exactly once.

3.
V replaces the commitment on the numbered cell with a white commitment.
4.
Repeat the following steps exactly $n-1$ times.
1. (a)
  P uses the chosen pile protocol to choose a red commitment.
2. (b)
  V reveals the chosen commitment. If it corresponds to red, V continues; otherwise V aborts.
3. (c)
  Recall that P attempts to verify that any of four neighbor commitments is not black. Recall also the encoding (1), i.e. the left card of a white or red commitment is a heart $\boxed {\heartsuit }\,$. V reveals the left card of each of the four neighbors. If all of them are hearts (which means that all the commitments do not correspond to black), V replaces the chosen commitment with a white commitment; otherwise V aborts:
4. (d)
  P and V end the chosen pile protocol to revert the commitments to their original positions.

By applying the aforementioned steps to all the numbered cells, V is convinced that the placement of the commitments satisfies all the constraints, i.e. P possesses the solution.

Security Proofs

We present the following theorems to demonstrate that our protocol respects the security properties.

Theorem 1

(Completeness) If P knows a solution of a Nurikabe grid, then P can convince V.

Proof

Suppose that P, which knows the solution s of the grid, runs the setup phase as in Section 4.1. We will demonstrate that P can perform the proofs for the sea formation and the verification phases.

Setup: In this phase, the goal of P is to prove that the white commitments form a white-polyomino (rule 3). Because s is a solution to the initial grid, the white cells appearing (in the solution) are connected. Hence, P can always pick a white commitment. The corresponding neighbor can be changed into a white commitment, thereby ensuring that the resulting figure is connected.

Verification: The verifier V must be convinced that rules 1, 2, and 4 hold. First, the forbidden area (rule 4) must be verified. Because s is a solution, there is no $2\times 2$ area solely comprising white commitments on the grid. Therefore, by checking each $2\times 2$ area, there will be at least one black commitment among the chosen four commitments on the area. Hence, P can choose (via the chosen-pile protocol) such a black commitment.

Second, the island rules (rules 1 and 2 ) must be verified. Because s is a solution, each numbered cell is in a region (island) with the corresponding number of black commitments and no additional numbered cell. Consider a numbered cell equal to $n>2$ (the case $n=1$ is straightforward because it must have its four neighbors all in white, which can be verified by simply revealing them). There are $n-1$ black commitments without counting the commitment on the numbered cell. Hence, P and V can apply the first sub-routine exactly $n-1$ times. This implies that all the black commitments are turned into red ones. From here, V is convinced that the region contains at least n black commitments. However, this could be more than n, if two regions are not separated. Hence, the second sub-routine ensures that the region does not comprise more than n black commitments. Note that at this point, all black cells are encoded as red commitments: $\boxed {\heartsuit }\,\boxed {\heartsuit }\,$.

Now, V replaces the commitment on the numbered cell by a white commitment. When revealing the left card of the four neighbors for a given previous black commitment, there are all $\boxed {\heartsuit }$ because all previous black commitments are encoded as $\boxed {\heartsuit }\,\boxed {\heartsuit }\,$. The verified commitments are then turned into white ones; hence, V is convinced that no red commitment is checked twice.

Finally, because all the verifications have been checked, we proved that if P has a solution, then the verifications will always succeed. $\square$

Theorem 2

(Soundness) If P does not provide a solution of a Nurikabe grid, then P cannot convince V.

Proof

Suppose that P does not provide a solution for the grid in the setup phase. We will demonstrate that V will always detect it.

Suppose that the commitments are correct, meaning that the white commitments form a white polyomino. (If it is not the case, then V aborts because a black commitment can be whitened if and only if one of its four neighbors is already whitened.)

We can distinguish two cases, each corresponding to a part of the verification phase.

Forbidden area. V verifies all possible $2\times 2$ areas of the grid. If one of them solely comprises only white commitments, then P cannot choose a black one. Therefore, V will reveal a white one, as P cannot act otherwise.
Island rules. Consider a numbered cell equal to $n\,(>\!2)$. We divide all the invalid cases into three, depending on the size of their islands. Each example is presented as follows:
1. 1.
  Consider the size is less than n, i.e. only $\ell \,(<\!n)$ black commitments constitute the island. During Step 2c for the $\ell$-th instance, the neighbor commitment cannot correspond to a black commitment; thus, V aborts.
2. 2.
  Consider the size is equal to n, but some other numbered cells are inside the island. Note that when the verification is completed for the numbered cell equal to n, the commitments on the other numbered cells will become white ones. Consequently, in Step 1, a white commitment should appear when V verifies the other numbered cells, and then V aborts.
3. 3.
  Consider the size is greater than n^{Footnote 10}. This means that after Step 2, there are more black commitments around red commitments. V can detect it in Step 4c because a club $\boxed {\clubsuit }$ should appear when V reveals the left card of each of four neighbors of a red commitment.

Therefore, if P does not provide a solution, V always detects it. $\square$

Theorem 3

(Zero-knowledge) V learns nothing about P’s solution of a given Nurikabe grid.

Proof

We adopt the same proof technique as in [9]: zero-knowledge is induced by a description of an efficient simulator that simulates the interaction between a cheating verifier and a real prover. Here, although the simulator does not have a solution, it can swap cards for different ones during shuffles. The simulator acts as follows:

The simulator constructs a random white polyomino of size $N_w$.
During the verification of the forbidden area rule, each possible $2\times 2$ area is verified. For a given area, the corresponding commitments are shuffled; thus, the simulator can swap the target commitment by a black commitment via the chosen-pile protocol.
During the verification of the island rule, the simulator replaces the target commitment by a red one, and its corresponding neighbor by a black one, for the first sub-routine. For the second sub-routine, the simulator changes the target commitment by a red commitment, and also change the left card of each of the four neighbors by heart cards.

Note that the chosen pile and 4-neighbor protocols use shuffle techniques; thus, the simulator can replace shuffled cards when applying these protocols. The simulated and real proofs are indistinguishable; hence, V learns nothing about P’s solution. $\square$

ZKP Protocol for Hitori

In this section, we present a card-based ZKP protocol for Hitori. Our protocol comprises the setup and verification phases, which are presented in Sections 5.1 and 5.2 , respectively. Its security proof is provided in Section 5.3.