Physical Zero-Knowledge Proof
for Suguru Puzzle?
Léo Robert1 , Daiki Miyahara2,3 , Pascal Lafourcade1 , and Takaaki
Mizuki4
1

University Clermont Auvergne, LIMOS, CNRS UMR 6158, Aubière France
Graduate School of Information Sciences, Tohoku University, Sendai, Japan
3
National Institute of Advanced Industrial Science and Technology, Tokyo, Japan
4
Cyberscience Center, Tohoku University, Sendai, Japan
2

Abstract. Suguru is a paper and pencil puzzle invented by Naoki Inaba. The goal of the game is to fulfil a grid with numbers between 1
and 5 and to respect three simple constraints. In this paper we design aphysical Zero-Knowledge Proof (ZKP) protocol for Suguru. A ZKP protocol allows a prover (P ) to prove that he knows a solution of a Suguru
grid to a verifier (V ) without leaking any information on the solution.
For constructing such a physical ZKP protocol, we only rely on a small
number of physical cards and an adapted encoding. For a grid of Suguru
with n cells, we only use 5n + 5 cards. Moreover, we prove the threeclassical security properties of a ZKP: completeness, extractability, andzero-knowledge.

Keywords: Physical zero-knowledge proof, Suguru, Security, Completeness, Extractability, and Zero-knowledge.

1

Introduction

Zero-Knowledge Proofs (ZKP) were introduced in 1985 by Goldwasser et
al. [8]. Two parties are involved in such a ZKP protocol: a prover P anda verifier V . At the end of the protocol, the verifier V is convinced that P
knows the solution s to the instance I of a problem P, without revealing
any information about s. A zero-knowledge proof prevents the verifier
from gaining any knowledge about the solution other than its correctness.
In fact, when both randomization and interaction are allowed, the proofs
that can be verified in polynomial time are exactly those proofs that canbe generated within polynomial space [19].
Formally, for a solution s to any instance I of a problem P , a convincing interactive zero-knowledge protocol between P and V must then?

This paper appears in Proceedings of SSS 2020. The final authenticated version isavailable online at https://doi.org/10.1007/978-3-030-64348-5_19.

2

L. Robert et al.

satisfy the three following properties? :Completeness: If P knows s, then he is able to convince V .
Extractability‡ : If P does not know s, then he is not able to convince
V except with some small probability. More precisely, we want a negligible probability, i.e., the probability should be a function f of a security
parameter λ (for example the number of repetitions of the protocol) suchthat f is negligible, that is for every polynomial Q, there exists n0 > 0such that:1∀ x > n0 , f (x) <.
Q(x)Zero-knowledge: V learns nothing about s except I, i.e. there exists
a probabilistic polynomial time algorithm Sim(I) (called the simulator)
such that outputs of the real protocol and outputs of Sim(I) follow thesame probability distribution.
There exist two kinds of ZKP: interactive and non-interactive. In aninteractive ZKP the prover can exchange messages with the verifier inorder to convince him, while in the non-interactive case the prover canjust create the proof in order to convince the verifier.
ZKPs are usually executed by computers. They are often used in electronic voting to prove that some parties correctly mix some ballots without cheating, or in multi-party computation [3,4,16]. Moreover, there exist
generic cryptographic zero-knowledge proofs for all problems in NP [7],via a reduction to an NP-complete problem with a known zero-knowledge
proof.
In [15], the authors explained simply this concept to some children
using a circular cave. This was the first proposition of a physical ZKP.
Later, Gradwohl et al. [9] proposed a ZKP for the famous Nikoli’s puzzle
called Sudoku§ . They just used some physical cards to construct a ZKP
protocol. It was one of the first interactive physical ZKP protocols forsuch puzzles. Our aim is to design a ZKP protocol for Suguru puzzles inthe same spirit as the one done for Sudoku.
Suguru: It was designed by Naoki Inaba, the original name of thegame was “Nanba Burokku’ but it is also known as Tectonics or Number?

