Interactive Physical Zero-Knowledge Proof for
Norinori?
Jean-Guillaume Dumas1 , Pascal Lafourcade2 , Daiki Miyahara3,5 ,Takaaki Mizuki4 , Tatsuya Sasaki3 , and Hideaki Sone4
1

Univ. Grenoble Alpes, CNRS, Grenoble INP? ? ? , LJK, 38000 Grenoble, France
2
LIMOS, University Clermont Auvergne, CNRS UMR 6158, France
3
Graduate School of Information Sciences, Tohoku University, Japan
4
Cyberscience Center, Tohoku University, Japan
5
National Institute of Advanced Industrial Science and Technology, Japan

Abstract. Norinori is a logic game similar to Sudoku. In Norinori, agrid of cells has to be filled with either black or white cells so that thegiven areas contain exactly two black cells, and every black cell shares anedge with exactly one other black cell. We propose a secure interactive
physical algorithm, relying only on cards, to realize a zero-knowledge
proof of knowledge for Norinori. It allows a player to show that he or sheknows a solution without revealing it. For this, we show in particular that
it is possible to physically prove that a particular element is present in alist, without revealing any other value in the list, and without revealing
the actual position of that element in the list.
Keywords: Zero-knowledge proofs · Card-based secure two-party protocols · Puzzle · Norinori

1

Introduction

Sudoku, introduced under this name in 1986 by the Japanese puzzle company
Nikoli, and similar games such as Akari, Takuzu, Makaro, and Norinori havegained immense popularity in recent years. Many of them have been proved to
be NP-complete [1, 5, 9, 10]. In 2007, Gradwohl, Naor, Pinkas, and Rothblum
proposed the first physical zero-knowledge proof protocols for Sudoku [7]. Their
protocol only use several cards and allow a prover to prove to a verifier that heknows a solutions of a Sudoku grid. More precisely, a zero-knowledge proof ofknowledge is a protocol that allows a prover P to convince a verifier V that she
knows the solution w of an instance of a computational problem. Such a protocol
has the following properties:
Correctness. If P knows w, then P can convince V .
???
?

Institute of Engineering Univ. Grenoble Alpes
This paper appears in Proceedings of COCOON 2019. The final authenticated version is available online at https://doi.org/10.1007/978-3-030-26176-4_14.

2

J. Dumas et al.

Extractability. If P does not know w, then P cannot convince V , except withsome small probability (here will have perfect Extractability, that is theprobability that V does not detect a wrong grid is zero). This implies thestandard soundness property, which ensures that if there exists no solutionof the puzzle, then the prover is not able to convince the verifier regardlessof the prover’s behavior.
Zero-Knowledge. V cannot obtain any information about w. To prove thata protocol satisfies the zero-knowledge property, it is sufficient to exhibit aprobabilistic polynomial time algorithm M (I), not knowing w, such that theoutputs of the protocol and the outputs of M (I) follow the same probability
distribution.
Recently, a novel protocol for Sudoku using fewer cards and with no soundness error was then proposed [14]. Physical protocols for other games, such as
Hanjie, Akari, Kakuro, KenKen, Takuzu, and Makaro, have been designed [2–4].
In this article, we propose the first interactive physical zero-knowledge proof
protocol for Norinori.
Norinori: It is a pencil puzzle published in the famous puzzle magazine Nikoli.
The puzzle instance is a rectangular grid of cells. The grid is partitioned into
rooms, that is, areas surrounded by bold lines. The goal of the puzzle is to shadecertain cells so that they become black, according to the following rules [12]:1. Room condition: Each room must contain exactly two black cells.
2. Pair condition: The black cells come in pairs: each black cell must be adjacent
to exactly one, and only one, other black cell.
In Figure 1, we give a simple example of a Norinori game. It is easy to verify
that both constraints are satisfied in the solution on the right part of the figure.
We note that in a solution the number of black cells is exactly twice the numberof rooms.

Fig. 1. Example of a Norinori grid and its solution.

Solving Norinori was shown to be NP-complete via a reduction from PLANAR 1-IN-3-SAT in [1]. Hence, it is possible to construct a cryptographic zeroknowledge proof of this game by using the generic cryptographic zero-knowledge

