Card-based Zero-knowledge Proof Protocols forGraph Problems and Their Computational
Model⋆
Daiki Miyahara1,2 , Hiromichi Haneda1 , and Takaaki Mizuki1,2
1

Tohoku University, Sendai, Japandaiki.miyahara.q4[atmark]alumni.tohoku.ac.jp,
mizuki+lncs[atmark]tohoku.ac.jp
2
National Institute of Advanced Industrial Science and Technology, Tokyo, Japan

Abstract. Zero-Knowledge Proof (ZKP) is a cryptographic techniquethat enables a prover to convince a verifier that a given statement istrue without revealing any information other than its truth. It is known
that ZKP can be realized by physical objects such as a deck of cards;
recently, many such “card-based” ZKP protocols for pencil puzzles (suchas Sudoku and Numberlink) have been devised. In this paper, we shift
our attention to graph theory problems from pencil puzzles: We propose card-based ZKP protocols for the graph 3-coloring problem and thegraph isomorphism problem. Similar to most of the existing card-based
ZKP protocols, our two protocols have no soundness error. The proposed
protocols can be implemented without any technical knowledge, and theprinciple of zero-knowledge proof is easy to understand. In particular, ourprotocol for the graph isomorphism problem requires only three shuffles
regardless of the sizes of a pair of given graphs. In addition, to deal
with our proposed protocols more rigorously, we present a formal framework for card-based ZKP protocols which are non-interactive and haveno soundness error.
Keywords: Physical zero-knowledge proof · Card-based cryptography ·Graph 3-coloring problem · Graph isomorphism problem

1

Introduction

Suppose that there are two parties, the prover, Peggy, and the verifier, Victor.
The prover Peggy has a witness w guaranteeing that a statement x is true,
while the verifier Victor does not have it. In this case, a Zero-Knowledge Proof(ZKP) protocol, whose concept was devised by Goldwasser et al. in 1989 [9],enables Peggy to convince Victor that the statement x is true without leaking
any information about the witness w. Such a ZKP protocol must satisfy thefollowing three conditions.
⋆This paper appears in Proceedings of ProvSec 2021. The final authenticated version
is available online at https://doi.org/10.1007/978-3-030-90402-9_8.

2

H. Haneda et al.

Completeness. If x is true, then Victor accepts.
Soundness. If x is false, then no matter how Peggy behaves, Victor rejects withan overwhelming probability.
Zero-knowledge. No information about w other than the fact that x is true isleaked to Victor.
The probability that Victor accepts even though x is false is called a soundness error probability, denoted by δ. If a ZKP protocol having such a probability
δ is executed ℓ times, Victor rejects with a probability of 1 − δ ℓ . Thus, we cansatisfy the soundness condition by repeatedly running such a protocol sufficient
times.
Normally, ZKP protocols are implemented on computers and network systems, based on cryptographic primitives, such as public-key cryptography. By
contrast, there are physical ZKP protocols that do not rely on computers; for example, Gradwolh et al. [10] in 2009 invented the first physical ZKP protocol for
Sudoku using a deck of physical cards. This protocol directly verifies a solutionof a Sudoku puzzle without reducing it to other NP-complete problems, such as
3SAT. Therefore, a physical ZKP protocol is suitable for visual understandingof the concept of ZKP, as it can be performed with human hands.
It should be noted that because any Boolean circuit can be securely evaluatedby card-based cryptography (e.g., [4,14,15,19,21,30]), we can construct a physical
ZKP protocol for any 3SAT instance [20].
1.1

Existing Physical ZKP Protocols

Many physical ZKP protocols using a deck of cards have been constructed for
Nikoli’s pencil puzzles, such as Sudoku [10, 24, 29], Makaro [3], Slitherlink [16],and Numberlink [26]. These protocols are fun, and their proofs can be easily
understood because they were presented using pictures of a deck of cards (aswill be seen in Section 2).
Going back to history, Goldreich et al. [8] in 1991 proved that, for all languages in NP, there exist ZKP protocols based on cryptographic primitives.
In their paper, they also presented a physical ZKP protocol for the 3-coloring
problem using boxes having locks to clarify the presentation of their concept.
This physical ZKP protocol has a soundness error as will be seen in Section 2.3,
meaning that the protocol needs to be repeated many times.
1.2

Contribution

In this paper, we shift our attention to graph theory problems from pencil puzzles.
We propose card-based ZKP protocols for two famous graph problems: the 3coloring problem and the graph isomorphism problem. Similar to most of theexisting card-based ZKP protocols, our two protocols have no soundness error.
The proposed protocols can be implemented without any technical knowledge,
and the principle of ZKP is easy to understand. In particular, our protocol forCard-based ZKP Protocols for Graph Problems and Their Model3

the graph isomorphism problem requires only three shuffles regardless of how
large a pair of given graphs is.
In addition to constructing the two protocols, we present a formal framework
for card-based ZKP protocols which are non-interactive and have no soundness
error. Using this proposed framework, we can describe such card-based ZKP
protocols in a rigorous way.
We emphasize that this paper is an attempt to connect physical ZKP protocols (in cryptology) and graph theory. Hence, we believe that our work explores
new directions of physical ZKP protocols toward graph problems. Constructing
efficient ZKP protocols for other famous graph problems is an interesting problem, including the ones in Karp’s 21 NP-complete problems [13], as a physical
ZKP protocol for the Hamiltonian cycle problem has recently been designed [28].

