Card-Based ZKP Protocol for Nurimisaki⋆Léo Robert1,2 , Daiki Miyahara3,4 , Pascal Lafourcade1,2 , andTakaaki Mizuki5,4
1

Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne,
2
LIMOS, 63000 Clermont-Ferrand, France{leo.robert,pascal.lafourcade}@uca.fr
3
The University of Electro-Communications, Tokyo, Japan
4
National Institute of Advanced Industrial Science and Technology, Tokyo, Japan
5
Cyberscience Center, Tohoku University, Sendai, Japan

Abstract. 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 kindof 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, thispuzzle has been proven to be NP-complete.
Using a deck of cards, we propose a physical ZKP protocol to prove thata player knows a solution of a Nurimisaki grid without revealing any
information about the solution.

Keywords: Zero-knowledge proof, Pencil Puzzle, Card-based cryptography, Nurimisaki

1Introduction

The democratization of computers and network systems has fuelled thevirtualization of interactions and processes such as communication, payments, and elections. Proving the knowledge of some secret without re⋆This paper appears in Proceedings of SSS 2022. This version of the contribution has been accepted for publication, after peer review but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/
978-3-031-21017-4_19. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use: https://www.springernature.com/gp/
open-research/policies/accepted-manuscript-terms.

vealing any bit of information from that secret is crucial in our today’ssociety. This issue can be applied to numerous contexts.
For instance, a client would like to connect to a server via a password
without revealing the password. Another example is database management, where an entity could ask if a piece of information is in a database
without asking for factual data. A third example can be given in the electronic voting system where the voters want to be sure that the ballots
are correctly mixed (without revealing how the mix was done).
A cryptographic tool exists for all the previous examples, called a
Zero-Knowledge Proof (ZKP) protocol. It enables a prover P to convincea verifier V that P knows a secret s without revealing anything otherthan it. A ZKP protocol must verify the following three properties:– Completeness: If P knows s then the protocol ends without aborting(meaning that V is convinced that P has s);– Soundness: If P does not have s then V will detect it;– Zero-Knowledge: V learns nothing about s.
In practice, ZKP protocols are typically executed by computers. However, their understanding is difficult for the uninitiated. We take a more
direct approach to the notion of ZKP and construct a protocol using
physical objects like playing cards and envelopes. It allows us to present
the notion of ZKP protocols without deep mathematical backgrounds andalso to extend the existing literature.
The first physical ZKP protocol [7] for a Sudoku grid was constructedusing a deck of cards. Since this novel protocol was devised, several
teams in the world have proposed physical ZKP protocols using a deckof cards for pencil puzzles, such as Sudoku [24,19], Akari [1], Takuzu [1],Kakuro [1,13], KenKen [1], Makaro [2], Norinori [5], Slitherlink [11], Suguru [16], Nurikabe [17], Ripple Effect [22], Numberlink [20], Bridges [21],Cryptarithmetic [8], Shikaku [23], and Nonogram [3,18].
Why shall we propose a new card-based ZKP protocol for anotherNikoli puzzle? For us, it is similar to the question: Why shall we provethat a puzzle is NP-complete? People want to know if a puzzle is NPcomplete in order to know if the puzzle is difficult or not for a computer
to solve it. Card-based ZKP protocols are quite similar; once a puzzle isshown to be NP-complete, a natural question is: Can we design a physical
ZKP protocol? This is an intellectual challenge on the puzzle. Moreover,each puzzle has different rules and specificity, which force us to imagine new physical ZKP techniques. For instance, consider a Nikoli puzzle,
Nurimisaki, which we will deal with in this paper; then, its rules combine for the first time some connectivity, neighbourhood restriction, and
2

3

3
4

4

4

4
4

4

Fig. 1. Nurimisaki example (left) with its solution (right).