Interactive Physical Zero-Knowledge Proof for Norinori

3

proofs for all problems in NP given in [6]. However, this construction requires
cryptographic primitives and is not very efficient.
Contributions: Our aim in this paper is to design an interactive physical protocolthat uses only cards and envelopes for Nornori. This paper is not just anotherpaper that proposed a physical zero-knowledge protocol for a Nikoli’s game but
we want to extend the physically verifiable set of functions that we are able
to solve using only physical material. For instance, we know how to guarantee
the presence of all numbers in some set without revealing their order [7], how
to guarantee that two numbers are distinct without revealing their respective
values [2], or how to prove that a number is the largest in a list, without revealing
any value in the list [3]. In this paper, by providing a physical zero-knowledge
proof for the Nikoli puzzle Norinori, we show in particular that it is possible tophysically prove that a particular element is present in a list, without revealing
any other value in the list, and without revealing the actual position of thatelement in the list.
Outline: In the next section, we introduce some notations and explain simple
physical subprotocols that we use in our protocol for Norinori. In Section 3,
we construct our zero-knowledge protocol for Norinori, before giving a security
analysis in Section 4 and concluding in Section 5.

2

Preliminaries

In this section, we present some notations and introduce shuffling operations anda subprotocol that will be used later.
2.1

Physical Objects

