Interactive Physical ZeroKnowledge Proof for Norinori
Jean-Guillaume Dumas1 Pascal Lafourcade2 〇Daiki Miyahara3,4
Takaaki Mizuki3 Tatsuya Sasaki3 Hideaki Sone3
1. Univ. Grenoble Alpes 2. Univ. Clermont Auvergne
3. Tohoku Univ. 4. National Institute of Advanced Industrial Science and Technology

COCOON2019

西安 CHINA

1

Outline

1. Background・Norinori

・Scenario

・Contribution

2. Idea

3. Our Construction
4. Conclusion2What is Norinori?
✓One of the most famous puzzles published by Nikori.

surrounded bybold lines
RoomAn example of a challenge of Norinori.
https://www.nikoli.co.jp/en/puzzles/norinori.html

3What is Norinori?
✓Goal: Make some of empty cells become blackso that:Rules.
Room condition. Each roommust contain exactly twoblack cells.
Pair condition. Each black
cell must be adjacent toexactly one other black cell.
An example of a challengeof Norinori.
https://www.nikoli.co.jp/en/puzzles/norinori.html

45

What is Norinori?
✓Goal: Make some of empty cells become blackso that:Rules.
Room condition. Each roommust contain exactly twoblack cells.

Pair condition. Each black
cell must be adjacent toexactly one other black cell.
A solution of the challenge.

✓Solving Norinori was shown to be NP-complete.[BS17][BS17] M. Biro and C. Schmidt, ``Computational complexity and bounds for Norinori andLITS,’’ EuroCG 2017.

What is Norinori?
✓We can easily confirm both rules are satisfied.

Room:exactly twoRules.

Room condition. Each roommust contain exactly twoblack cells.
Pair condition. Each blackcell must be adjacent toPair: exactly
exactly
one otherone
black cell.
A solution of the challenge.

6

Consider two players, 𝑃 and 𝑉.

7✓𝑃 has brought a challenge of Norinori to 𝑉.

Player 𝑃

Player 𝑉

Consider two players, 𝑃 and 𝑉.

8✓𝑃 has brought a challenge of Norinori to 𝑉.

Can you solve
this puzzle?

Player 𝑃

Player 𝑉

Consider two players, 𝑃 and 𝑉.

9✓But 𝑉 can’t solve this, so 𝑉 wonders if this puzzle
really has a solution.

This puzzle hasa solution?

Of course!

Player 𝑃

Player 𝑉

10Consider two players, 𝑃 and 𝑉.
✓Dilemma: 𝑃 wants to convince 𝑉 but does notwant to reveal the solution.

How can youprove it?

Hmm…

Player 𝑃

Player 𝑉

The scenario✓ Convince 𝑉 that theproblem has a solution
without revealing it.
Restrictions:✓ Use everyday objects.

Player 𝑃 ✓ Prove it manually.

Player 𝑉

Physical Zero-Knowledge Proof (ZKP)!

11

Contribution✓Design a physical ZKP protocol for Norinori using
cards and envelopes.

1 2 3 4
Back side

Face side

Envelopes

Player 𝑃

Player 𝑉

12

Outline

1. Background・Norinori・Scenario

・Contribution

2. Idea

3. Our Construction
4. Conclusion

13

A deck of cards used in our protocol

White cards

Black cards✔✔✔✔✔✔

1 2 3 4Marker cards

Number cards

14

Basic Idea
✓Setup: 𝑃 puts one face-down card on each cellaccording to the solution.
♣♣

♣♣♣♣

♣

♣

♣

Player 𝑃♣♣♣

15

Basic Idea
✓Then, the Room condition can be easily verified.

Player 𝑃16

Basic Idea
✓Then, the Room condition can be easily verified.

ShuffleExactly two; noinformation is leaked.

Reveal17

Basic Idea
✓Then, how we verify the Pair condition?

Player 𝑃

Pair: exactly one

18Basic Idea
✓Exactly one black cell exists among four
adjacent cells of each black one.

Exactly oneblack cell

19Basic Idea
✓Exactly one black cell exists among four
adjacent cells of each black one.

Exactly one
black card20

Outline

1. Background・Norinori・Scenario

・Contribution

2. Idea

3. Our Construction
4. Conclusion

21

Our construction
Setup

Pair
verification

Roomverification

Player 𝑃

Player 𝑉

22

Our construction
Setup

Pair
verificationRoomverification

Player 𝑃

Player 𝑉23

24

Setup
✓𝑃 puts one face-down card on each cell according
to the solution.
✓They put additional white cards for the Pairverification.

♣♣♣♣♣♣♣♣♣♣♣♣

Our construction
Setup

Pair
verification

Roomverification

Player 𝑃

Player 𝑉25

Pair verification
1. 𝑃 picksNote:
one blackcard theand existing
four adjacent cards
we useof it without revealing
their position.
[KW17]
to hidepositions.
Then, techniquethey replace the blackwiththea markercard.

(see our paper)✔

26[KW17] A. Koch and S. Walzer, ``Foundations for actively secure card-based cryptography,’’ IACR Cryptology ePrint Archive, 2017:423, 2017.

Pair verification✓Now, we have the four adjacent cards.
✓We can verify the Pair condition by just revealing
these four cards, but:

Just revealing
them leaksinformation.

These are necessary
for the next verifications.

27

Pair verification
2. 𝑉 puts number cards below the four adjacent cards,
which specify the original positions (and then turnthem over).

124

3

28

Pair verification
3. 𝑉 puts each two cards into an envelope, and thenshuffles them:29

Pair verification
4. 𝑉 reveals the four adjacent cards.

Then, exactly one black or marker should appear.

or ✔

30

Pair verification
5. 𝑉 turns them over, and then shuffles them asbefore.

31

Pair verification
6. 𝑉 reveals the four number cards.

𝑉 can place the four adjacent cards in the originalpositions.

432132

Pair verification

33✓By repeating the previous steps twice as the numberof rooms, 𝑉 is convinced of the Pair condition.

Our construction
Setup

Pair
verification

Roomverification

Player 𝑃

Player 𝑉

34

Room verification is easy

35

✓Shuffle the cards corresponding to each room andthen reveal them.

ShuffleRevealRoom verification is easy

36

✓By repeating the previous step, 𝑉 is convinced of theRoom condition.

Our construction
Setup

Pair
verification

Roomverification

Player 𝑃

Player 𝑉

37

Outline

1. Background・Norinori

・Scenario

・Contribution

2. Idea

3. Our Construction
4. Conclusion

38

Conclusion✓Designed a physical ZKP protocol for Norinori using
cards and envelopes.

Player 𝑃

Player 𝑉39