Moreover, if P is NP-complete, then the ZKP should be run in a polynomial time [6].
Otherwise it might be easier to find a solution than proving that a solution is acorrect solution, making the proof pointless.
‡This implies the standard soundness property, which ensures that if there exists nosolution of the puzzle, then the prover is not able to convince the verifier regardlessof the prover’s behavior.
§
https://www.nikoli.co.jp/en/puzzles/sudoku.html

Physical Zero-Knowledge Proof for Suguru Puzzle

2

3

4

4
3
3
5
Fig. 1. Initial Suguru grid

Blocks. Suguru is a paper and pencil puzzle in which a grid is divided
into outlined blocks called region. Each region containing up to five cells.
Every cell of the grid must contain a number from 1 to 5 (according to
the number of cells in the region). Each cell should be filled such that notwo identical numbers touch — not even diagonally.
Suguru’s rule: This puzzle is formed by a rectangular grid where blocks
divide the overall area. Those blocks called region contain up to five cells.
The goal is to fill all the cells with integers under the following constraints:– Number region rule: A region composed of k cells must be filledwith integers 1, . . . , k.
– Neighbour rule: For every cell, all of its eight neighbours must havedifferent values from the cell’s value.
In Figure 1, we give an example of an initial Suguru grid and in
Figure 2 we give its unique solution.
Contributions: We propose a simple ZKP protocol for Suguru using asmall number of cards. Our construction is simple and can be used as apedagogical example to explain the role of ZKP protocols. We propose
an encoding of the number using simple cards. Using this encoding, theprover places some cards on the grid according to its solution. We use
these cards to prove that the two rules of Suguru are satisfied. We startwith the first number of cell in a region, after having verified the validityof all regions and replacing the cards placed by the prover, we reuse them

4

L. Robert et al.

2

5

2

4

1

3

1

3

4

2

5

2

5

1

3

1

3

2

4

2

4

1

5

1

Fig. 2. Solution of the Suguru grid of Figure 1

to prove the second rule of Suguru about the eight neighbours of each cellof the grid. Here is the difficulty of Suguru, since we need to prove that allvalues of the eight neighbours of each cell are different without revealing
any information to the verifier. Here, we use a trick of our encoding of thevalues of the cards in order not to leak any information. Our encoding
requires five cards per cell; therefore if a Suguru grid has n cells to guess,our protocol only requires 5n+5 cards. Finally, we prove the three security
properties of our construction i.e., completeness, extractability, and zeroknowledge.

Related Work: In [18] the authors proposed an improved ZKP protocol for
Sudoku that follows the pioneer work of [9]. In [5], the authors proposed
a ZKP protocol for the Nikoli’s puzzle Norinori.
In [12], a method to take into account one feature of several puzzles
that consists to construct a single loop, has been invented. This techniqueused a topological approach with successive interactive transformations.
Recently several ZKP proofs have been proposed for different Nikoli’s
puzzles. In [13], card-based ZKP Protocols for Takuzu and Juosan havebeen proposed. In [17] a physical ZKP proof for Numberlink has been
designed. In [14], a card-based physical ZKP for Kakuro have been giventhat improves the first version proposed by Bultel et al. in [1] with the
ZKP protocols for three other Nikoli’s games: Akari, Takuzu, and Kenken.

Physical Zero-Knowledge Proof for Suguru Puzzle

5

All these works clearly demonstrate that designing physical ZKP isclearly an interesting topic of research. Each game has its own particular
rules and requires an adapted construction.
Although the existence of all those previous works, one cannot reuseor adapt directly them for the Suguru game. Indeed, the main reason is
the “strong” neighbour rule where no cell can have its eight neighbours
with the same value. Other puzzles have a similar rule but with relaxed
restrictions. For instance, Makaro has a neighbour rule but only for adjacent cells (and not in diagonal). Thus a naive adaptation would imply
a loss in terms of efficiency and of zero-knowledge (no information about
the solution can be leaked). Furthermore, it is worth noting that the encoding for the proof of NP-completness of Makaro cannot be applied for
Suguru. Thus ZKP for Suguru cannot be directly adapted from the ZKPof Makaro. Further discussion is given in Section 5.
Outline: In Section 2, we present our notations, and all subprotocols
needed to construct our ZKP. In Section 3, we design our ZKP protocol for
Suguru. In Section 4, we prove the security of our protocol. In Section 5,
we discuss a complexity of Suguru and of Makaro. In the last section, we
conclude the paper.