straight line with counting, as seen later. A previous work [?] (in Japanese,
unpublished) proposed a card-based ZKP protocol for Nurimisaki. Yet,the protocol is not optimal since it prepares another grid to verify therules (so the number of cards is large). Moreover, elaborate but complex
techniques are used (e.g., using another grid to represent the in-spanningtree of P ’s solution). In contrast, our protocol has a more direct approachwith closer interaction to the real game. Before giving our contributions,let us define the rules of the Nurimisaki puzzle.
Nurimisaki Rules. Figure 1 shows a puzzle instance of Nurimisaki. The
goal for Nurimisaki puzzle is to color in black some cells on the grid,under the following rules:
1. A cell with a circle is called a “Misaki”. A Misaki has only one cellof its neighbours (vertically or horizontally) remaining white and therest black.
2. The number written in a Misaki cell indicates the number of white cells
in straight line from the Misaki. If there is no number, any number ofwhite cells is allowed.
3. White cells without a circle cannot be a Misaki.
4. A 2 × 2 square cannot be composed of only black or white cells.
5. White cells are connected.
Nurimisaki puzzle was recently proven NP-complete in [9]; hence, it
is a natural question to construct a physical ZKP protocol for this fun
puzzle. Although Goldwasser et al. [6] proved that any NP-complete problem has its corresponding interactive ZKP protocol, simple physical ZKP
protocols are always sollicited as mentioned above.
Contributions. We propose a physical ZKP protocol that only uses cards
and envelopes. We rely on some classical existing card-based sub-protocols
in order to be able to construct our ZKP protocol. The main difficulty inthis Nurimisaki game that seems to be simple, is that existing techniques
proposed in the literature since few years cannot be applied directly. The
3

main trick is to find an encoding that allows us to apply several subprotocols in the right order to obtain a secure ZKP protocol. For this, we
propose an original way to combine several techniques to design our ZKP
protocol with a reasonable amount of cards and manipulations.
Outline. In Section 2, we introduce our encoding scheme using cards inorder to represent a gird of the game and a solution. We also give some
sub-protocols that are used in our construction. In Section 3, we give our
ZKP protocol for Nurimisaki. Before concluding in the last section, wegive the security proof of our ZKP protocol in Section 4.

2

Preliminaries

We explain the notations and sub-protocols used in our constructions.
Cards and Encoding. The cards we use in our protocols consist of clubs♣ ♣ · · · , hearts ♡ ♡ · · · , and numbered cards 1 2 · · · , whose backs are
identical ? . We encode three colors {black, white, red} with the order of
two cards as follows:♣ ♡ → black,♡ ♣ → white,♡ ♡ → red.

(1)

We call a pair of face-down cards ? ? corresponding to a color according to the above encoding rule a commitment to the respective color.
We also use the terms, a black commitment, a white commitment, and a
red commitment. We sometimes regard black and white commitments as
bit values, based on the following encoding scheme:♣ ♡ → 0,♡ ♣ → 1.

(2)

For a bit x ∈ {0, 1}, if a pair of face-down cards satisfies the encoding (2),we say that it is a commitment to x, denoted by ? ? .
| {z }x

We also define two other encoding [25,22]:– ♣-scheme: for x ∈ Z/pZ, there are p cards composed of p − 1 ♡s andone ♣, where the ♣ is located at position (x + 1) from the left. For
example, 2 in Z/4Z is represented as ♡ ♡ ♣ ♡ .
– ♡-scheme: it is the same encoding as above but the ♡ and ♣ arereversed. For instance, 2 in Z/4Z is represented as ♣ ♣ ♡ ♣ .
4

2.1

Pile-shifting Shuffle [25,15]

This shuffling action means to cyclically shuffle piles of cards. More formally, given m piles, each of which consists of the same number of facedown cards, denoted by (p1 , p2 , . . . , pm ), applying a pile-shifting shuffle(denoted by ⟨·∥ · · · ∥·⟩) results in (ps+1 , ps+2 , . . . , ps+m ):
*
+
?
?
?
?
? ··· ?
|{z} |{z} · · · |{z} → |{z} |{z}|{z} ,p1
p2
pm
ps+1 ps+2
ps+m
where s is uniformly and randomly chosen from Z/mZ. Implementing apile-shifting shuffle is simple: we use physical cases that can store a pile ofcards, such as boxes and envelopes; a player (or players) cyclically shuffles
them manually until everyone (i.e., the prover P and the verifier V ) loses
track of the offset.
2.2

