Two UNO Decks Efficiently Perform
Zero-Knowledge Proof for Sudoku⋆
Kodai Tanaka1 and Takaaki Mizuki2
1

Graduate School of Information Sciences, Tohoku University, Sendai, Japan
2
Cyberscience Center, Tohoku University, Sendai, Japan

Abstract. Assume that there is a challenging Sudoku puzzle such thata prover knows a solution while a verifier does not know any solution. A
zero-knowledge proof protocol allows the prover to convince the verifierthat the prover knows the solution without revealing any information
about it. In 2007, Gradwohl et al. constructed the first physical zeroknowledge proof protocol for Sudoku using a physical deck of playing
cards; its drawback would be to have a soundness error. In 2018, Sasaki
et al. improved upon the previous protocol by developing soundnesserror-free protocols; their possible drawback would be to require many
standard decks of playing cards, namely nine (or more) decks. In 2021,
Ruangwises designed a novel protocol using only two standard decks ofplaying cards although it requires 322 shuffles, making it difficult to use
in practical applications. In this paper, to reduce both the numbers ofrequired decks and shuffles, we consider the use of UNO decks, which
are commercially available: we propose a zero-knowledge proof protocol
for Sudoku that requires only two UNO decks and 16 shuffles. Thus, theproposed protocol uses reasonable numbers of decks and shuffles, and webelieve that it is efficient enough for humans to execute practically.
Keywords: Card-based cryptography, Sudoku, Zero-knowledge proof

1

Introduction

Sudoku is one of the most popular pencil puzzles in the world. A standard Sudoku
puzzle consists of a 9 × 9 grid divided into 9 sub-grids (whose sizes are 3 × 3); wecall such a sub-grid a block throughout this paper. Some of the cells on the grid
are already filled with numbers from 1 through 9, and the goal of the puzzle is⋆

Sudoku and UNO are trademarks or registered trademarks of Nikoli Co., Ltd. andMattel, Inc., respectively.
This paper appears in Proceedings of FCT 2023. 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: http://dx.doi.org/10.
1007/978-3-031-43587-4_29. 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.

2

K. Tanaka and T. Mizuki

2

4
2

1

7

8
7
6

4

5

8 9
6

6 5
5 8

4
3
4
7
5

3

9 2 6 3 4 5 8 1 7
8 5 1 7 2 6 3 9 4
4 7 3 8 9 1 2 6 5
7 3 4 1 6 2 5 8 9
6 8 5 4 7 9 1 2 3
2 1 9 5 3 8 7 4 6
5 6 8 9 1 3 4 7 2
3 4 2 6 8 7 9 5 1
1 9 7 2 5 4 6 3 8

Fig. 1: Example of a standard Sudoku puzzle and its solution

to place a number on each empty cell so that exactly one number from 1 to 9
appears in each row, each column, and each block. Figure 1 shows an example
of a puzzle instance and its solution.
1.1

Zero-knowledge Proof for Sudoku

Assume that a player P had created a challenging Sudoku puzzle and P showed
the puzzle to another player V . The player V has spent much time and effort
finding a solution, but V cannot find any solution. The player V gets skeptical
about whether the puzzle really has a solution. As easily imaged, this is the rightopportunity to make use of the zero-knowledge proof [3]. Thus, this paper deals
with zero-knowledge proof protocols for Sudoku.
In addition, we solicit physical zero-knowledge proof protocols that do not
use any electronic devices such as computers, but use everyday objects suchas a physical deck of playing cards. Physical protocols tend to be simple andeasy-to-understand so that lay-people can easily execute them.
1.2

The Existing Protocols

In 2007, for the first time, Gradwohl et al. [4, 5] developed several physical zeroknowledge proof protocols for Sudoku. Among them, the most easy-to-implement
protocol would be the one which uses a physical deck of playing cards. This
protocol is the first card-based zero-knowledge proof protocol for Sudoku; roughly
speaking, after a prover P places face-down cards to commit to the solution
P has, the protocol applies a series of actions, such as shuffling and turningover cards, to convince a verifier V that P surely knows the solution. Since theprotocol has a soundness error, it must be repeated many times to make thesoundness error probability negligibly small.
Later in 2018, Sasaki et al. [28] improved upon the previous protocol bydevising a new technique (called the “uniqueness verification protocol” as will
be seen in Sect. 2.3) to eliminate the soundness error. Specifically, they proposed
three zero-knowledge proof protocols for Sudoku having no soundness error [27];
we name them Sasaki’s Protocols A, B, and C, whose performances are shown

Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku

3

Table 1: Comparison of the proposed protocol with the existing protocols
Protocols

Number of cards Accommodating decks Number of shuffles Interactive?
(
9 standard decks
45
No90
5 UNO decks(
18 standard decks
36
No
171
9 UNO decks(
27 standard decks
28
Yes
243
14 UNO decks

Sasaki’s Protocol A [27]Sasaki’s Protocol B [27]Sasaki’s Protocol C [27]Ruangwises’s Protocol A [22]120

3 standard decks

108

Yes

Ruangwises’s Protocol B [22]108

2 standard decks

322

Yes

Ours

117

2 UNO decks

16

No

as the first three protocols listed in Table 1. For instance, Sasaki’s Protocol
A uses 9 sets of 9 numbered cards 1 2 3 4 5 6 7 8 9 as well as arbitrary
distinct 9 cards, and hence, it requires 90 cards in total and all the required cards
can be accommodated by 9 standard decks of playing cards. As for the numberof shuffles, it applies a “pile-scramble shuffle” (which is a kind of a shufflingaction as seen later in Sect. 2.2) 45 times. As known from Table 1, Sasaki’s
protocols require at least 9 standard decks and at least 28 shuffles. Note that
Sasaki’s Protocols A and B are “non-interactive” whereas Sasaki’s Protocol C is
“interactive.”iii A non-interactive card-based zero-knowledge proof protocol uses
no prover’s knowledge after a prover commits to a solution with face-down cards(and hence, the protocol can be executed by either a prover or a verifier, or evena third party) [12]. By contrary, an interactive card-based zero-knowledge proof
protocol requires prover’s knowledge during the execution of the protocol.
In 2021, to reduce the number of required standard decks, Ruangwises [21,22]
proposed two novel interactive protocols, which we name Ruangwises’s Protocols
A and B, using two or three standard decks of playing cards. For instance,
Ruangwises’s Protocol B requires two sets of 13 × 4 = 52 cards♣A ♢A ♡A ♠A ♣2 ♢2 ♡2 ♠2 · · · ♣K ♢K ♡K ♠K

along with two jokers (i.e., two cards of different patterns); therefore, two standard decks can accommodate all the required cards. Thus, Ruangwises’s Protocol
B is very efficient in terms of the number of required decks. However, the numberof required shuffles is 322, which is too many for humans to execute. Overall, as
known from Table 1, Ruangwises’s protocols use only two or three decks while
requiring at least 108 shuffles.
1.3

Contribution of This Paper

In this paper, instead of standard decks, we consider the use of UNO decks,
which are also commercially available over the world. Specifically, we constructiii

The usage of these terms is valid only for card-based zero-knowledge proof protocols.

4

K. Tanaka and T. Mizuki(a) Yellow, red, and blue numbered cards(b) 27 distinct cards

Fig. 2: UNO cards to usea zero-knowledge proof protocol for Sudoku that works on two UNO decks using
only 16 shuffles. Our proposed protocol is non-interactive (and has no soundness
error); see the last line in Table 1.
The specific numbers of required cards are as follows. We use four sets ofyellow numbered cards
Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 ,three sets of red numbered cards
R1 R2 R3 R4 R5 R6 R7 R8 R9 ,and three sets of blue numbered cards
B1 B2 B3 B4 B5 B6 B7 B8 B9(as partially illustrated in Fig. 2(a)) along with 27 arbitrary distinct cards (asillustrated in Fig. 2(b)). One can easily confirm that two UNO decks can accommodate all the necessary cards mentioned above.
Making use of “color information” of cards, as will be seen, we can aggregate
necessary shuffles, resulting in only the 16 shuffles. The shuffling operation our
protocol uses is also the pile-scramble shuffle; our protocol uses such a shuffle
for 27 cards whereas the existing ones use it for 9 cards or less. Note that apile-scramble shuffle for 27 cards is also easy-to-implement.
Needless to say, zero-knowledge proofs play an important role in providing
security and privacy. As Hanaoka [6] mentioned, for technology diffusion, we
require easy-to-understand structures of cryptographic tools whereby potential
users can easily understand the essential mechanisms. Since Sudoku is one of
the most famous puzzles and our protocol is quite simple, our protocol might
motivate potential users to try to use zero-knowledge proof technology.
1.4

Related Work

Aside from Sudoku, many physical zero-knowledge proof protocols have been
constructed for other pencil puzzles. Examples are as follows: Akari [1], Hashiwokakero (Bridges) [25], Heyawake [19], Kakuro [1,14], Makaro [2,26], Masyu [10],Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku

5

Numberlink [23, 24], Nurikabe [18, 19], Slitherlink [10, 11], Suguru [17, 20], andTakuzu [1, 13].

2Preliminaries

In this section, we formally describe the cards and actions on them, and explain
the “pile-scramble shuffle.” Then, we introduce the “uniqueness verification protocol,” which we will use as a sub-protocol in our protocol.
2.1

Cards and ActionsFirst, as mentioned in Sect. 1.3, we use numbered cards of three colors (yellow,
red, and blue); the face of every card has a number from 1 through 9 and thepatterns of the backs of all cards are identical, illustrated as
face up: R1 Y6 B9 ,face down: ?

?

? .

Specifically, as mentioned before, we use four sets of yellow numbered cards
Y1 Y2 · · · Y9 , three sets of red numbered cards R1 R2 · · · R9 , and three sets ofblue numbered cards B1 B2 · · · B9 . We call these cards encoding cards, which
we will use to represent a solution to a Sudoku puzzle.
In addition to the encoding cards, 27 distinct cards h1 h1 · · · h27 with theidentical backs ? ? · · · ? are used; these are called helping cards. We choose
helping cards from UNO decks as already illustrated in Fig. 2(b).
Our proposed protocol follows the standard computational model of cardbased cryptographic protocols [8,9,15,16], in which a protocol is formally defined
as an abstract machine. Here, we introduce three main actions, which are applied
to a sequence of cards; below, we assume a sequence of m cards.
Permute.
This is denoted by (perm, π), where π is a permutation applied to the sequence of cards as follows:2

1m? ? ··· ?

π −1 (1) π −1 (2)(perm,π)−−−−−→?

?

π −1 (m)

···

.

?

Turn.
This is denoted by (turn, T ), where T is a set of indices, indicating that forevery t ∈ T , the t-th card is turned over as follows:
t∈T

2

1

m

(turn,T )1? ? · · · ? · · · ? −−−−−→

t∈T

2

m

? ? · · · R1 · · · ? .

Shuffle.
This is denoted by (shuf, Π), where Π is a set of permutations, indicatingthat π ∈ Π is drawn uniformly and is applied to the sequence of cards asfollows:
1

2

m? ? ··· ?

π −1 (1) π −1 (2)(shuf,Π)−−−−−→?

?

π −1 (m)

···

?

.

6

K. Tanaka and T. Mizuki

Although a protocol is supposed to be defined with a combination of theactions above (or an abstract machine), in the sequel, we use a natural language
to describe a protocol for simplicity.
2.2

Pile-Scramble Shuffle

In our protocol, we use the pile-scramble shuffle, which was devised in [7].
Assume that there are k piles of cards, denoted by pi for every i, 1 ≤ i ≤ k,such that all the piles have the same number of cards:··· ? .
?
?
|{z} |{z}
|{z}
p1

p2

pk

A pile-scramble shuffle is a shuffling action that applies a random permutationr ∈ Sk to the sequence of piles, denoted by [·| · · · |·]:
i
h
···
→ ?
··· ?
,
?
?
?
?
|{z} |{z}|{z}|{z} |{z}
|{z}
p1

p2

pk

pr−1 (1) pr−1 (2)pr−1 (k)where Sk denotes the symmetric group of degree k.
A pile-scramble shuffle can be implemented in practice by placing each pileof cards in a sleeve or envelope and stirring the envelopes (until the original
sequence is no longer discernible).
2.3

Uniqueness Verification Protocol

This subsection explains the uniqueness verification protocol using the pilescramble shuffle described in Sect. 2.2. This protocol has been proposed by Sasaki
et al. [27, 28].
Assume that there is a sequence of k face-down cards ? ? · · · ? such thatit consists of k distinct cards a1 a2 · · · ak arranged in an unknown order. The
uniqueness verification protocol enables us to confirm that the sequence surely
consists of these k distinct cards without revealing the unknown order while
keeping the original sequence unchanged. The protocol uses k helping cards
h1 h2 · · · hk and proceeds as follows.
1. Place the k helping cards below the unknown sequence, turn them face down,
and apply a pile-scramble shuffle as follows:? ? ··· ?
?
?
?
? ? ··· ?
→
→
···
.
h1 h2 · · · hk?
?
?
? ? ··· ?
2. Turn over all the cards of the top sequence to verify that it consists of{a1 , a2 , . . . , ak }:?

? ··· ?

?

? ··· ?

→

a7 ak · · · a3?

? ··· ?

.

Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku

7

A B C
D E F
G H I
Fig. 3: The names of the 9 blocks

3. After turning over all the cards of the top sequence, apply a pile-scramble
shuffle:?
?
?
? ? ··· ?

→
···
.
?
?
?
? ? ··· ?
4. Turn over all the cards of the bottom sequence and sort the piles so that thebottom sequence becomes h1 , h2 , . . . , hk in this order:?

? ··· ?

h2 h5 · · · h3→?

? ··· ?

h1 h2 · · · hk.

This restores the original sequence.
As mentioned above, we utilize this uniqueness verification protocol as a
sub-protocol when constructing our protocol.

3

Building Blocks

Our proposed protocol consists of several sub-protocols: the color verification,
row verification, color change, and column verification sub-protocols. In this section, we present these sub-protocols as building blocks for our proposed protocol(which will be shown in the next section). Hereinafter, we call the 9 blocks of a
Sudoku puzzle Blocks A, B, C, . . . , H, I as shown in Fig. 3.
We first explain how a prover P commits to a solution with face-down encoding cards in Sect. 3.1, and then the sub-protocols will be presented in the
succeeding subsections.
3.1

Commitment to a Solution

Assume that a prover knows a solution of a given 9×9 Sudoku puzzle. According
to the solution, the prover P secretly arranges face-down encoding cards asfollows.
1. Prepare three sets of encoding cards Y1 Y2 · · · Y9 R1 R2 · · · R9 B1 B2 · · · B9.

8K. Tanaka and T. Mizuki(a) An actual
placement byP(b) The placement after turning over face-up
cards(c) Color scheme
for input(d) After applying
the color change
protocolFig. 4: Commitment to a solution by a prover and color schemes for input blocks
and those after color change

2. P and V (or someone) publicly place an encoding card on each cell that
already has a number written on it such that the number of the card isequal to the written number (on the cell) and its color matches the color
scheme for blocks shown in Fig. 4(c) (i.e., yellow cards are placed in Blocks
A, B, and C, red cards in Blocks D, E, and F , and blue cards in Blocks G,
H, and I).
3. According to the solution, P secretly places face-down encoding cards on
the remaining empty cells (without V ’s seeing the faces), based on the samecolor and number schemes as in the previous step.
In this way, the prover P commits to the solution with face-down encoding
cards; Fig. 4(a) illustrates an actual placement by P , and Fig. 4(b) shows theplacement after turning over all the face-up cards, which we sometimes call acommitment to the solution.
3.2

Color Verification Sub-protocol

Given a commitment to a solution (as illustrated in Fig. 4(b)), we first want tocheck that the face-down cards satisfy the color scheme properly. That is, given
three rows of length 9:
?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

? ,

?

?

?

?

?

?

?

?

?

we want to verify that all cards have the same color, say yellow. More precisely,
the following color verification sub-protocol can confirm that the 27 cards consistof three sets of Y1 Y2 · · · Y9 using 27 helping cards.

Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku

9

1. Make a sequence of length 27 from the three rows, and place the 27 helping
cards below it:? ? ? ? ? ··· ? ? ?
.
h1 h2 h3 h4 h5 · · · h25 h26 h27
2. Apply the uniqueness verification protocol described in Sect. 2.3. If theopened cards do not consist of three sets of Y1 Y2 · · · Y9 , the protocol
aborts.
3. Move the face-down cards (of the top sequence) back to the original positions
to restore the three rows.
3.3

3-row Verification Sub-protocol

Suppose that all the cards in Blocks A, B, and C are yellow, all the cards inBlocks D, E, and F are red, and all the cards in Blocks G, H, and I are blue.
The 3-row verification sub-protocol can verify that each of the three rows (ofdifferent colors) consists of numbers 1 through 9. Take Rows 1, 4, and 7 as an
example for row verification:
Row 1:

?

?

?

?

?

?

?

?

?

Row 4:

?

?

?

?

?

?

?

?

? .

Row 7:

?

?

?

?

?

?

?

?

?

1. Make a sequence of 27 cards from the three row and place 27 helping cards
below it:
? ? ? ? ? ··· ? ? ?
.
h1 h2 h3 h4 h5 · · · h25 h26 h27
2. Apply the uniqueness verification protocol described in Sect. 2.3. If theopened cards do not consist ofY1 Y2 · · · Y9 R1 R2 · · · R9 B1 B2 · · · B9 ,the protocol aborts.
3. Move the face-down cards (of the top sequence) back to the original positions
to restore the three rows.
The same can be applied to the other three rows (of different colors).
3.4

Color Change Sub-protocol

In this subsection, we present the color change sub-protocol, which changes only
the colors of the cards in blocks without changing their numbers as well as
provides block verification.

10

K. Tanaka and T. Mizuki

Assume that there are three blocks, the first one consisting of yellow cards,
the second one consisting of red cards, and the third one consisting of blue cards.
The following procedure exchanges the colors of the first and second blocks aswell as changes the color of the third block into yellowiv .
1. Make a sequence of 27 cards from the three blocks and place 27 helping cards
below it:?

?

?

? ··· ?

?

?

?

.

h1 h2 h3 h4 h5 · · · h25 h26 h27
2. Apply a pile-scramble shuffle to them. Turn the encoding cards face up,
making sure that the yellow, red, and blue cards from 1 to 9 appear withoutomission (otherwise it aborts):



?

?

?

?

···

?
?



Y3 R3 B6 · · · Y5

→

?

.

? ··· ?

?

3. For yellow and red cards, swap the cards with the same number (for example,
swap the positions of the yellow 3 and the red 3). For blue cards, preparing
9 free yellow cards Y1 Y2 · · · Y9 ,v swap the cards with the same number:Y3 R3 B6 R8 · · · Y5
?

?

?

→

? ··· ?

R3 Y3 Y6 Y8 · · · R5
?

?

?

.

? ··· ?

4. Turn the encoding cards face down and apply a pile-scramble shuffle:



?

?

?

?

···

?
?


→

?

? ··· ?

?

? ··· ?

.

5. Turn over all the cards of the bottom sequence and sort the piles so that thebottom sequence become h1 , h2 , . . . , h27 in this order. Return the encoding
cards to their original positions:?

? ··· ?

h2 h5 · · · h3→?

? ··· ?

h1 h2 · · · h27.

Note that this sub-protocol also checks that each of the three blocks consistsof numbers from 1 to 9.
iv
v

The sub-protocol works for other combinations of colors.
This is why our protocols needs four sets of yellow cards.

Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku

3.5

11

3-column Verification Sub-Protocol

Suppose that all the cards in Blocks A, D, and G are yellow, all the cards inBlocks B, E, and H are red, and all the cards in Blocks C, F, and I are blue.
The 3-column verification sub-protocol can verify that each of the three columns(of different colors) consists of numbers 1 through 9 while it does not revert
the blocks contrary to the 3-row verification sub-protocol presented in Sect. 3.3.
Take Columns 1, 4, and 7 as an example for column verification:
Column 1:

?

?

?

?

?

?

?

?

?

Column 4:

?

?

?

?

?

?

?

?

? .

Column 7:

?

?

?

?

?

?

?

?

?

1. Make a sequence of 27 cards from the three columns and apply a pilescramble shuffle (i.e., a normal shuffle):ih? ? ··· ? →→ ? ? ··· ? .
?
? ··· ?
2. Turn over all the 27 cards. If the opened cards do not consist ofY1 Y2 · · · Y9 R1 R2 · · · R9 B1 B2 · · · B9 ,the protocol aborts.
Since this sub-protocol will be used at the last step of our proposed protocol,
there is no need to restore the three retrieved columns. Therefore, the uniquenessverification protocol described in Sect. 2.3 is not used. The same can be applied
to other three columns (of different colors).

4

Our Protocol for 9 × 9 Sudoku

In this section, we construct a zero-knowledge proof protocol for a standard
Sudoku puzzle.
A prover P who knows a solution places a commitment to the solution as
described in Sect. 3.1, and this is the input to the protocol. After the input isgiven, the protocol does not require the knowledge of the prover P and can be
executed by anyone thereafter (because our protocol is non-interactive).
Given the placement by P along with 27 helping cards and free 9 cards
Y1 Y2 · · · Y9 , our protocol proceeds as follows.
1. Apply the color verification sub-protocol given in Sect. 3.2 to each of Blocks
A, B, C, Blocks D, E, F , and Blocks G, H, I. If it does not abort, Blocks
A, B, C consist of three sets of Y1 Y2 · · · Y9 , Blocks D, E, F consist of threesets of R1 R2 · · · R9 , and Blocks G, H, I consist of three sets of B1 B2 · · · B9 .

12

K. Tanaka and T. Mizuki

2. Apply the 3-row verification sub-protocol given in Sect. 3.3 to Rows 1, 4,
and 7. Apply also the 3-row verification sub-protocol to Rows 2, 5, and 8. If
it does not abort, Rows 1, 2, 4, 5, 7, and 8 consist of numbers 1 through 9.
In addition, this result together with the result of the color verification in
the previous step automatically implies that the remaining Rows 3, 6, and 9
must consist of numbers 1 through 9.
3. In order to be able to verify the columns, we want to change the colorof Blocks A, D, and G to yellow, Blocks B, E, and H to red, and Blocks
C, F, and I to blue, as shown in Fig. 4(d). First, apply the color change
sub-protocol described in Sect. 3.4 to Blocks B, D, and G with colors yellow, red, and blue in this order. This swaps the colors of Blocks B and D,
and changes the color of Block G to yellow. (This produces 9 free cards
B1 B2 · · · B9.) Second, apply the color change sub-protocol to Blocks H, F ,and C with colors blue, red, and yellow in this order. This swaps the colors
of Blocks H and F , and changes the color of Block C to blue. Through thesecolor transformations, Blocks B, C, D, F, G, and H are verified to consistof numbers 1 through 9. In addition, based on the results of Step 1, it isautomatically guaranteed that the remaining Blocks A, E, and I consist of
numbers 1 through 9.
4. Apply the 3-column verification sub-protocol described in Sect. 3.5 to Columns
1, 4, and 7. The same procedure is applied to Columns 2, 5, and 8. The remaining Columns 3, 6, and 9 are automatically verified as in the row case.
This is the proposed protocol for convincing a verifier that the numbers 1 to
9 appear exactly once in each row, each column, and each block.
The number of required cards is 117 and the number of shuffles is 16 although
we omit the breakdowns due to the space limitation. We also omit the security
proof in this extended abstract.

5

Conclusion

In this paper, we proposed a new card-based zero-knowledge proof protocol for
Sudoku. The main idea behind our proposed protocol is to make use of UNO
decks, which are commercially available over the world, and hence, they areeasy to prepare. The property that there are several UNO cards having thesame pair of a color and a number on their faces leads to reducing the numberof required shuffles. Specifically, two UNO decks and 16 shuffles are sufficientfor constructing a zero-knowledge proof protocol for a standard Sudoku puzzle.
We believe that this is efficient enough for humans to execute practically. The
proposed protocol can also be implemented with standard decks of playing cards
although it requires four decks along with two jokers of different designs.
Our techniques can be applied to a general n × n Sudoku although we omit
the details in this extended abstract.

Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku

13

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 Numbers JP21K11881 and JP23H00479.

References
1. Bultel, X., Dreier, J., Dumas, J.G., Lafourcade, P.: Physical zero-knowledge proofs
for Akari, Takuzu, Kakuro and KenKen. In: Fun with Algorithms. LIPIcs, vol. 49,
pp. 8:1–8:20. Schloss Dagstuhl, Dagstuhl, Germany (2016)
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)
3. 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)
4. Gradwohl, R., Naor, M., Pinkas, B., Rothblum, G.N.: Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles. In: Fun with
Algorithms. LNCS, vol. 4475, pp. 166–182. Springer, Berlin, Heidelberg (2007)
5. Gradwohl, R., Naor, M., Pinkas, B., Rothblum, G.N.: Cryptographic and physicalzero-knowledge proof systems for solutions of Sudoku puzzles. Theory of Computing Systems 44(2), 245–268 (2009)
6. Hanaoka, G.: Towards user-friendly cryptography. In: Paradigms in Cryptology–
Mycrypt 2016. Malicious and Exploratory Cryptology. LNCS, vol. 10311, pp. 481–
484. Springer, Cham (2017)
7. Ishikawa, R., Chida, E., Mizuki, T.: Efficient card-based protocols for generating ahidden random permutation without fixed points. In: Unconventional Computation
and Natural Computation. LNCS, vol. 9252, pp. 215–226. Springer, Cham (2015)
8. Kastner, J., Koch, A., Walzer, S., Miyahara, D., Hayashi, Y., Mizuki, T., Sone, H.:
The minimum number of cards in practical card-based protocols. In: Advances in
Cryptology—ASIACRYPT 2017. LNCS, vol. 10626, pp. 126–155. Springer, Cham(2017)
9. Koch, A., Walzer, S., Härtel, K.: Card-based cryptographic protocols using a minimal number of cards. In: Advances in Cryptology—ASIACRYPT 2015. LNCS,
vol. 9452, pp. 783–807. Springer, Berlin, Heidelberg (2015)
10. Lafourcade, P., Miyahara, D., Mizuki, T., Robert, L., Sasaki, T., Sone, H.: How toconstruct physical zero-knowledge proofs for puzzles with a “single loop” condition.
Theor. Comput. Sci. 888, 41–55 (2021)
11. Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: A physical ZKP for
Slitherlink: How to perform physical topology-preserving computation. In: Information Security Practice and Experience. LNCS, vol. 11879, pp. 135–151. Springer,
Cham (2019)12. Miyahara, D., Haneda, H., Mizuki, T.: Card-based zero-knowledge proof protocols
for graph problems and their computational model. In: Provable and Practical
Security. LNCS, vol. 13059, pp. 136–152. Springer, Cham (2021)

14

K. Tanaka and T. Mizuki

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:
Fun with Algorithms. LIPIcs, vol. 157, pp. 20:1–20:21. Schloss Dagstuhl, Dagstuhl,
Germany (2020)
14. Miyahara, D., Sasaki, T., Mizuki, T., Sone, H.: Card-based physical zero-knowledge
proof for Kakuro. IEICE Trans. Fundam. 102(9), 1072–1078 (2019)15. Mizuki, T., Shizuya, H.: A formalization of card-based cryptographic protocols via
abstract machine. Int. J. Inf. Secur. 13(1), 15–23 (2014)
16. Mizuki, T., Shizuya, H.: Computational model of card-based cryptographic protocols and its applications. IEICE Trans. Fundam. E100.A(1), 3–11 (2017)
17. Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Physical zero-knowledge
proof for Suguru puzzle. In: Stabilization, Safety, and Security of Distributed Systems. LNCS, vol. 12514, pp. 235–247. Springer, Cham (2020)
18. Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Interactive physical ZKP
for connectivity: Applications to Nurikabe and Hitori. In: Connecting with Computability. LNCS, vol. 12813, pp. 373–384. Springer, Cham (2021)
19. Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake. New Gener. Comput. 40,
149–171 (2022)
20. Robert, L., Miyahara, D., Lafourcade, P., Libralesso, L., Mizuki, T.: Physical zeroknowledge proof and NP-completeness proof of Suguru puzzle. Inf. Comput. 285,
1–14 (2022)
21. Ruangwises, S.: Two standard decks of playing cards are sufficient for a ZKP for Sudoku. In: Computing and Combinatorics. LNCS, vol. 13025, pp. 631–642. Springer,
Cham (2021)
22. Ruangwises, S.: Two standard decks of playing cards are sufficient for a ZKP for
Sudoku. New Gener. Comput. 40, 49–65 (2022)
23. Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for Numberlink. In: Funwith Algorithms. LIPIcs, vol. 157, pp. 22:1–22:11. Schloss Dagstuhl, Dagstuhl,
Germany (2020)
24. Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for Numberlink puzzle andk vertex-disjoint paths problem. New Gener. Comput. 39(1), 3–17 (2021)
25. Ruangwises, S., Itoh, T.: Physical ZKP for connected spanning subgraph: Applications to Bridges puzzle and other problems. In: Unconventional Computation andNatural Computation. pp. 149–163. Springer, Cham (2021)
26. Ruangwises, S., Itoh, T.: Physical ZKP for Makaro using a standard deck of cards.
In: Theory and Applications of Models of Computation. LNCS, vol. 13571, pp.
43–54. Springer, Cham (2022)
27. Sasaki, T., Miyahara, D., Mizuki, T., Sone, H.: Efficient card-based zero-knowledge
proof for Sudoku. Theor. Comput. Sci. 839, 135–142 (2020)
28. Sasaki, T., Mizuki, T., Sone, H.: Card-based zero-knowledge proof for Sudoku. In:
Fun with Algorithms. LIPIcs, vol. 100, pp. 29:1–29:10. Schloss Dagstuhl, Dagstuhl,
Germany (2018)