2Preliminaries

In this section, we introduce notations of a deck of cards and a shuffling actionused in our proposed protocols later. We then introduce the 3-coloring problem
and the graph isomorphism problem. We also describe an existing protocol forthe 3-coloring problem [8].
2.1

A Deck of Cards

Both of our proposed protocols use a two-colored deck of cards, such as black ♣and red ♡ cards. In addition, our protocol for the graph isomorphism problem(presented in Section 4) uses numbered cards, such as 1 2 3 · · · . The backsof all these cards, denoted by ? , are indistinguishable.
2.2

Pile-scramble Shuffle

In our construction, we will use a shuffling action called the pile-scramble shuffle.
This action uniformly shuffles multiple piles of face-down cards at random. Moreprecisely, for some natural number n (≥ 2), let (pile1 , pile2 , . . . , pilen ) denote asequence of n piles of cards where each pile consists of the same number of cards.
Applying a pile-scramble shuffle to such a sequence of piles (denoted by [·| . . . |·])
results in:


···
?
?
?
?
?
?


·
·
·
···
?
?
?
?
? 
 ?
 .
···
..
..
..
..
.. 
 .
 →
,
.
.
···
.
.
. 
 .
·
·
·


···
?
?
?
 ?
?
? 
|{z}
|{z}
|{z}
|{z} |{z} · · · |{z}
pile1

pile2

pilen

pileπ−1 (1)pileπ−1 (2)pileπ−1 (n)where π ∈ Sn is a random permutation uniformly chosen from the symmetricgroup of degree n, denoted by Sn . In this case, we regard cards in the same

4

H. Haneda et al.

“column” as a pile; thus, the resulting order of cards in each pile does notchange. We also consider applying a pile-scramble shuffle “vertically,” i.e., cards
in the same row are regarded as a pile and all the piles are shuffled.
A pile-scramble shuffle was first used by Ishikawa et al. [12] in 2015. It can beeasily implemented by using rubber bands or envelopes to fix each pile of cards
and scrambles the piles to randomize the order of them. We assume that, as in
the case of usual card games, even if only one player performs a pile-scramble
shuffle, nobody (including the executor) can know the resulting order of piles.
If some players are skeptical, they may repeat the shuffling action in turn until
they are satisfied.
2.3