Input-preserving Five-card Trick [12]Given two commitments to a, b ∈ {0, 1} based on the encoding rule (2),this sub-protocol [4,12] reveals only the value of a ∨ b as well as restorescommitments to a and b: ? ? ? ? → a ∨ b & ? ? ? ? .
| {z } | {z }| {z } | {z }
a

a

b

b

The original sub-protocol [4,12] was designed for computing AND(a ∧ b), but we adjust it to compute OR (a ∨ b):
1. Add helping cards and swap the two cards of the commitment to b sothat we have the negation b, as follows:? ? ? ? → ? ? ♡ ? ? ♡ ♣ ♣ ♣ ♣.
| {z } | {z }| {z }| {z }abab

2. Rearrange the sequence of cards and turn over the face-up cards as:? ? ♡ ? ? ♡♣♣♣♣ → ? ? ♡ ? ? → ? ? ? ? ?.
♡♣♣♣♣? ? ? ? ?
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.
5(a) If it is ♣ ♣ ♡ ♡ ♡ (up to cyclic shifts), then a ∨ b = 0.
(b) If it is ♡ ♣ ♡ ♣ ♡ (up to cyclic shifts), then a ∨ b = 1.
5. After turning over all the face-up cards, apply a pile-shifting shuffle.
6. Reveal all the cards in the second row; then, the revealed cards should
include exactly one ♡ .
7. Shift the sequence of piles so that the revealed ♡ is the leftmost cardand swap the two cards of the commitment to b to restore commitments to a and b.

2.3

Mizuki–Sone Copy Protocol [14]Given a commitment to a ∈ {0, 1} along with four cards ♣ ♡ ♣ ♡ , theMizuki–Sone copy protocol [14] outputs two commitments to a:? ? ♣♡♣♡ → ? ? ? ? .
| {z }| {z } | {z }
a

a

a

0

? ?
| {z }

0

.

→

.

*

?
?
?

2. Apply a pile-shifting shuffle as follows:

? ?
? ?
? ?

?
?
?

+

a

? ?
| {z }? ?
| {z }

1. Turn all cards face-down and set the commitments as follows:

2.4

.

a

a

? ?
| {z }or♡♣? ?
| {z }a? ?
| {z }a♣♡? ?
| {z }

3. Reveal the two above cards to obtain either a or a as follows:

How to Form a White Polyomino [17]We introduce the generic method of [17] to address the connectivity constraint (rule 5). Given a grid where all cells are black, it enables P to
make white connected cells, i.e., white-polyomino, without revealing anything to V . We first describe two crucial sub-protocols: the chosen pile
protocol and the 4-neighbor protocol.
6Chosen pile protocol [5]. The chosen pile protocol allows P to choose apile of cards without V knowing which one. This pile can be manipulated
and all the commitments are replaced to their initial order afterward.
This protocol is an extended version of the “chosen pile cut” proposedin [10]. Given m piles (p1 , p2 , . . . , pm ) with 2m additional cards, the chosen pile protocol enables a prover P to choose the i-th pile pi (without
revealing the index i) and revert the sequence of m piles to their originalorder after applying other operations to pi .
1. Using m − 1 ♣ s and one ♡ , P places m face-down cards encodingi − 1 in the ♡-scheme (denoted by row 2 ) below the given piles, i.e.,
only the i-th card is ♡ . We further put m cards encoding 0 in the♡-scheme (denoted by row 3 ):?
? ... ?
?
? ... ?
|{z} |{z}|{z} |{z} |{z}
|{z}
p1

p2

pi−1

pi

pi+1

pm

?

? ... ?

?

? . . . ? ← row 2

♣

♣

♡

♣

?

? ... ?

?

? . . . ? ← row 3

♡

♣

♣

♣

♣
♣

♣
♣