2

Preliminaries

We introduce some notations of cards and shuffles used in our construction.
2.1

Notations

Card: A deck of cards used in our protocol consists of blacks ♣ andreds ♥ whose back sides are identical ? . Each integer i ∈ {1, . . . , 5} isencoded as:
1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

♥ ♣ ♣ ♣ ♣, ♣ ♥ ♣ ♣ ♣, ♣ ♣ ♥ ♣ ♣,
|
{z
} |
{z
} |
{z
}
1

2

1
3

4

5

1

2

2
3

3

4

5

♣ ♣ ♣ ♥ ♣, ♣ ♣ ♣ ♣ ♥ .
|
{z
} |
{z
}
4

5

We call such face-down five cards ? ? ? ? ? corresponding to an integer according to the above encoding rule a commitment to the respective
integer.
We also use numbered cards such as 1 2 3 4 5 whose backs are
identical ? .

6

L. Robert et al.

Neighbour cell: Consider a target cell denoted ct on a grid. A cell is aneighbour of ct if it is next to ct . It can be on the left, the right, the top,or the bottom of ct , and also on its diagonal:

ct

Thus, a cell can have at most eight neighbours.
Pile-scramble shuffle: A shuffle used in our protocol is a pile-scramble
shuffle, which was first used by Ishikawa et al. [10] and was used in otherphysical ZKP protocols for puzzles (e.g., Sudoku [18]). Consider that wehave a sequence of ` piles of cards, each of which consists of the same
number of face-down cards, denoted by (p1 , p2 , . . . , p` ) for some positive integer `. Applying a pile-scramble shuffle to the sequence resultsin (pr−1 (1) , pr−1 (2) , . . . , pr−1 (`) ) where permutation r is uniformly and randomly chosen from the symmetric group of degree `. That is, it randomly
permutes a sequence of piles and nobody knows the order of the resulting
sequence.
One can easily implement a pile-scramble shuffle by using physicaltools that can fix each pile of cards such as rubber bands and envelopes;
a player (or players) randomly shuffle them until nobody traces the orderof the piles.

3

ZKP Protocol for Suguru

We propose a ZKP protocol for Suguru composed of two phases, the setup
phase and the verification phase.
3.1

Setup phase

The verifier V and the prover P place commitments corresponding to theintegers on the initial grid of a Suguru puzzle. In addition, when a regionof k cells is already filled with k − 1 cells, then P and V agreed on thelast cell to complete and place the commitment accordingly¶ .
Then, P continues to place commitments on all the remaining cellsby himself according to the solution of the puzzle.
¶

For example, in Figure 1 the upper left region can be directly completed with a 1.

Physical Zero-Knowledge Proof for Suguru Puzzle

3.2

7

Verification phase

There are two verifications to ensure the number region rule and theneighbour rule.
Number region rule: V wants to check that a region of k cells contains all
the consecutive integers from 1 to k.
1. For every i, 1 ≤ i ≤ k, V picks all cards of the i-th cell (in any
ordering) to form a pile pi . Then, V attaches a numbered card i topi . Thus, there are p1 , . . . , pk piles, each of which consists of six cards.
2. Apply the pile-scramble shuffle [10].
3. V reveals the cards of each pile except for the numbered card. The
revealed output is of the form (up to a permutation in the rows), i.e.,
all the k (opened) commitments corresponding to 1 through k should
appear. For example, if k = 4, the revealed output should be of thefollowing form (up to a permutation in the rows):♥♣♣♣♣ ?
♣♥♣♣♣ ?
♣♣♥♣♣ ?

,♣♣♣♥♣ ?
where the face-down cards on the right side are the numbered cards.
If the revealed output is not of this form, V aborts.
4. Turn over the face-up cards and apply the pile-scramble shuffle again
to the piles.
5. Reveal only the numbered cards of all piles. Because these revealed
cards indicate the initial positions for each pile, V rearranges eachpile back to their initial place. The revealed numbered cards can bereused for the remaining verifications.
Neighbour rule: V wants to check if a given cell has no neighbour having
the same integer as the cell.
1. V picks the first card of the target commitment and then picks eachfirst card of the commitments on its neighbour cells (in any ordering)
to form the pile p1 . The following is an example when there are eight8

L. Robert et al.

neighbours:
7

8

9? ? ? ? ?

? ? ? ? ?

? ? ? ? ?

6

1

2

? ? ? ? ?

? ? ? ? ?

? ? ? ? ? →

5

4

3

? ? ? ? ?

? ? ? ? ?

? ? ? ? ?

1

2

3

4

p1 : ? ? ? ?
5

6

7

8

9

.

? ? ? ? ?

2. V repeats the same operation until the pile p5 is formed.
3. V attaches a numbered card i to pi . (If the target cell is the last one,
V does not perform this step.)
4. If an integer is written on the target cell, then go to the next step.
Otherwise, apply the pile-scramble shuffle to the piles.
5. V reveals the first card of each pile, which corresponds to the target
commitment. Let pt denotes the pile where a red card appears.
6. V reveals all the cards in the pile pt except for the numbered cards. If
there are two red cards in the pile then V aborts; otherwise, V goesto the next step.
7. As Steps 4 and 5 in the previous verification, V rearranges all the
cards in the piles back to their initial places. (If the target cell is thelast one, V does not perform this step.)
3.3

Evaluation

If the size of the grid is represented by n then the number of cards usedin this protocol is equal to 5n + 5. Indeed, each cell must be encoded with
5 cards (4 blacks and 1 red)k and 5 numbered cards are used for all target
cell.

4

Security proofs

We give the theorems along with their proofs to provide that our protocol
respects the security properties. A ZKP protocol is secure if the following
three properties are satisfied:Correctness: If the prover P commits its cards according to the actual
solution, then all verifications will not abort. Hence, if P knows asolution, then it can always convince the verifier V . Correctness isproven in Theorem 1.
k

We could have encoded each cell with a total of ` cards where ` is the number ofcells in the region (thus, a region with two cells has its cell encoded with only two
cards, a red and a black). Yet, this would lead to inconstancy in the encoding rule
which is required in the neighbour verification.

Physical Zero-Knowledge Proof for Suguru Puzzle

9

Extractability: If P ’s input is invalid, the protocol will point errors out
to V . Therefore, if P does not know the solution, it cannot convince
V . Extractability is proven in Theorem 2.
Zero-knowledge: V learns nothing about P ’s solution. Zero-knowledge
is proven in Theorem 3.
Theorem 1 (Completeness). If P knows a solution of a Suguru grid,then it can convince V .
Proof. Suppose that the prover P knows the solution of the Suguru grid.
It runs with the verifier V the Setup phase (Section 3.1). We show that
P can perform both verification phases without aborting.
Number region verification: In this phase, the goal of P is to show thateach region of size k contains consecutive integers from 1 to k (note thatthe lower bound of k is 1 and its upper bound 5). Since P places the cards
accordingly with the solution, each region of size k contains the numbers
1 to k. Without loss of generality, suppose that the pile pi corresponds
to the number i with i = 1 . . . k. The pile p1 is composed of the sequence(in this order):♥ ♣ ♣ ♣ ♣.
The pile p2 is composed of the sequence (in this order):♣ ♥ ♣ ♣ ♣.
More generally, the pile pi is a sequence of black cards where the red cardis placed on position i.
Since the pile-scramble shuffle applied on Step 2 does not modify theorder of the sequence, the red card of pile pi is on position i. As i = 1 . . . k,
all numbers from 1 to k are represented. Thus, V is convinced that the
number region rule is verified by revealing the piles in Step 3.
Neighbour verification: The goal of P is to convince V that no cell has
the same number of its neighbours (there are eight neighbours as definedin Section 2). Let ct be the target cell placed on the center of the 3 × 3
square. Since P placed the commitments according to the solution, there
is no cell with the same value of ct in this square. Let i be the position of
the red card of ct (with i = 1 . . . 5). Since no neighbour cell has the samevalue of ct , there is no other red card with position i. Since each pile iscomposed of card with the same indices, the pile pi (before the shuffle)

10

L. Robert et al.

contains exactly one red card. Hence, V is convinced that the neighbour
rule is verified.
Finally, since all verifications are checked, we proved that if P has thesolution then the verifications will always succeed.
tu
Theorem 2 (Extractability). If P does not provide a solution of the
Suguru puzzle, it is not able to convince V .
Proof. Suppose that P does not know a solution for the puzzle. We want
to show that V will always detect it.
Since P cannot provide the solution, at least one of the two rules is notverified (if both can be verified, this is the solution). We can distinguish
two cases corresponding to each verification:– The number region rule is not respected. That is, suppose w.l.o.g. thata region of size k with k > 1 does not contain the number 1. Hence,the sequence corresponding to this number is missing, meaning that
V cannot reveal at Step 3 the sequence:♥ ♣ ♣ ♣ ♣.
Thus, V will abort the protocol and detect that P cannot provide thesolution.
– The neighbour rule is not respected. Suppose that we have the following configuration:
22

with blank cards of unimportant value but different from 2.
We encode number 2 as:♣ ♥ ♣ ♣ ♣.
Thus, the pile p2 corresponding to all the cards with indices 2 (before
the shuffle) will contain exactly two red cards. Thus, V will abort the
protocol.
We proved that if P does not have the solution then the verifications
will abort in both cases meaning that P cannot convince V .
tuPhysical Zero-Knowledge Proof for Suguru Puzzle

11

Theorem 3 (Zero-knowledge). V learns nothing about P ’s solutionof the given grid G.
Proof. We use the same proof technique as in [9]: zero-knowledge is caused
by a description of an efficient simulator which simulates interaction between a cheating verifier and a real prover. However, the simulator does
not have a solution but it can swap cards for different ones during shuffles.
The simulator acts as follows:– During the number region verification at Step 2, the simulator swaps
the piles to replace them by the sequences (up to a permutation in
the rows):
♥♣♣♣♣
♣♥♣♣♣
♣♣♥♣♣
♣♣♣♥♣
– During the neighbour verification, when revealing the cards at Step 6,
the simulator swaps the pile with a pile containing k − 1 black cards
and 1 red card.
The simulated proofs and the real proofs are indistinguishable; thus, Vlearns nothing about P ’s solution.
tu

5Discussion

Among related work introduced in Section 1, the closest work is [2], wherea ZKP for Makaro has been proposed. This game is close to the Nikoli’s
game called Makaro∗∗ where regions are called rooms and some extra
black cells indicate thanks to an arrow the position of the biggest number
among the (up to) four cells around (over, under, left, right) the cell withthe arrow (black) is in the cell the arrow points at.
In [11], the authors proved that the two games Herugolf and Makaro
are NP-complete. Solving Makaro was shown to be NP-complete via a
reduction from 3-SAT.
Makaro is a game close to Suguru, with different constraints as follows:
1. Room condition: Each room contains all the numbers from 1 up to
the number of cells in the room.
∗∗

http://nikoli.co.jp/en/puzzles/makaro.html

12

L. Robert et al.

←
3

←
→
←
Fig. 3. Example of a Makaro grid

1

2 ← 1

4

2

3

1

2

3

1

2

3

4 ←

→ 3

1

2

3

2 ← 1

2

1

Fig. 4. Solution of a Makaro grid of Figure 3

2. Neighbour condition: A number cannot be next (adjacent) to the same
number in another room.
3. Arrow condition: Every black arrow cell must point at the largest
number among the numbers in the adjacent cells of the black cell(possibly the fours cells: right, left, above, and bottom).
In Figure 3, we give a simple example of a Makaro game, where all
black cells are arrow cells and all white cells are empty cells except for
one filled cell with three. It is easy to verify that the three constraints are
satisfied in the solution given in Figure 4. We remark that in a solution
all white cells are filled with numbers between 1 and k, where k is the
maximum size of all the rooms of the grid.
The room condition is the same, however the neighbour condition isdifferent in Suguru. In Suguru for each cell, we consider the eight neighbours while in Makaro we consider only the four neighbours. Moreover in
Suguru the size of the regions is limited to five while in Makaro there isno limit on the size of the rooms.
These differences avoid us to reuse the 3-SAT encoding used in the
proof of NP-completeness of Makaro [11]. If we remove the limit of the
maximum of five cells in each region, we can use the same gadgets as

Physical Zero-Knowledge Proof for Suguru Puzzle

13

the ones used for Makaro to prove in a similar way that Suguru is also
NP-complete. But with the limit of five cells per regions and the change
of four neighbours into eight neighbours, it is not clear if we can prove
the NP-completeness of Suguru. These extra constraints seem to remove
some difficulty in finding some solutions for Suguru. At the moment weare not able to prove NP-completeness and we conjecture that solving a
Suguru grid should be in P.
Even if solving Suguru is in P, our physical ZKP is an interesting
approach since it requires only 5n + 5 cards as we show when we present
our ZKP protocol in Section 3. (In addition, it could always happen that
one cannot solve a Suguru puzzle.) This is clearly a real ZKP protocolthat can be used by Suguru players in practice.

6

Conclusion

In this paper we propose a simple card-based physical ZKP for Suguru.
Our solution is simple and efficient since it relies on only 5n + 5 cards.
One open question left for the future is to demonstrate the conjecturestates in the introduction i.e., proving that solving a Suguru grid is in P.
We clearly cannot adapt the proof of NP-completeness of Makaro withthe rules of Suguru, it is why we conjecture that Suguru is in P.
Moreover, our long term research direction is to design physical ZKP
protocols for all Nikoli’s games. However some rules of some games like
Shakashaka†† that requires to draw rectangles which is not easy to model
without leaking any information. Another example of challenging game is
Shikaku‡‡ , where the rules are simple: 1) Divide the grid into rectangles
with the numbers in the cells. 2) Each rectangle is to contain only one
number showing the number of cells in the rectangle. However it remains achallenging open question to design a physical ZKP for this game without
revealing any information on the positions of the rectangles.
Acknowledgements. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper. This work
was supported in part by JSPS KAKENHI Grant Number JP19J21153.

References
1. 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.)††‡‡

http://www.nikoli.co.jp/en/puzzles/shakashaka.html
https://www.nikoli.co.jp/en/puzzles/shikaku.html

14

L. Robert et al.

Fun with Algorithms. Leibniz International Proceedings in Informatics (LIPIcs),
vol. 49, pp. 8:1–8:20. Schloss Dagstuhl, Dagstuhl, Germany (2016), https://doi.
org/10.4230/LIPIcs.FUN.2016.8
2. 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: Stabilization, Safety, and Security of Distributed Systems. LNCS, vol. 11201,
pp. 111–125 (2018), https://doi.org/10.1007/978-3-030-03232-6_8
3. Cramer, R., Damgård, I., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) Advances in Cryptology — EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–300. Springer, Berlin, Heidelberg (2001),
https://doi.org/10.1007/3-540-44987-6_18
4. Damgård, I., Faust, S., Hazay, C.: Secure two-party computation with low communication. In: Cramer, R. (ed.) Theory of Cryptography. LNCS, vol. 7194,
pp. 54–74. Springer, Berlin, Heidelberg (2012), https://doi.org/10.1007/
978-3-642-28914-9_4
5. Dumas, J.G., Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: Interactive physical zero-knowledge proof for Norinori. In: Du, D.Z., Duan, Z., Tian,
C. (eds.) Computing and Combinatorics. LNCS, vol. 11653, pp. 166–177. Springer,
Cham (2019), https://doi.org/10.1007/978-3-030-26176-4_14
6. Goldreich, O., Micali, S., Wigderson, A.: How to prove all np statements in zeroknowledge and a methodology of cryptographic protocol design (extended abstract). In: Odlyzko, A.M. (ed.) Advances in Cryptology — CRYPTO’ 86. LNCS,
vol. 263, pp. 171–185. Springer, Berlin, Heidelberg (1987), https://doi.org/10.
1007/3-540-47721-7_11
7. Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity
for all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691–729(1991), https://doi.acm.org/10.1145/116825.116852
8. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive
proof-systems. In: Annual ACM Symposium on Theory of Computing. pp. 291–
304. STOC’85, ACM, New York (1985), https://doi.org/10.1145/22145.22178
9. Gradwohl, R., Naor, M., Pinkas, B., Rothblum, G.N.: Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles. In: Crescenzi,
P., Prencipe, G., Pucci, G. (eds.) Fun with Algorithms. LNCS, vol. 4475,
pp. 166–182. Springer, Berlin, Heidelberg (2007), https://doi.org/10.1007/
978-3-540-72914-3_16
10. Ishikawa, R., Chida, E., Mizuki, T.: Efficient card-based protocols for generating a hidden random permutation without fixed points. In: Calude, C.S.,
Dinneen, M.J. (eds.) Unconventional Computation and Natural Computation.
LNCS, vol. 9252, pp. 215–226. Springer, Cham (2015), https://doi.org/10.1007/
978-3-319-21819-9_16
11. 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. Leibniz
International Proceedings in Informatics (LIPIcs), vol. 100, pp. 24:1–24:11. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018), https://doi.org/10.4230/LIPIcs.FUN.2018.24
12. Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: A physical ZKP
for Slitherlink: How to perform physical topology-preserving computation. In:
Heng, S.H., Lopez, J. (eds.) Information Security Practice and Experience. LNCS,
vol. 11879, pp. 135–151. Springer, Cham (2019), https://doi.org/10.1007/
978-3-030-34339-2_8

Physical Zero-Knowledge Proof for Suguru Puzzle

15

13. Miyahara, D., Robert, L., Lafourcade, P., Takeshige, S., Mizuki, T., Shinagawa,
K., Nagao, A., Sone, H.: Card-based ZKP protocols for Takuzu and Juosan. In:
Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) Fun with Algorithms. Leibniz International Proceedings in Informatics (LIPIcs), vol. 157, pp. 20:1–20:21.
Schloss Dagstuhl, Dagstuhl, Germany (2020), https://doi.org/10.4230/LIPIcs.
FUN.2021.20
14. Miyahara, D., Sasaki, T., Mizuki, T., Sone, H.: Card-based physical zero-knowledge
proof for Kakuro. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 102(9),1072–1078 (2019), https://doi.org/10.1587/transfun.E102.A.1072
15. Quisquater, J.J., Quisquater, M., Quisquater, M., Quisquater, M., Guillou, L.,
Guillou, M.A., Guillou, G., Guillou, A., Guillou, G., Guillou, S.: How to explain
zero-knowledge protocols to your children. In: Brassard, G. (ed.) Advances in Cryptology — CRYPTO’ 89. LNCS, vol. 435, pp. 628–631. Springer, New York (1990),
https://doi.org/10.1007/0-387-34805-0_60
16. Romero-Tris, C., Castellà-Roca, J., Viejo, A.: Multi-party private web searchwith untrusted partners. In: Rajarajan, M., Piper, F., Wang, H., Kesidis, G.
(eds.) Security and Privacy in Communication Networks. LNICST, vol. 96,
pp. 261–280. Springer, Berlin, Heidelberg (2012), https://doi.org/10.1007/
978-3-642-31909-9_15
17. Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for Numberlink. In:
Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) Fun with Algorithms. Leibniz International Proceedings in Informatics (LIPIcs), vol. 157, pp. 22:1–22:11.
Schloss Dagstuhl, Dagstuhl, Germany (2020), https://doi.org/10.4230/LIPIcs.
FUN.2021.22
18. Sasaki, T., Miyahara, D., Mizuki, T., Sone, H.: Efficient card-based zero-knowledge
proof for Sudoku. Theor. Comput. Sci. 839, 135–142 (2020), https://doi.org/
10.1016/j.tcs.2020.05.036
19. Shamir, A.: IP = PSPACE. J. ACM 39(4), 869–877 (1992), https://doi.org/10.
1145/146585.146609