Known Physical Protocol for 3-coloring Problem [8]The 3-coloring problem is a decision problem to determine whether vertices ofa given undirected graph G = (V, E) can be colored with three colors suchthat every two adjacent vertices are assigned different colors. More precisely, theproblem is to determine whether there exists a mapping ϕ : V → {1, 2, 3} suchthat any edge (u, v) ∈ E satisfies ϕ(u) ̸= ϕ(v). This problem is known to be
NP-complete [6].
Goldreich et al. [8] in 1991 presented a physical ZKP protocol for the 3coloring problem. It uses boxes each having a lock with a corresponding key,such as safety boxes. Assuming that Peggy knows a correct coloring ϕ but Victor
does not, the protocol proceeds as follows.
1. Let n be the number of vertices in a given graph G. Peggy prepares n boxes
and assigns a box to each vertex.
2. Peggy assigns three random colors to {1, 2, 3} and puts the correspondingcolor for each vertex into the box without Victor’s seeing it. More precisely,
Peggy chooses a random permutation π ∈ S3 , and for every u ∈ V , Peggy
puts π(ϕ(u)) into the box corresponding to u.
3. Victor randomly chooses one edge (u, v) ∈ E and tells it to Peggy.
4. Peggy sends Victor the keys to the two boxes corresponding to u and v.
5. Victor opens the two boxes using the keys received. If they contain different
colors, then Victor continues to the next iteration; otherwise, Victor rejects.
This protocol satisfies the three conditions required for a ZKP protocol. If
Peggy has a correct mapping ϕ, then Peggy can always convince Victor because
the two boxes corresponding to the two adjacent vertices chosen by Victor nevercontain the same color, i.e., π(ϕ(u)) ̸= π(ϕ(v)). If Peggy does not have ϕ, thenVictor rejects with a probability of at least 1/m, where m is the number of edges
in the given graph G, i.e., this protocol has a soundness error. By repeating thisprotocol ℓ times, Victor can detect such a malicious prover Peggy with a proba1 ℓ) . Since Peggy discloses to Victor only the randomly assigned
bility of 1 − (1 − mcolors of the two adjacent vertices, Victor cannot obtain more information than
the fact that the two vertices are colored with different colors.

Card-based ZKP Protocols for Graph Problems and Their Model

2.4

5

Graph Isomorphism Problem

The graph isomorphism problem is a decision problem to determine whether two
given undirected graphs are isomorphic. More specifically, given two graphs G1 =(V1 , E1 ) and G2 = (V2 , E2 ), the problem is to determine whether there exists a
permutation π : V1 → V2 such that (u, v) ∈ E1 if and only if (π(u), π(v)) ∈ E2 .
It has been believed that the graph isomorphism problem is neither in P nor
NP-complete. A quasi-polynomial time algorithm has been reported by Babai [1,11].

3

Card-based ZKP for 3-coloring Problem

In this section, we construct a physical ZKP protocol for the 3-coloring problem
with no soundness error. As in the existing protocol [8] introduced in Section 2.3,
our proposed protocol enables the prover, Peggy, to convince the verifier, Victor,
that, for a given undirected graph G = (V, E), Peggy has a mapping ϕ : V →{1, 2, 3} such that any edge (u, v) ∈ E satisfies ϕ(u) ̸= ϕ(v) without revealing
any information about ϕ.
In our protocol, Peggy first places sequences of cards representing ϕ that
she has, and then Peggy and Victor publicly manipulate the sequences for theverification. Thus, after Peggy places the sequences as input, either Peggy or
Victor (or even a third party) may manipulate the cards.
The idea behind our proposed protocol is to verify that every pair of adjacentvertices is colored with different colors one by one. Our protocol proceeds asfollows.
1. Let V = {1, 2, . . . , n}. For every vertex i ∈ {1, 2, . . . , n}, Peggy preparesa sequence of face-down cards representing ϕ(i) according to the following
encoding rule (with one red card and two black cards):3♡ ♣ ♣ = 1,

♣ ♡ ♣ = 2,

♣ ♣ ♡ = 3.

(1)

Place such n sequences vertically one by one as follows:? ? ? = ϕ(1)? ? ? = ϕ(2).
.. .. ..
. . .
? ? ? = ϕ(n)2. For every edge (i, j) ∈ E, perform the following steps. If Victor does not
reject for any edge, then Victor accepts.
3

An encoding rule representing a positive integer in this manner was first consideredby Shinagawa et al. in 2015 [31].

6

H. Haneda et al.

(a) Regarding cards in the same column as a pile, apply a pile-scramble
shuffle (horizontally) to the n sequences as follows:


?

?

 ?

 .
 ..
?

?
..
.
?

?



? ? ?

? 
? ? ?
→ . . . .
.. .. .. ..

.
?
? ? ?

Let us emphasize that anyone cannot know the resulting order after
performing a pile-scramble shuffle.4(b) Reveal all the cards of the i-th and j-th sequences. If the two sequences
represent different colors, i.e., the two red cards are revealed to be atdifferent positions, it means that ϕ(i) ̸= ϕ(j), and hence, continue theprotocol after turning over the revealed cards; otherwise, Victor rejects.
Note that information about the values of ϕ(i) and ϕ(j) does not leakbecause a pile-scramble shuffle has been applied to the sequences in theprevious step.
Let m be the number of edges in the given graph G. The number of required
cards and shuffles for this protocol is 3n and m, respectively.
We present a security proof of this protocol in Section 6.1. This proof is basedon our computational model formalized in Section 5.

4

Card-based ZKP for Graph Isomorphism Problem

In this section, we construct a card-based ZKP protocol for the graph isomorphism problem with no soundness error. Our proposed protocol enables Peggy
to convince Victor that for two given undirected graphs G1 = (V1 , E1 ) andG2 = (V2 , E2 ), Peggy has a permutation π : V1 → V2 (as a witness) such that(u, v) ∈ E1 if and only if (π(u), π(v)) ∈ E2 .
4.1

Idea

Assume that Peggy has a correct permutation π ∈ Sn where n denotes thenumber of vertices in the two given graphs G1 and G2 . Let A(G1 ) and A(G2 )denote their adjacency matrices, respectively. Then, the following equation holds
for the permutation matrix Pπ corresponding to π [7]:A(G2 ) = PπT A(G1 )Pπ ,4

One might think that the resulting order could be easily known because there are
only six possibilities. One possible implementation is to put piles of cards into a box
or ball whose inside is invisible from outside and then throw it up to randomize theorder of them (cf. [32]).

Card-based ZKP Protocols for Graph Problems and Their Model

7

where for a row vector ei in which the i-th element is 1 and the remaining ones
are 0, 1 ≤ i ≤ n, the permutation matrix Pπ is


eπ(1)


Pπ =  ...  ,eπ(n)and PπT is the transpose. From this equation, it suffices that Peggy and Victor
place sequences of face-down cards representing A(G1 ), and Peggy having πrearranges the sequences according to the permutation matrix Pπ so that theresulting sequences represent A(G2 ) (without revealing any information about
π).
4.2

Description

In our proposed protocol, Peggy first prepares a sequence of face-down cards
representing π, and then Peggy and Victor publicly manipulate the sequences
for the verification. Our protocol proceeds as follows.
1. Peggy prepares a sequence of face-down numbered cards from 1 to n
representing the inverse permutation π −1 ∈ Sn (that she knows as a witness)according to the following encoding:?
? ··· ?
|{z} |{z}|{z}π(1) π(2)[π −1 ].

π(n)This sequence is called the sequence [π −1 ] where the parentheses indicatethat all cards in the sequence are face-down.
2. Let ♣ represent 0 and ♡ represent 1. According to this encoding, placesequences of face-down cards representing the n × n adjacency matrix of
G1 , namely A(G1 ). For example, the following 4 × 4 adjacency matrix isrepresented using sequences of cards as follows:♣ ♡ ♡ ♣
0110
1 0 1 1♡ ♣ ♡ ♡

1 1 0 0 → ♡ ♡ ♣ ♣ .
0100♣ ♡ ♣ ♣
Then, place the sequence of [π −1 ] that Peggy prepared and a sequence of
the identity permutation [id] consisting of 1 2 · · · n (in this order) on theleft side of the matrix [A(G1 )] vertically, as follows:
?
?
?
?
..
..
.
.
?
?


[id] π −1? ··· ?
? ··· ?
.. . . ..
. .
.
? ··· ?
[A(G1 )].

8

H. Haneda et al.

Note that the sequence [id] represents the position of each card in the sequence [π −1 ].
3. Regarding the cards in the same row as a pile, apply a pile-scramble shuffle
to the piles as follows:
?
..
.
?

?
..
.

? ··· ?
.. . . ..
. .
.
···
?
?

?
 −1 
[id] π[A(G1 )]?
?
? ··· ?
..
..
.. . .
.
. ..
.
.
.
→
,
?
?
? ··· ?
 −1   T
[r] rπPr A(G1 )where r ∈ Sn is a random permutation generated by applying a pile-scramble
shuffle.
4. Reveal the sequence [rπ −1 ] to obtain the information about rπ −1 . Transformthe matrix [PrT A(G1 )] to [PπT A(G1 )] by sorting the rows of the matrix inascending order according to rπ −1 :?
?
? ··· ?
? ··· ?
..
..
.. . .
..
.. . .
.
. .
. ..
.
.
.
.
→
.
?
?
? ··· ?
? ··· ?
 −1   T
 T[r] rπPr A(G1 )Pπ A(G1 )5. Turn over the sequence revealed in the previous step. Then, regarding cards
in the same row as a pile, apply a pile-scramble shuffle to the sequences [r]and [rπ −1 ] as follows:
?
..
.

?
..
.

?
?
..
..
.
.
→
,
?
?


?
?
[r′ r] r′ rπ −1
 −1 
[r] rπwhere r′ ∈ Sn is a random permutation generated by applying a pilescramble shuffle.
6. Reveal the sequence [r′ r]. Sort the sequence [r′ rπ −1 ] in ascending orderaccording to r′ r. This sorting applies the inverse permutation (r′ r)−1 tothe sequence [r′ rπ −1 ], and hence, the sequence [r′ rπ −1 ] becomes a sequence[π −1 ]:
?
?
?
..
..
..
.
.
.
→
.
?
?
?


 −1 
[r′ r] r′ rπ −1
πCard-based ZKP Protocols for Graph Problems and Their Model

9

7. Horizontally place the sequence [π −1 ] above the matrix [PπT A(G1 )] as follows:
? · · · ? π −1
? ··· ?
 .
.. . . ..  T. . Pπ A(G1 ).
? ··· ?
8. Regarding the cards in the same column as a pile, apply a pile-scramble
shuffle to the piles:



 

? ... ?
? · · · ? r′′ π −1
π −1
 ? ··· ?   → ?. ·.· · ?. 
 .. . .
.. T.. . . .. P T A(G )P ′′  ,
P
A(G
)
 .

1
. .
π
1
r
π
? ··· ?
? ··· ?
where r′′ ∈ Sn is a random permutation generated by applying a pilescramble shuffle.
9. Reveal the sequence [r′′ π −1 ]. Sort the columns of the matrix [PπT A(G1 )Pr′′ ]in ascending order according to r′′ π −1 to transform the matrix to [PπT A(G1 )Pπ ]:? · · · ? r′′ π −1
? ··· ?
. .
. ? ··· ?
 → .. . . .. PπT A(G1 )Pπ .
.. . . ..  T. . Pπ A(G1 )Pr′′.
? ··· ?
? ··· ?
10. Reveal all the cards of the matrix [PπT A(G1 )Pπ ]. If they represent the adjacency matrix of G2 , then Victor accepts; otherwise, Victor rejects.
Let m be the number of edges in the given graphs. The total number ofrequired cards is n2 + 2n, because 2m ♡ s and (n2 − 2m) ♣ s are used for
representing the adjacency matrix of G1 , and 2n numbered cards are used forthe sequences of [π −1 ] and [id]. The number of required shuffles is three, whichis constant regardless of the size of a pair of given graphs.
We present a security proof of this protocol in Section 6.2.

5

Basic Formalization of Card-based ZKP Protocols

In this section, we give a formalization of card-based ZKP protocols to deal with
our proposed protocols more rigorously.
Remember that our two protocols presented in Sections 3 and 4 are noninteractive: After the prover, Peggy, places a hidden sequence of face-down cards
at the beginning of each of the protocols according to a witness (that only
Peggy knows), the protocol can be executed by anyone publicly; for example,
it suffices that Peggy does every action while the verifier, Victor, watches all
behaviors of Peggy. Note that most of the existing ZKP protocols for pencil
puzzles (e.g. [3, 17, 22, 26, 27, 29]) are also non-interactive.
Thus, this section begins with clarifying the relationship between a witness
and a hidden sequence of cards.

10

5.1

H. Haneda et al.

Witness Subsequence

Let L ⊆ Σ ∗ be a language that captures a decision problem (such as the 3coloring problem and graph isomorphism problem), where Σ is an alphabet. In
our setting, Peggy and Victor are given a problem instance x ∈ L such that only
Peggy knows a witness w of the instance x; w being a witness of x means that,given a pair (x, w), everyone (including Peggy and Victor) can easily confirm
that x ∈ L (say, it can be computed in polynomial time).
For example, given an instance of the graph isomorphism problem, a permutation π which transforms one graph into the other graph serves a witness. As
seen in Section 4, Peggy who knows the permutation π is supposed to privately
arrange a sequence of face-down cards encoding π:?
? ··· ?
|{z} |{z}|{z}π(1) π(2)[π −1 ].

π(n)Therefore, in general, Peggy and Victor must agree upon a correspondence between a witness and a sequence of cards; we call such a sequence of cards awitness subsequence.
Fixing a language L, for an instance x ∈ L, we denote by Wx the set of all
witnesses of x. If Peggy knows a witness w ∈ Wx and she is honest, she should
place a witness subsequence correctly (with all cards’ faces down); we call it acorrect witness subsequence. If Peggy does not know any witness, she may place a‘wrong’ sequence of cards that follows the ‘format’ at least; we say a sequence ofcards is a legal witness subsequence if there exist an instance y ∈ L and a witness
w′ ∈ Wy such that the sequence corresponds to w′ . If Peggy is malicious, she
may place a random sequence of cards; we call any witness sequence which is
not legal an illegal witness subsequence.
Let us consider the case where x ∈/ L. If an instance x is clearly outside of L
(say, the numbers of edges of G1 and G2 are different), Victor would not agreewith executing any protocol; therefore, for such an instance, we do not have toconstruct a protocol. On the other hand, there are instances x ∈/ L for which wehave to construct protocols; define L̆ ⊆ Σ ∗ − L as
L̆ = {x ∈/ L | Victor cannot determine if x ∈ L}.
If Peggy is malicious, she may present an instance x ∈ L̆ to Victor, and placesome subsequence to run a protocol (although there is no witness). We call sucha subsequence an illegal witness subsequence as well.
Consequently, we are supposed to construct a protocol for every instance in
L ∪ L̆.
5.2

Input to Protocol

As seen above, at the beginning of a protocol, Peggy is supposed to prepare
a witness subsequence. In addition to the witness subsequence, we need somehelping cards; for example, our protocol for the graph isomorphism (presented in

Card-based ZKP Protocols for Graph Problems and Their Model

11

Section 4) uses n2 black ♣ or red ♡ cards as well as n numbered cards. These
helping cards are placed with their faces up at the beginning of the protocol.
As mentioned, if Peggy is malicious, she may place an illegal witness subsequence. To this end, she may prepare some number of cards stealthily and use
them to arrange such an illegal subsequence. Therefore, we have to take into
account such stealthy cards (owned by Peggy). Therefore, in addition to thewitness subsequence and helping cards, we consider stealthy cards: That is, we
assume that every input to a protocol consists of these three parts, and that adeck D to consider accommodates all these cards.
5.3

Abstract Protocol for ZKP

A card-based protocol itself has been well formalized already [18]. We will slightly
adjust the model of protocols by mainly adding a couple of two states, as follows.
First, we review some terms. Let D be a deck containing all cards as mentioned above. We call any element c ∈ D an atomic card, ?c a face-down card,
and ?c a face-up card. Define top( uv ) = u, calltop(Γ ) = (top(α1 ), top(α2 ), · · · , top(α|D| ))a visible sequence of a sequence Γ = (α1 , α2 , . . . , α|D| ), and let VisD be the setof all visible sequences from the deck D.
Next, we consider the input to a protocol. As mentioned before, the input
consists of three parts: the witness subsequence, helping cards, and stealthycards. Considering all possible input sequences, we use U to denote the set of all
such sequences.
We now consider a state of a protocol. Contrary to the conventional cardbased model, we introduce two additional states qaccept and qreject . That is, Q
is the set of states including the initial state q0 , the accepting state qaccept , andthe rejecting state qreject . When a protocol terminates with qaccept , it means that
Victor accepts an input sequence Γ ; when it terminates with qreject , it meansthat Victor rejects.
Based on these definitions and terms, a protocol is defined as follows.
Definition 1. A card-based protocol P is a 4-tuple P = (D, U, Q, A) that satisfies:– D is a deck.
– U is an input set.
– Q is a set of states containing q0 , qaccept , and qreject .
– A : (Q\{qaccept , qreject }) × VisD → Q × Action is an action function. Here,
Action is a set of all actions consisting of the followings.
• Turning over (turn, T ): This action is to turn over cards in the positions
specified by T ⊆ {1, 2, · · · , |D|}. Thus, this transforms a sequence Γ =(α1 , α2 , · · · , α|D| ) as follows:
turnT (Γ ) := (β1 , β2 , · · · , β|D| ),12

H. Haneda et al.

such that for swap( uv ) := uv ,(swap(αi )βi =αi

if i ∈ T ,otherwise.

• Permuting (perm, π): This action is applying a permutation π ∈ S|D| toa sequence of cards and transforms Γ = (α1 , α2 , . . . , α|D| ) as follows:
permπ (Γ ) := απ−1 (1) , απ−1 (2) , · · · , απ−1 (|D|) .
• Shuffling (shuf, Π, F): This action is applying a permutation chosen froma permutation set Π ⊆ S|D| according to a probability distribution F on
Π. This action transforms Γ = (α1 , α2 , · · · , α|D| ) as follows:
shuf Π,F (Γ ) := permπ (Γ ),where π ∈ Π is drawn according to F.
A protocol P = (D, U, Q, A) runs as an abstract machine: Staring from theinitial state q0 with some input Γ0 ∈ U , the state and the current sequence change
according to the output of the action function. When its state becomes qaccept
or qreject , the protocol terminates. Considering an execution of the protocol, thetuple of all sequences (Γ0 , Γ1 , · · · , Γt ) appeared from the initial state q0 to thefinal is called a sequence trace. Similarly, (top(Γ0 ), top(Γ1 ), · · · , top(Γt )) is calleda visible sequence trace.
5.4

Properties of ZKP

Based on the formalization thus far, we formally define a card-based ZKP protocol (collection) that is non-interactive and has no soundness error, as follows.
Definition 2. Let L be a language, and let x ∈ L ∪ L̆. We say that a protocol
Px = (D, U, Q, A) is compatible with the instance x if its input set U contains
every possible sequence whose prefix is a witness subsequence (corresponding toa witness w ∈ Wx ).5
Definition 3. Let L be a language. Assume that, for every instance x ∈ L ∪ L̆,
we have a protocol Px compatible with x. We call the set of all these protocols a
ZKP protocol collection for L if the following three conditions are met:
Completeness If x ∈ L and an initial sequence Γ0 ∈ U for the protocol Px contains a correct witness subsequence (corresponding to a witness w ∈ Wx ), theprotocol starting with Γ0 always terminates with the accepting state qaccept .
Soundness If x ∈ L and an initial sequence Γ0 for Px does not contain any
correct witness subsequence, the protocol starting with Γ0 always terminateswith the rejecting state qreject . If x ∈ L̆, Px always terminates with qreject .
Zero-knowledge Let x ∈ L, and consider any distribution on input set U of
the protocol Px . For any run of the protocol, the distribution of input andthat of the visible sequence trace are stochastically independent.
5

All other sequences in U start with illegal witness subsequences.

Card-based ZKP Protocols for Graph Problems and Their Model

613

Proof of ZKP Properties for Our Protocols

In this section, we prove the completeness, soundness, and zero-knowledge of our
proposed protocols based on the formalization presented in Section 5.
6.1

3-coloring Problem

We prove that our ZKP protocol for the 3-coloring problem presented in Section 3
satisfies the three conditions.
Theorem 1 (Completeness) If the input sequence Γ0 corresponding to ϕ contains a correct witness subsequence, the protocol always terminates with the accepting state qaccept .
Proof. In Step 2(a), we apply a pile-scramble shuffle horizontally to the threepiles. Let π ∈ S3 be a random permutation generated by this pile-scramble
shuffle. Two sequences that represented ϕ(i) and ϕ(j) before applying the pilescramble shuffle become to represent πϕ(i) and πϕ(j), i.e., the positions of the red
cards in the two sequences are πϕ(i)-th and πϕ(j)-th, respectively. By revealing
the two sequences, we can know whether πϕ(i) = πϕ(j) (i.e., ϕ(i) = ϕ(j)) ornot. Therefore, the protocol always terminates with the accept state qaccept . ⊔⊓Theorem 2 (Soundness) If the input sequence Γ0 corresponding to ϕ does notcontain any correct witness subsequence, the protocol always terminates with therejecting state qreject .
Proof. We consider the case where a sequence placed in Step 1 does not contain acorrect witness subsequence. In Step 2(a), we make vertical piles by pile-scramble
shuffle. That is, the sequence is placed in such a way that ψ(u) = ψ(v) satisfied
in Step 1. When the turn operation (turn, T ) is performed in Step 2(b), it isfound that ♡ is in the same column, resulting in the rejecting state.
⊔⊓
Theorem 3 (Zero-knowledge) For any run of the protocol, the distributionof input and that of the visible sequence trace are stochastically independent.
Proof. In Step 2(b), the sequence to be turned over by the operation (turn, T )is randomly selected from the following six patterns:
1
○

2
○

3
○

♡ ♣ ♣

♡ ♣ ♣

♣ ♡ ♣

♣ ♡ ♣

♣ ♣ ♡

♡ ♣ ♣

4
○

5
○

6
○

♣ ♡ ♣

♣ ♣ ♡

♣ ♣ ♡

♣ ♣ ♡

♡ ♣ ♣

♣ ♡ ♣

Let r ∈ S3 be a uniformly randomly generated permutation. This sequenceis transformed by (perm, r). Thus, the visible sequence trace of the protocol
is uniformly distributed. Therefore, the distribution of input and the visible
sequence trace are stochastically independent.
⊔
⊓

14

6.2

H. Haneda et al.

Graph Isomorphism Problem

We prove that our ZKP protocol for the graph isomorphism problem presented
in Section 4 satisfies the three conditions.
Theorem 4 (Completeness) If the input sequence Γ0 corresponding to π contains a correct witness subsequence, the protocol always terminates with the accepting state qaccept .
Proof. As shown in Section 4.1, there exists a permutation matrix Pπ for theadjacency matrices A(G1 ) and A(G2 ) of two isomorphic graphs G1 and G2 asfollows:
A(G2 ) = PπT A(G1 )Pπ .
In Step 4, (perm, (rπ −1 )−1 ) is equal to computing PπT A(G1 ), and in Step 9,(perm, (r′′ π −1 )−1 ) is equal to computing (PπT A(G1 ))Pπ .
Therefore, the protocol always terminates with qaccept in Step 10.
⊔⊓
Theorem 5 (Soundness) If the input sequence Γ0 corresponding to ϕ does notcontains any correct witness subsequence, the protocol always terminates with therejecting state qreject .
Proof. Consider the case where a witness subsequence placed in Step 1 is notcorrect but legal. Let π ′ be a permutation corresponding to that witness subsequence. The card sequences in Steps 3, 4, 8, and 9 is transformed by (perm, π ′ ).
As shown in Section 4.1, if the permutation matrix Pπ′ corresponding to π isused, it is transformed into a sequence corresponding to the graph G′2 insteadof the graph G2 such that
A(G′2 ) = PπT′ A(G1 )Pπ′ .
Thus, when (turn, T ) is performed in Step 10, the sequence is different from thatof the adjacency matrix in G2 , resulting in the rejecting state. Next, consider
the case where a sequence corresponding to an illegal witness subsequence isplaced. In this case, when (turn, T ) is performed in Step 10, it is found that thesequence does not follow the format of the sequence, resulting in the rejecting
state as well.
⊔⊓
Theorem 6 (Zero-knowledge) For any run of the protocol, the distributionof input and that of the visible sequence trace are stochastically independent.
Proof. As seen in Section 2.2, pile-scramble shuffles are applied so that random permutations r, r′ , r′′ are generated. The sequence in Steps 3, 5, and 8 istransformed by (perm,r), (perm,r’), and (perm,r”), respectively. Thus, the visible
sequence trace of the protocol is uniformly distributed. Therefore, the distribution of input and the visible sequence trace are stochastically independent. ⊔⊓Card-based ZKP Protocols for Graph Problems and Their Model

715

Conclusion

In this paper, we proposed physical ZKP protocols using a deck of cards forthe two major graph problems. Our protocols have no soundness error and they
are easy to implement. In particular, it is interesting to note that our ZKP
protocol for the graph isomorphism problem requires only three shuffles. Similar
to the proposed protocol, we believe that we can propose a card-based ZKP
with no soundness error for other graph problems. In addition, we constructeda rigorous definition of a card-based ZKP protocol that is non-interactive andwith no soundness error.
As future work, we are interested in the subgraph isomorphism problem6 andin analyzing computation classes in more details. Furthermore, formalizing interactive card-based ZKP protocols (e.g., [2, 5, 16, 23]) is an important future task.
In addition, investigating the relationship between our model and the standard
definitions of ZKP in details will be expected.

Acknowledgements
We thank the anonymous referees, whose comments have helped us improve
the presentation of the paper. We would like to thank Hideaki Sone for hiscooperation in preparing a Japanese draft version at an earlier stage of thiswork. We would also like to thank Kazumasa Shinagawa for his idea improving a
protocol for the 3-coloring problem. The first author is grateful to Haruka Mizuta
for helpful discussions at the beginning of this work. This work was supported
in part by JSPS KAKENHI Grant Numbers JP19J21153 and JP21K11881.

References
1. Babai, L.: Graph isomorphism in quasipolynomial time. In: ACM Symposium on
Theory of Computing. pp. 684–697. STOC ’16, ACM, New York (2016), https://doi.org/10.1145/2897518.2897542
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 with Algorithms. LIPIcs, vol. 49, pp. 8:1–8:20. Schloss Dagstuhl, Dagstuhl(2016), https://doi.org/10.4230/LIPIcs.FUN.2016.8
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.) Stabilization, Safety, and Security of Distributed
Systems. LNCS, vol. 11201, pp. 111–125. Springer, Cham (2018), https://doi.
org/10.1007/978-3-030-03232-6_8
4. Crépeau, C., Kilian, J.: Discreet solitary games. In: Stinson, D.R. (ed.) Advancesin Cryptology—CRYPTO’ 93. LNCS, vol. 773, pp. 319–330. Springer, Berlin, Heidelberg (1994), https://doi.org/10.1007/3-540-48329-2_27
6

Very recently, Ruangwises and Itoh [25, 28] implied that a card-based ZKP protocol
for the Hamiltonian cycle problem can be constructed in a similar way to our protocol
for the graph isomorphism problem.

16

H. Haneda et al.

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. Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graphproblems. Theor. Comput. Sci. 1(3), 237–267 (1976), https://doi.org/10.1016/
0304-3975(76)90059-1
7. Godsil, C., Royle, G.F.: Algebraic Graph Theory, Graduate Texts in Mathematics,
vol. 207. Springer (2001), https://doi.org/10.1007/978-1-4613-0163-9
8. Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity
or all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 690–728(1991), https://doi.acm.org/10.1145/116825.116852
9. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive
proof systems. SIAM J. Comput. 18(1), 186–208 (1989), https://doi.org/10.
1137/0218012
10. Gradwohl, R., Naor, M., Pinkas, B., Rothblum, G.N.: Cryptographic and physicalzero-knowledge proof systems for solutions of Sudoku puzzles. Theory Comput.
Syst. 44(2), 245–268 (2009), https://doi.org/10.1007/s00224-008-9119-9
11. Grohe, M., Schweitzer, P.: The graph isomorphism problem. Commun. ACM
63(11), 128–134 (2020), https://doi.org/10.1145/3372123
12. 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
13. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E.,
Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. pp. 85–103. Springer, Boston, MA (1972), https://doi.org/10.1007/
978-1-4684-2001-2_9
14. Koch, A.: Cryptographic Protocols from Physical Assumptions. Ph.D. thesis,
Karlsruhe Institute of Technology (KIT) (2019), https://doi.org/10.5445/IR/
1000097756
15. Koch, A., Schrempp, M., Kirsten, M.: Card-based cryptography meets formal verification. New Gener. Comput. 39(1), 115–158 (2021), https://doi.org/10.1007/
s00354-020-00120-0
16. 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. (2021), https://doi.org/10.1016/j.tcs.2021.07.019, inpress
17. 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. LIPIcs,
vol. 157, pp. 20:1–20:21. Schloss Dagstuhl, Dagstuhl (2020), https://doi.org/10.
4230/LIPIcs.FUN.2021.20
18. Mizuki, T., Shizuya, H.: A formalization of card-based cryptographic protocols via
abstract machine. Int. J. Inf. Secur. 13(1), 15–23 (2014), https://doi.org/10.
1007/s10207-013-0219-4
19. Mizuki, T., Sone, H.: Six-card secure AND and four-card secure XOR. In: Deng,
X., Hopcroft, J.E., Xue, J. (eds.) Frontiers in Algorithmics. LNCS, vol. 5598,
pp. 358–369. Springer, Berlin, Heidelberg (2009), https://doi.org/10.1007/
978-3-642-02270-8_36

Card-based ZKP Protocols for Graph Problems and Their Model

17

20. Niemi, V., Renvall, A.: Secure multiparty computations without computers.
Theor. Comput. Sci. 191(1–2), 173–183 (1998), https://doi.org/10.1016/
S0304-3975(97)00107-2
21. Ono, H., Manabe, Y.: Card-based cryptographic logical computations using private
operations. New Gener. Comput. 39(1), 19–40 (2021), https://doi.org/10.1007/
s00354-020-00113-z
22. Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Physical zero-knowledge
proof for Suguru puzzle. In: Devismes, S., Mittal, N. (eds.) Stabilization, Safety,
and Security of Distributed Systems. LNCS, vol. 11891, pp. 235–247. Springer,
Cham (2020), https://doi.org/10.1007/978-3-030-64348-5_19
23. Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Interactive physical ZKP
for connectivity: Applications to Nurikabe and Hitori. In: De Mol, L., Weiermann, A., Manea, F., Fernández-Duque, D. (eds.) Connecting with Computability. LNCS, vol. 12813, pp. 373–384. Springer, Cham (2021), https://doi.org/10.
1007/978-3-030-80049-9_37
24. Ruangwises, S.: Two standard decks of playing cards are sufficient for a ZKP
for Sudoku. In: Computing and Combinatorics. LNCS, Springer, Cham (2021), toappear
25. Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for connected spanning subgraph problem and Bridges puzzle (2020), https://arxiv.org/abs/2011.
02313
26. Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for Numberlink puzzle
and k vertex-disjoint paths problem. New Gener. Comput. 39(1), 3–17 (2021),
https://doi.org/10.1007/s00354-020-00114-y
27. Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for Ripple Effect. In: Hong,
S.H., Nandy, S.C., Uehara, R. (eds.) WALCOM: Algorithms and Computation.
LNCS, vol. 12635, pp. 296–307. Springer, Cham (2021), https://doi.org/10.
1007/978-3-030-68211-8_24
28. Ruangwises, S., Itoh, T.: Physical ZKP for connected spanning subgraph: Applications to Bridges puzzle and other problems. In: Unconventional Computation andNatural Computation. LNCS, Springer, Cham (2021), to appear
29. 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
30. Shinagawa, K.: On the Construction of Easy to Perform Card-Based Protocols.
Ph.D. thesis, Tokyo Institute of Technology (2020)
31. Shinagawa, K., Mizuki, T., Schuldt, J.C.N., Nuida, K., Kanayama, N., Nishide, T.,
Hanaoka, G., Okamoto, E.: Multi-party computation with small shuffle complexity
using regular polygon cards. In: Au, M.H., Miyaji, A. (eds.) Provable Security.
LNCS, vol. 9451, pp. 127–146. Springer, Cham (2015), https://doi.org/10.1007/
978-3-319-26059-4_7
32. Ueda, I., Miyahara, D., Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: Secure implementations of a random bisection cut. Int. J. Inf. Secur. 19(4), 445–452(2020), https://doi.org/10.1007/s10207-019-00463-w