2. Considering the cards in the same column as a pile, apply a pileshifting shuffle to the sequence of piles.
3. Reveal all the cards in row 2. Then, exactly one ♡ appears, and thepile above the revealed ♡ is the i-th pile (and hence, P can obtainpi ). After this step is invoked, other operations are applied to thechosen pile. Then, the chosen pile is placed back to the i-th positionin the sequence.
4. Remove the revealed cards, i.e., the cards in row 2. (Note, therefore,that we do not use the card ♡ revealed in Step 3.) Then, apply apile-shifting shuffle.
5. Reveal all the cards in row 3. Then, one ♡ appears, and the pile above
the revealed ♡ is p1 . Therefore, by shifting the sequence of piles (suchthat p1 becomes the leftmost pile in the sequence), we can obtain asequence of piles whose order is the same as the original one without
revealing any information about the order of the input sequence.
Sub-protocol: 4-Neighbor Protocol [17]. Given pq commitments placed on
a p × q grid, a prover P has a commitment in mind, which we call a target
commitment. The prover P wants to reveal the target commitment andanother 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
7one) as well as V should be able to confirm the colors of both the commitments. To handle the case where the target commitment is at the edge ofthe grid, we place commitments to red (as “dummy” commitments) in theleft of the first column and below the last row to prevent P from choosing
a commitment that is not a neighbor. Thus, the size of the expanded gridis (p + 1) × (q + 1). This sub-protocol proceeds as follows.
1. P and V pick the (p + 1)(q + 1) commitments on the grid fromleft-to-right and top-to-bottom to make a sequence of commitments:? ? ? ? ? ? ? ? ··· ? ? .
2. P uses the chosen pile protocol to reveal the target commitment.
3. P and V pick all the four neighbors of the target commitment. Sincea pile-shifting shuffle is a cyclic reordering, the distance between commitments are kept (up to a given modulo). That is, for a target commitment (not at any the edge), the possible four neighbors are at
distance one for the left or right one, and p + 1 for the bottom or
top one so that P and V can determine the positions of all the fourneighbors.
4. Among these four neighbors, P chooses one commitment using thechosen pile protocol and reveals it.
5. P and V end the second and first chosen pile protocols.
Forming white-polyomino. Assume that there is a grid having p × q cells.
P wants to arrange white commitments on the grid such that they form awhite-polyomino while V is convinced that the placement of commitments
is surely a white-polyomino. The sub-protocol proceeds as follows.
1. P and V place a commitment to black (i.e., ♣ ♡ ) on every cell andcommitments to red as mentioned above so 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 wants to change.
(a) V swaps the two cards constituting the chosen commitment sothat it becomes a white commitment (recall the encoding (1)).
(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.
(a) P chooses one white commitment as a target and one black commitment among its neighbors using the 4-neighbor protocol; theneighbor is chosen such that P wants to make it white.
(b) V reveals the target commitment. If it corresponds to white, thenV continues; otherwise V aborts.
8

(c) V reveals the neighbor commitment (chosen by P ). If it corresponds to black, then P makes the neighbor white or keep it black(depending on P ’s choice) by executing the following steps; otherwise V aborts.
i. If P wants to change the commitment, P places face-downclub-to-heart pair below it; otherwise, P places a heart-to-club
pair: ? ? → ? ? or ? ? .
? ?
? ?
♣

♡

♡

♣

ii. Regarding cards in the same column asa pile, V applies
a pile?
?
? ?
shifting shuffle to the sequence of piles:
→
?
?
? ? .
iii. V reveals the two cards in the second row. If the revealed
right card is ♡ , then V swaps the two cards in the first row;otherwise V does nothing.
(d) P and V end the 4-neighbor protocol.
V is now convinced that all the white commitments represent a whitepolyomino. Therefore, this method allows a prover P to make a solutionthat only P has in mind, guaranteed to satisfy the connectivity constraint.
2.5

Sum in Z [22]We give a brief overview of the protocol described in [22] for the additionofPnelements in Z/2Z with a result in Z. This allows to compute S =i=1 xi with S ∈ Z and xi ∈ Z/2Z for i ∈ {1, . . . , n}. The idea is tocompute the sum inductively; when starting by the two first elements x1
and x2 , they are transformed into x1 − r and x2 + r for uniformly randomr ∈ Z/2Z. Then x2 + r is revealed (no information about x2 leaks since r
is random), and the cards of x1 − r is shifted by x2 + r positions to encodevalue (x1 − r) + (x2 + r) = x1 + x2 . Note that this result is in Z/(p + 1)Z(or simply Z since the result is less than p) for elements x1 , x2 in Z/pZ.

3

ZKP Protocol for Nurimisaki

We present our ZKP protocol for Nurimisaki. Hereinafter, we consider an
instance of Nurimisaki as a rectangular grid of size p × q.
3.1

Setup phase

The verifier V and the prover P place black commitments on all the cellof the p × q grid and place red commitments (“dummy” commitments)
around the grid so that we have (p + 1)(q + 1) commitments.
93.2

Connectivity phase

P and V apply the protocol given in Section 2.4: a white-polyomino isformed according to P ’s solution. Now, V reveals all the commitments
corresponding to Misaki to check that they are indeed white. After thisphase, V is convinced that white commitments are connected (rule 5).
3.3

Verification Phase

The verifier V is now checking that the other rules are satisfied.
No 2 × 2 square (rule 4). We use an adapted verification phase of the
one in [17] for checking that 2 × 2 square are not composed of only white(black) commitments. Note that for an initial grid p × q, there are (p −1)(q − 1) possible squares of size 2 × 2. Thus P and V consider each of
those squares (in any order) and apply the following:
1. P chooses a white commitment and a black one among the four commitments via the chosen-pile protocol (Section 2.4).
2. V reveals both commitments marked by P in the previous step. If
there are exactly a white commitment and a black one, V continues;
otherwise, abort.
Misaki (rule 1 and 2). V wants to check that each Misaki cell (cell witha circle) has only one of its neighbours white and others black. Moreover,when a Misaki has a number in it, V wants to check that the straight line
formed by white cells starting from the Misaki cell has the corresponding
number of white cells.
P and V first consider Misaki cells with a number. For each Misaki
cell (not at a border) with a number i in it, apply the following:
1. P and V add black commitments (i.e., “dummy” commitments) at theborder of the grid. This ensures that we delimit correctly the numberof white commitments in a straight line.
2. For each of the four neighbours, P and V form a pile composed ofi + 1 commitments for each direction (top, bottom, left, right).
3
2
1

p2
1 2 3

2
3 2 1

1
2
3

10

p1 2 p3
p4

3. P and V puts numbered cards under each pile as follows:

p1 p2 p3 p4

1 2 3 4 .
4. P and V shuffle the piles and reveal the first commitment of eachpile. If there is exactly one commitment corresponding to white thenV continues. Otherwise, V aborts.
5. V reveals the next i commitments of the pile with the first whitecommitment. If there are only white commitments for the first i −1 commitments and a black commitment for the last one, then V
continues; otherwise, aborts.
After this step, V is convinced that Misaki cells with a number are
well-formed. In the case where there is no number, the first step consistsof forming a pile with only one commitment. Hence, V is convinced that
Misaki cells without a number satisfy only rule 1 but not rule 2 since any
number of white cells could form the straight line.1
No circle, no Misaki (rule 3). V needs to check that white cells without
a circle are not Misaki, meaning that any white cell of the grid has atleast two of its neighbours white. This rule is somewhat challenging toverify without leaking information on the solution because the number
and location of white cells are part of the solution (and must not be
publicly revealed).
If the targeted cell is black then there is nothing to verify since any
configurations could occur. Yet, if the targeted cell is white then there
are at least (but it could be more) two neighbours that are white. The
idea is to set the value of targeted cell being 5 if it is white and 0 if it isblack. Then we add the neighbours to it (white is 0, and black is 1). If
the cell is black then the sum is always less than or equal to 4 (which ispermitted by the rules to have all black). But if the cell is white then thepermitted value for the sum is less than or equal to 7 (a Misaki is equal
to 8) for a targeted cell that is not at a border.
For a given cell, called targeted cell ct , we look at its neighbors (up to4). The idea of verifying that a white cell is not a Misaki is to first sum
the four neighbors (where a white cell is equal to 0 and a black cell is 1).
Then by choosing another encoding, the targeted cell can be equal to 5
for white and 0 for black. Finally, adding the sum of the neighbors with ct
1

Note that we described the protocol for Misaki cell not at the border of the grid. If
a Misaki cell is at a border (but not a corner) then the 4-neighbours becomes the
3-neighbours and the protocol is the same (there will be only three piles instead offour). For Misaki cells at a corner, P and V consider the 2-neighbours (thus only
two piles).

11

gives at most 4 for black ct (which is permitted by the rules) and at most
7 for white ct in a valid configuration and 8 or 9 for invalid configuration.
1. Copy all the commitments using the copy protocol (Section 2.3). The
number of copies for a p × q grid is 2(2pq − p − q);
2. Sum the four neighbours by considering that a white commitment
is equal to 0 and a black commitment is equal to 1. The result isgiven in the ♡-scheme (i.e., there are four ♣ s and one ♡ at position
corresponding to the result of the sum).
3. For the targeted cell, add 3 ♡ s in the middle of the commitment as:
white: ♡ ♣ → ♡ ♡ ♡ ♡ ♣ = 5,
black: ♣ ♡ → ♣ ♡ ♡ ♡ ♡ = 0.
White is now 5 and black is 0 in the ♣-scheme.
4. Sum the result of the two previous steps (the sum of the four neighbours and the inner cell). The result is encoded in the ♡-scheme.
5. Reveal the last and penultimate cards. If a ♡ appears then abort;otherwise, continue.

4

Security Proofs

Our protocol needs to verify three security properties given as theorems.
Theorem 1 (Completeness). If P knows the solution of a Nurimisaki
grid, then P can convince V .
Proof. First, notice that P convinces V in the sense that the protocol
does not abort which mean that all the rules are satisfied. The protocol
can be split in two: (1) the connectivity and (2) the verification phases.
(1) Since P knows the solution, the white cells are connected andhence can always choose a black commitment at step 2 to swap it towhite. Notice that there exists a proof for the connectivity in [17].
(2) The verification of 2 × 2 square will not abort since if P has thesolution then for any given 2 × 2 square there always exist a white commitment and a black commitment. For the Misaki rules, each Misaki cellhas three of its neighbors black and one white; thus, the first commitment of piles p1 , p2 , p3 , p4 will reveal exactly three black and one whitecommitments. Then, when looking at pile pi of the first commitment corresponding to white, the number of white commitments corresponds tothe number in the inner cell. Thus the protocol will continue. Finally, thenon-Misaki rule is verified. Since P has the solution, any white cell (with12no circle in it) has at least two white neighbors. Thus if the inner cell iswhite then the sum will start to 5 and the maximal value is 7 because asolution has at least two whites so at most two black commitments (ofvalue 1 in this step). So the protocol will continue and hence V will be
convinced that P has the solution.
⊔⊓
Theorem 2 (Soundness). If P does not provide a solution of the p × q
Nurimisaki grid, P is not able to convince V .
Proof. Suppose that P does not know the solution, hence at least one of
the rules is not verified. If the white cells are not connected then P cannot
choose a black commitment at step 2 hence V will detect it. Notice that
there is also the proof of this phase in [17].
If P does not have the solution, then one of the verification phasewill fail. We apply a case distinction for those verifications. Assume firstthat there is a block of 2 × 2 square composed of only white (black)
commitments, then P cannot choose, during the chosen-pile protocol,
two distinct commitments (i.e., a black and a white) thus the revealedcommitments will attest to V that P does not have the solution. Second,
assume that a Misaki cell is not well-formed in the sense that either (1)the number of white neighbour is not equal to 1 or that (2) the numberof white cells in straight line does not correspond to the number of the
Misaki cell. For (1) the neighbours are revealed (after a shuffle) so V will
notice the number of white commitments; for (2) all the commitments
next to the white neighbour are revealed thus V will also notice if there
is a flaw. The last verification is for white cells which are not Misaki. It isequivalent of saying that any white cell (without a circle in it) has at least
two white neighbours. If a white cell has only one white neighbour thenduring the sum process, then ct = 5 (because the central cell is white) andthe total for its neighbours is 3 (because there are 3 black commitments
and 1 white). The final sum is then equal to 8, since V will look at thelast and penultimate card of the sum (corresponding to a sum equal to
9 and 8) then V will detect that a white card is a Misaki. Notice that a
sum equals to 9 means the white cell is surrounded by 4 black cells. It is
not possible since white cells are connected.
⊔⊓
Theorem 3 (Zero-knowledge). V learns nothing about P ’s solutionof the given grid G.
Proof. We use the same proof technique as in [7], namely the descriptionof an efficient simulator which simulates the interaction between an hon13

est prover and a cheating verifier. The goal is to produce an indistinguishable interaction from the verifier’s view (with the prover). Notice that thesimulator does not have the solution but it can swap cards during shuffles.
Informally, the verifier cannot distinguish between two protocols, one thatis run with the actual solution and one with random commitments. The
simulator acts as follows: The simulator constructs a random connected
white polyomino. During the 2 × 2 square verification, the simulator willswap cards to choose white and black commitments. For the Misaki verification, the simulator swaps three commitments to black for three piles
and one to white for the last pile. The latter will also be modified by thesimulator to contain the correct numbers of white commitments (and thelast commitment to black). During the non-Misaki verification, when thesum is computed, the simulator swaps the cards to always put ♣ cards
in position 8 and 9 (for the cell not at the edge, but the latter is done thesame way).
The simulated and real proofs are indistinguishable hence V learns
nothing from the connectivity and verification phases. Finally, we conclude that the protocol is zero-knowledge.
⊔⊓

5Conclusion

We proposed a physical ZKP protocol for Nurimisaki that uses only cards
and envelopes. The most difficult part was to prove that cells are not
Misaki without leaking their color. Of course, we combined this part withthe rest of the verifications that are stated by other rules. This new approach clearly demonstrates that showing that some cells do not havesome properties is often more difficult than proving an explicit property
without leaking any information.

Acknowledgements
We thank the anonymous referees, whose comments have helped us to
improve the presentation of the paper. This work was supported in partby JSPS KAKENHI Grant Numbers JP19J21153 and JP21K11881. This
study was partially supported by the French ANR project ANR-18-CE390019 (MobiS5).

References
1. X. Bultel, J. Dreier, J. Dumas, and P. Lafourcade. Physical zero-knowledge proofs
for Akari, Takuzu, Kakuro and KenKen. In E. D. Demaine and F. Grandoni,
editors, Fun with Algorithms, volume 49 of LIPIcs, pages 8:1–8:20, 2016.

14

2. X. Bultel, J. Dreier, J. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, A. Nagao,
T. Sasaki, K. Shinagawa, and H. Sone. Physical zero-knowledge proof for Makaro.
In T. Izumi and P. Kuznetsov, editors, SSS 2018, volume 11201 of LNCS, pages
111–125, Cham, 2018. Springer.
3. Y.-F. Chien and W.-K. Hon. Cryptographic and physical zero-knowledge proof:
From Sudoku to Nonogram. In P. Boldi and L. Gargano, editors, Fun with Algorithms, volume 6099 of LNCS, pages 102–112, Berlin, Heidelberg, 2010. Springer.
4. B. den Boer. More efficient match-making and satisfiability: The five card trick.
In J. Quisquater and J. Vandewalle, editors, EUROCRYPT 1989, volume 434 of
LNCS, pages 208–217, Berlin, Heidelberg, 1989. Springer.
5. J.-G. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, T. Sasaki, and H. Sone.
Interactive physical zero-knowledge proof for Norinori. In D.-Z. Du, Z. Duan, andC. Tian, editors, Computing and Combinatorics, volume 11653 of LNCS, pages
166–177, Cham, 2019. Springer.
6. S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive
proof-systems. In STOC 1985, pages 291–304, New York, 1985. ACM.
7. R. Gradwohl, M. Naor, B. Pinkas, and G. N. Rothblum. Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles. Theory Comput.
Syst., 44(2):245–268, 2009.
8. R. Isuzugawa, D. Miyahara, and T. Mizuki. Zero-knowledge proof protocol for
Cryptarithmetic using dihedral cards. In I. Kostitsyna and P. Orponen, editors,
UCNC 2021, volume 12984 of LNCS, pages 51–67, Cham, 2021. Springer.
9. C. Iwamoto and T. Ide. Computational complexity of Nurimisaki and Sashigane.
IEICE Trans. Fundamentals, 103(10):1183–1192, 2020.
10. A. Koch and S. Walzer. Foundations for actively secure card-based cryptography.
In M. Farach-Colton, G. Prencipe, and R. Uehara, editors, Fun with Algorithms,
volume 157 of LIPIcs, pages 17:1–17:23, Dagstuhl, 2021. Schloss Dagstuhl.
11. P. Lafourcade, D. Miyahara, T. Mizuki, L. Robert, T. Sasaki, and H. Sone. How toconstruct physical zero-knowledge proofs for puzzles with a “single loop” condition.
Theor. Comput. Sci., 888:41–55, 2021.
12. D. Miyahara, L. Robert, P. Lafourcade, S. Takeshige, T. Mizuki, K. Shinagawa,A. Nagao, and H. Sone. Card-based ZKP protocols for Takuzu and Juosan. In
M. Farach-Colton, G. Prencipe, and R. Uehara, editors, Fun with Algorithms, volume 157 of LIPIcs, pages 20:1–20:21, Dagstuhl, 2021. Schloss Dagstuhl.
13. D. Miyahara, T. Sasaki, T. Mizuki, and H. Sone. Card-based physical zeroknowledge proof for Kakuro. IEICE Trans. Fundamentals, 102-A(9):1072–1078,
2019.
14. T. Mizuki and H. Sone. Six-card secure AND and four-card secure XOR. In
X. Deng, J. E. Hopcroft, and J. Xue, editors, FAW 2009, volume 5598 of LNCS,
pages 358–369, Berlin, Heidelberg, 2009. Springer.
15. A. Nishimura, Y. Hayashi, T. Mizuki, and H. Sone. Pile-shifting scramble forcard-based protocols. IEICE Trans. Fundamentals, 101-A(9):1494–1502, 2018.
16. L. Robert, D. Miyahara, P. Lafourcade, L. Libralesso, and T. Mizuki. Physicalzero-knowledge proof and NP-completeness proof of Suguru puzzle. Inf. Comput.,
285(B):104858, 2022.
17. L. Robert, D. Miyahara, P. Lafourcade, and T. Mizuki. Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake. New Gener. Comput.,
40:149–171, 2022.
18. S. Ruangwises. An improved physical ZKP for Nonogram. In COCOA, volume13135 of LNCS, pages 262–272, Cham, 2021. Springer.

1519. S. Ruangwises. Two standard decks of playing cards are sufficient for a ZKP for
Sudoku. New Gener. Comput., 40:49–65, 2022.
20. S. Ruangwises and T. Itoh. Physical zero-knowledge proof for Numberlink puzzle
and k vertex-disjoint paths problem. New Gener. Comput., 39(1):3–17, 2021.
21. S. Ruangwises and T. Itoh. Physical ZKP for connected spanning subgraph: Applications to Bridges puzzle and other problems. In I. Kostitsyna and P. Orponen,
editors, UCNC 2021, volume 12984 of LNCS, pages 149–163, Cham, 2021. Springer.
22. S. Ruangwises and T. Itoh. Securely computing the n-variable equality function
with 2n cards. Theor. Comput. Sci., 887:99–110, 2021.
23. S. Ruangwises and T. Itoh. How to physically verify a rectangle in a grid: A physical
ZKP for Shikaku. In P. Fraigniaud and Y. Uno, editors, Fun with Algorithms,
volume 226 of LIPIcs, pages 24:1–24:12. Schloss Dagstuhl, 2022.
24. T. Sasaki, D. Miyahara, T. Mizuki, and H. Sone. Efficient card-based zeroknowledge proof for Sudoku. Theor. Comput. Sci., 839:135–142, 2020.
25. K. Shinagawa, T. Mizuki, J. C. N. Schuldt, K. Nuida, N. Kanayama, T. Nishide,
G. Hanaoka, and E. Okamoto. Card-based protocols using regular polygon cards.
IEICE Trans. Fundamentals, 100-A(9):1900–1909, 2017.

16