The physical cards used in this paper are given in Table 1. We assume thatthe back sides of all cards are identical6 , and the face sides of all the cards ofeach type (such as , ♣ , X , S , 1 , . . .) are also identical. We use the notation(c1 , c2 , . . . , ck ) to represent a sequence of k face-down cards ? ? . . . ? . We
also consider a pile of cards ? consisting of ` face-down cards and express it
as a vector p. Moreover, a sequence of k piles ( ? , ? , . . . , ? ) is expressed
as a k-tuple of vectors (p1 , p2 , . . . , pk ).
2.2

Pile-Scramble Shuffle

Pile-Scramble Shuffle [8] is a shuffle operation for piles: for a sequence of kpiles (p1 , p2 , . . . , pk ), applying a Pile-Scramble Shuffle results in (pπ−1 (1) , pπ−1 (2), . . . , pπ−1 (k) ), where π ∈ Sk is a uniformly distributed random permutation,and Sk is the symmetric group of degree k. A Pile-Scramble Shuffle can be
implemented by physical cases, for instance by using a big box where we place
all the cases that contain the pile of cards and we blindly shuffle them.
6

It means that the cards face down are indistinguishable from each other.

4

J. Dumas et al.
Table 1. Names of cards.

Face side

2.3

Back side

Name?

White card♣?

Black card

X?

Maker card

S?

Starting card

1 2 3 4?

Number card

Pile-Shifting Shuffle

Pile-Shifting Shuffle (which is also called Pile-Shifting Scramble) [13] cyclically
shuffles piles of cards. That is, given a sequence of k piles, each of which consistsof the same number of face-down cards, denoted by (p1 , p2 , . . . , pk ), applying
a Pile-Shifting Shuffle results in (pr+1 , pr+2 , . . . , pr+k ), where r is uniformly randomly generated from Z/kZ and is unknown to everyone. To implement a PileShifting Scramble, we use physical cases that can store a pile of cards, such asboxes or envelopes. One possible implementation is to place the different pile ofcards in cases that are linked together in a circle in order to form a cycle. Thenwe just have to physically shuffle the cases, for instance by turning the circle.

2.4

Card Choosing Protocol

In this subsection, we describe the Card Choosing Protocol, which is immediately
obtained by borrowing the idea behind the Chosen Cut [11]. This protocol is used
as a subprotocol in our construction in Section 3.
Given a sequence of k face-down cards (c1 , c2 , . . . , ck ), the Card Choosing
Protocol enables the prover P to choose a designated card secretly. More precisely, for some i such that 1 ≤ i ≤ k, P can choose the i-th card without
revealing any information about i to the verifier V . The protocol proceeds asfollows:
1. P holds k − 1 white cards and one black card. Then, P puts them with theirfaces down below the cards (c1 , c2 , . . . , ck ), such that only the i-th card is
the black card:? ? ... ? ? ? ... ?
c1 c2

ci−1 ci ci+1

ck

? ? ... ? ? ? ... ?
♣Interactive Physical Zero-Knowledge Proof for Norinori

5

2. Regarding cards in the same column as a pile, apply a Pile-Shifting Shuffle
to the sequence of piles (which is denoted by h · | . . . |· i):*+? ? ... ?
?
?
?
cr+1 cr+2
cr+k
c1
c2 . . . ck
→
,
?
?
?
? ? ... ?
where r ∈ Z/kZ is a uniformly distributed random value.
3. Reveal all the cards in the second row. Then, one black card appears, andthe card above the revealed black card is the i-th card:? ? ... ? ? ? ... ?
ci

...

♣

...

Thus, P can show the designated card to V .
Because all the opened cards are shuffled in Step 2, V does not learn any information about the index i of the chosen card and is sure that only one card was
designated.

3

Zero-Knowledge Proof for Norinori

We are now ready to describe our construction of a zero-knowledge proof for
Norinori. For a puzzle instance of board size m × n including exactly t rooms,
assume that the prover P knows the solution. Our protocol consists of threephases, namely:
1. Setup phase,
2. Pair Verification phase,
3. Room Verification phase.
It is important to perform the phases in this order. The Room Verification
phase has to be the last one and the Setup phase the first phase.
Setup phase: This phase has two steps:
1. P puts one face-down card on each cell according to the solution. That is, ablack card is placed on every cell where a black square exists in the solution,
and white cards are placed on all the other cells. For example, for the puzzle
instance in Fig. 1, the cards are placed as follows:? ? ? ? ?
♣

♣

♣

♣

? ? ? ? ?
♣? ? ? ? ?
♣♣♣? ? ? ? ?
♣♣? ? ? ? ?
♣♣

6

J. Dumas et al.

These cards are P ’s input, and we assume that P knows his or her input.
This implies that if the cards conform to the solution, P knows the solution.
Note that 2 × t black cards and m × n − (2 × t) white cards on a board ofdimension m × n including exactly t rooms.
2. Next, remembering that m is the number of rows and n is the number ofcolumns, V takes 2 × m + 2 × n + 3 white cards and one starting card. Then,
V puts these cards around the m × n “matrix” above to expand it to an(m + 1) × (n + 1) “matrix” as follows, where the starting card is placed at
the top-left corner:
S? ? ? ? ?
? ? ? ? ?
(1)
? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
Pick each row from top to bottom to make a sequence of cards:
m × n + 2 × m + 2 × n + 3 cardsz}|{? ? ? ? ? ? ? ... ? ?
SNotation: For any black card (whose location is known only to P ) in the matrix,
we define its four adjacent cards called north, east, west, and south cards:
?
north

?

?

?

west

♣

east

?
south

Pair Verification Phase: The verifier V verifies that P ’s input satisfies the
Pair condition. If P has placed the cards correctly, every black card will haveexactly one black card among its adjacent cards. The verification of the Paircondition is to guarantee this, and it proceeds as follows:
1. P selects a black card mentally from the card sequence, and performs theCard Choosing Protocol to choose that card:? ... ? ? ? ... ?
...

♣

...

Then, V opens the card chosen by P to make sure that the chosen card isblack:↓? ... ? ♣ ? ... ?
...

♣

...

Interactive Physical Zero-Knowledge Proof for Norinori

7

After confirming that the card is black, V replaces it by a marker card:↓? ... ? X ? ... ?
...

...

♣

This operation prevents P from choosing the same black card again at later
verifications.
2. V picks the four adjacent cards of the chosen black card. Because the sequence of cards was shifted cyclically, V can find such four cards, namely,
the north, east, west, and south cards, by counting the distances7 :
?

?

?

?

west north east south

3. V puts number cards
turns them over:
?
1

1
?
2

2

3

?

?

3

4

in this order below these cards, and

4

→

?

?

?

?

?

?

?

?

4. P regards cards in the same column as a pile and applies a Pile-Scramble
Shuffle to the sequence of piles:*+? ? ? ?
?
?
?
...
→
? ? ? ?
?
?
?
5. V reveals the top row and checks that there is exactly one black or one
marker card:♣Xor? ? ? ?
? ? ? ?
After checking it, the cards in the top row are turned over.
6. P applies a Pile-Scramble Shuffle to the piles again, and reveals the bottomrow:*+? ? ? ?
? ? ? ?
?
?
?
...
→
→
2 3 4 1
? ? ? ?
?
?
?
Because the number cards indicate the original order, V can place each top
card back in the original position in the card sequence:? ? ...

?
north... ? X ? ...
west

east

?

... ?

south

Turn over the face-up marker card. Note that P knows the locations of theother black cards and the starting card.
7

For example, if the size of the puzzle board is 3 × 4, the north card is the fifth card
away from the chosen card to the left, and the south card is the sixth card awayfrom it to the right.

8

J. Dumas et al.

P and V repeat Steps 1 to 6 above 2 × t − 1 times more; recall that 2 × t is thenumber of black cards8 . Furthermore, as a targeted black card is replaced by amarker card, V is convinced that 2t black cards are verified.
Next, P and V place the card sequence back on the puzzle board, as follows:
1. P chooses the starting card in the card sequence by performing a Card
Choosing Protocol:
↓
.
.
.
?
? S ? ... ?
...

?

...

2. Shift the cards so that the starting card is leftmost:
S ? ? ? ? ? ? ... ?
From the Card Choosing Protocols, the order of the cards is the same as
the order of the card sequence generated in the Setup phase (although 2t
black cards have been replaced by marker cards), and hence P and V canreconstruct the puzzle-board placement (1) by reversing the operations of
the Setup phase.
Room Verification Phase: In this phase, V verifies the Room condition. To
this end, the following is performed for each of the t rooms:
1. V picks all the cards from the room. Note that, regardless of the size of thetargeted room, exactly two of the cards should be marker cards.
2. P shuffles the cards and reveals them.
3. V checks that exactly two marker cards appear.
If all phases have been passed, then the verifier accepts the proof by outputting 1.
Performance Analysis Let us mention the performance of our protocol in termsof the numbers of shuffles and cards. The total number of shuffles is 7 × t + 1(where t is the number of rooms), and the total number of required cards is
2 × m × n + 4 × m + 4 × n + 2 × t + 12, whose distribution is shown in Table 2(where we have an m × n board).

4

Security Analysis

We can easily see that our protocol satisfies the three properties of a zeroknowledge proof, as follows:
8

One might think that t times would suffice if any black card found in Step 5 was
replaced by a marker card; however, this is not the case because we need to checkthat such a found black card also has exactly one black card among its adjacentcards.

Interactive Physical Zero-Knowledge Proof for Norinori

9

Table 2. Numbers of cards required to execute our protocol.

Type of card
White card (# of cards)

2×m×n+4×m+4×n−2×t+6

Black card ( ♣ )2×t+1Marker card ( X )2×tStarting card ( S )1

Number card ( 1 2 3 4 )4Correctness: If the prover P places the cards according to the solution in
the Setup phase, P ’s input passes all verifications. Therefore, P who knows thesolution, can always convince the verifier V .
Extractability: If P ’s input is invalid, V can detect it in the Verification phases.
Therefore, if P does not know the solution, P cannot convince V .
Zero-knowledgeness: Since all the cards have been shuffled before they are
opened, V learns nothing about the solution.
More precisely, we prove the following lemmas.
Lemma 1 (Correctness). If the prover P has a solution for the Norinori puzzle, then P can always convince the verifier V (i.e., V outputs 1).
Proof. We show that for a prover P with a solution, the verifier V never outputs
0. We look at the three phases:
Setup: In this phase the verifier just needs to check that the cards given by
P correspond to size of the board. After that, V needs to place some extra
cards and place all the cards in order to form a sequence. If P does not givethe right number of cards, it is clear that he does not know the solution since
he does not even know the puzzle itself.
Pair Verification: In this phase the goal of the verifier is to be convinced thatall black cells come in pairs. If P knows a solution then he can place correctly
the black cells. Hence the verifier never founds more than one marked or blackcard when he is opening the four adjacent cards of a black card. The only
remaining uncertainty is whether P used exactly 2t black cards or more.
Room Verification: In this last phase, the verifier discovers exactly two blackcards by room only if the prover knows a solution. As there are t rooms, thisalso proves that there were exactly 2t black cards to begin with.
Lemma 2 (Perfect Extractability). If the prover does not know a solution
for the Norinori puzzle, then the verifier V always rejects (i.e., V outputs 0)
regardless of the prover P ’s behavior.

10

J. Dumas et al.

Proof. It is important to notice that the order of our 3 phases is crucial andthe fact that we can use the same cards for all the steps to ensure that we haveno soundness error. In our proof, we consider two cases: the Pair condition isviolated or the Room condition is violated.
Pair Condition: If the solution given by P does not satisfy the Pair condition,
it means that some black cards do not come in pairs: some black cell areadjacent to more than one black card, or some black cells are isolated. We
have three possible cases (modulo rotations and symmetries) that can occur:
1. There are 3 aligned black cards as follows: ♣ ♣ ♣♣2. There are 3 black cards that form an “L” as follows:♣ ♣3. A single black card is surrounded by white cards.
In the first two cases, when V opens the four adjacent cards of a blackcard, he detects that there is strictly more than one extra black card in
the neighborhood. This shows that the prover does not have a solution thatsatisfies the Pair condition. Similarly, in case of an isolated black card, theneighborhood will show only white cards. Overall, the verifier is convinced
after this phase if and only if all black cards come in pairs.
Room Condition: If the solution given by P does not satisfy the Room condition, it means that a room contains one or no black card, or that a room
contains three or more black cards. Both situation are detected by the verifierthat opens all the cards in all the rooms.
Lemma 3 (Zero-knowledge). During an execution of our protocol, the verifier V learns nothing about P ’s Norinori solution.
Proof. In order to prove this, we have to describe an efficient simulator thatsimulates any interaction between a cheating verifier and a real prover. The
simulator does not have a correct solution, but it does have an advantage overthe prover: when shuffling decks, it is allowed to swap the packets for different
ones. We thus show how to construct a simulator for each challenge.
Setup: V learns only the size of the board when he receives P ’s inputs, which
is a known data already publicly avaible in the puzzle grid.
Pair Condition: In this phase the verifier does not learn any information except the number of black cards, which is 2×t. This is not a secret information
since it is a known data already publicly available in the puzzle grid. It is sufficient to show that all distributions of opening values are simulated without
knowing the prover’s solution.
Now, from [8,11,13], respectively, we know that the subprotocols Pile-Scramble
Shuffle, Pile-Shifting Shuffle and Card Choosing Protocol are zero-knowledge.
Note also, that during this verification phase, there is no need for the simulator to respect the Room condition. Thus a possible simulator is as follows:
the simulator places at least one black card randomly on the grid. Then,for each pair verification, the simulator designates a black card and, at theInteractive Physical Zero-Knowledge Proof for Norinori

11

Pile-Scramble step, P replaces the four adjacent cards by a single black andthree white cards, e.g., as follows:
♣
1

2

3

4

For the first step, the Card Choosing Protocol ensures that V does not learn
anything: indeed it reveals that there is at least one black card on the board,but nothing about its position. Hence this subprotocol does not leak any
information and is indistinguishable from the simulator.
For Step 4, the fact that P uses the Pile-Scramble Shuffle to the sequence ofpiles implies that their order is uniformly distributed and then can be simulated without knowing the solution. Therefore the position of the adjacent
black cell is not leaked either.
At Step 6, using the Pile-Scramble Shuffle, the simulator replaces the initialcards (not even switching the tested black card by a marked card, see in
the next phase). Note that the fact that we can replace the verified cards intheir initial position without leaking any information comes from the usageof Pile-Scramble Shuffle in Step 6 and the usage of Card Choosing Protocolin the next step. It allows us to use the same cards for the next verification9 .
Room Condition: This phase is similar to a room/row/column condition in
Sudoku [7, Protocol 3]: since P shuffles all the cards within a room before
revealing them, this is indistinguishable from a simulation putting randomly
two marked cards among white ones. Thus V only learns that there were
exactly two black cards in each rooms.

5

Conclusion

In this paper, we have designed an interactive zero-knowledge proof protocol forthe famous puzzle, Norinori. Our protocol is quite simple and easy to implementby humans. By solving this Nikoli’s puzzle, we also demonstrate that it is possible
to physically prove that a particular element is present in a list, without revealing
any other value in the list, and without relvealing the actual position of thatelement in the list. This functionality could be used to construct zero-knowledge
proof protocols for other puzzles.
An interesting open problem is to design a more efficient protocol in termsof the numbers of cards and shuffles.
Acknowledgement
We thank the anonymous referees, whose comments have helped us to improve
the presentation of the paper. This work was supported by JSPS KAKENHI
Grant Number JP17K00001 and partly by the OpenDreamKit Horizon 2020 European Research Infrastructures project (#676541) and the Cyber@Alps French
National Research Agency program (ANR-15-IDEX-02).
9

This trick is inspired from [14] and allows us to also have no soundness error.

12

J. Dumas et al.

References
1. Biro, M., Schmidt, C.: Computational complexity and bounds for Norinori and
LITS. In: EuroCG 2017. pp. 29–32 (2017)
2. Bultel, X., Dreier, J., Dumas, J.G., Lafourcade, P.: Physical zero-knowledge proofs
for Akari, Takuzu, Kakuro and KenKen. In: Demaine, E.D., Grandoni, F. (eds.)
FUN 2016. LIPIcs, vol. 49, pp. 8:1–8:20 (2016)
3. Bultel, X., Dreier, J., Dumas, J., Lafourcade, P., Miyahara, D., Mizuki, T., Nagao,
A., Sasaki, T., Shinagawa, K., Sone, H.: Physical zero-knowledge proof for Makaro.
In: Izumi, T., Kuznetsov, P. (eds.) SSS 2018. LNCS, vol. 11201, pp. 111–125.
Springer (2018)
4. Chien, Y.F., Hon, W.K.: Cryptographic and physical zero-knowledge proof: From
Sudoku to Nonogram. In: Boldi, P., Gargano, L. (eds.) Fun with Algorithms 2010.
LNCS, vol. 6099, pp. 102–112. Springer (2010)
5. Demaine, E.D.: Playing games with algorithms: Algorithmic combinatorial gametheory. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136,
pp. 18–32. Springer (2001)
6. Goldreich, O., Micali, S., Wigderson, A.: How to prove all NP-Statements in zeroknowledge, and a methodology of cryptographic protocol design. In: Odlyzko, A.M.
(ed.) CRYPTO 1986. LNCS, vol. 263, pp. 171–185. Springer (1987)
7. Gradwohl, R., Naor, M., Pinkas, B., Rothblum, G.N.: Cryptographic and physicalzero-knowledge proof systems for solutions of Sudoku puzzles. In: Crescenzi, P.,
Prencipe, G., Pucci, G. (eds.) Fun with Algorithms 2007. LNCS, vol. 4475, pp.
166–182. Springer (2007)
8. Ishikawa, R., Chida, E., Mizuki, T.: Efficient card-based protocols for generating ahidden random permutation without fixed points. In: Calude, C.S., Dinneen, M.J.
(eds.) UCNC 2015. LNCS, vol. 9252, pp. 215–226. Springer (2015)
9. Iwamoto, C., Haruishi, M., Ibusuki, T.: Herugolf and Makaro are NP-complete.
In: Ito, H., Leonardi, S., Pagli, L., Prencipe, G. (eds.) Fun with Algorithms 2018.
LIPIcs, vol. 100, pp. 24:1–24:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)
10. Kendall, G., Parkes, A.J., Spoerer, K.: A survey of NP-complete puzzles. ICGA
Journal 31(1), 13–34 (2008)
11. Koch, A., Walzer, S.: Foundations for actively secure card-based cryptography.
IACR Cryptology ePrint Archive 2017, 423 (2017)
12. Nikoli: Norinori, http://www.nikoli.co.jp/en/puzzles/norinori.html
13. Nishimura, A., Hayashi, Y.i., Mizuki, T., Sone, H.: Pile-shifting scramble for cardbased protocols. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 101(9),1494–1502 (2018)14. Sasaki, T., Mizuki, T., Sone, H.: Card-based zero-knowledge proof for Sudoku.
In: Ito, H., Leonardi, S., Pagli, L., Prencipe, G. (eds.) Fun with Algorithms 2018.
LIPIcs, vol. 100, pp. 29:1–29:10. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)