Six-Card Finite-Runtime XOR Protocol with Only Random Cut
Kodai Toyoda

Daiki Miyahara

Graduate School of Information Sciences, Tohoku
University
Sendai, Japan

Graduate School of Information Sciences, Tohoku
University
National Institute of Advanced Industrial Science andTechnology
Sendai, Japan

Takaaki Mizuki

Hideaki Sone

Cyberscience Center, Tohoku University
Sendai, Japan

Cyberscience Center, Tohoku University
Sendai, Japan

ABSTRACT

1.1

Executing a card-based cryptographic protocol is an attractive way
to perform secure multiparty computation (MPC) with a deck ofphysical cards. Crèpeau and Kilian at CRYPTO 1993 proposed cardbased AND and XOR protocols that can deal with a logical conjunction and exclusive-or of variables. Their protocols use a familiar
shuffling action called a random cut that can be easily implemented
by humans, while the numbers of required cards and shuffles are
not small enough to be efficient and the protocols are Las Vegas algorithms, i.e., they are not finite-runtime. Several researchers have
improved upon the protocols for a quarter of a century. Eventually,
there are many AND protocols in the literature, some of which
are quite efficient and practical to execute. By contrast, there are
only three XOR protocols including the Crèpeau–Kilian protocol
mentioned above. In this paper, we design an efficient XOR protocol
using only random cuts; the numbers of required cards and shuffles
are six and two (which is fixed), respectively. Our proposed XOR
protocol is the first construction of a finite-runtime XOR protocol
if we restrict ourselves to use only random cuts.

Most card-based protocols use a two-colored deck of cards, namely
red ♥ and black ♣ cards having identical backs ? . To manipulate Boolean values, we use the following encoding rule:

CCS CONCEPTS• Security and privacy → Cryptography.

KEYWORDS
Secure multiparty computation; Card-based cryptography; Deck ofcards
ACM Reference Format:
Kodai Toyoda, Daiki Miyahara, Takaaki Mizuki, and Hideaki Sone. 2020.
Six-Card Finite-Runtime XOR Protocol with Only Random Cut. In 7th ACM
ASIA Public-Key Cryptography Workshop (APKC’20), October 6, 2020, Taipei,
Taiwan. ACM, New York, NY, USA, 7 pages. https://doi.org/10.1145/3384940.
3388961

1

INTRODUCTION

Executing a card-based cryptographic protocol is an attractive way
to perform secure multiparty computation (MPC) with a deck ofphysical cards. Since den Boer [3] produced the “five-card trick” in
1989, many card-based protocols have been invented.
© 2020 Copyright held by the authors. Publication rights licensed to ACM.
This is the author’s version of the work. It is posted here for your personal use.
Not for redistribution. The definitive Version of Record was published in 7th ACM
ASIA Public-Key Cryptography Workshop (APKC’20), October 6, 2020, Taipei, Taiwan,
https://doi.org/10.1145/3384940.3388961.

Card-Based AND and XOR Protocols♣ ♥ = 0,♥ ♣ = 1.

(1)

According to the above encoding rule, a player having their private
bit 𝑥 ∈ {0, 1} can commit 𝑥 by putting two face-down cards on atable:? ? .
| {z }𝑥

We call such a pair of face-down cards a commitment to 𝑥.
Given two commitments to 𝑎, 𝑏 ∈ {0, 1} (along with six helping
cards1 ), the Crèpeau–Kilian AND protocol [2] outputs a commitment to 𝑎 ∧ 𝑏 without revealing any information about the valuesof 𝑎 and 𝑏:? ? ? ? ♣ ♥ ♠ ♠ ♦ ♦ → ··· → ? ? .
| {z } | {z }| {z }𝑎𝑏

𝑎∧𝑏

Since the output value is derived as a commitment, it can be used
as an input commitment for another computation. The drawback of
the protocol is that the numbers of required cards and shuffles are
not small enough to be efficient and it is a Las Vegas algorithm, i.e.,
the number of required shuffles is only expectedly finite. Several
researchers have improved upon the protocol for a quarter of acentury. Eventually, there are many AND protocols as shown in
Table 1, some of which are quite efficient and practical to execute.
On the other hand, another important elementary computation
is XOR (exclusive-or). As for XOR, Crèpeau and Kilian [2] also
proposed an XOR protocol with 14 cards by modifying their AND
protocol:? ? ? ? ♣ ♣ ♣ ♥ ♥ ♥ ♠ ♠ ♦ ♦ →| {z } | {z }𝑎𝑏··· → ? ? .
| {z }𝑎 ⊕𝑏
1 The Crèpeau–Kilian AND protocol uses a four-colored deck of cards.

Table 1: The existing card-based AND protocols, where “RC” means the random cut and “RBC” means the random bisection
cut.

Crépeau–Kilian [2]Niemi–Renvall [11]Stiglic [12]Mizuki–Sone [9]Abe et al. [1]Five-card KWH [6]Four-card KWH [6]#Colors
4
2
2
2
2
2
2

#Cards
10
12
8
6
5
5
4

That is, it uses 14 cards of four colors and ten shuffles on average.
The shuffle their protocol uses is a familiar shuffling action called arandom cut (which will be explained in Section 2).
To reduce the number of required cards and shuffles, Mizuki,
Uchiike, and Sone [10] in 2006 proposed a Las Vegas XOR protocol
with ten cards, improving upon the Crèpeau–Kilian protocol:? ? ? ?
| {z } | {z }𝑎♣ ♣ ♣ ♥ ♥ ♥𝑏→ ··· → ? ? .
| {z }𝑎 ⊕𝑏

That is, it uses ten cards of two colors and seven shuffles (randomcuts) on average. We will briefly introduce the protocol in Section 2.
Three years after that, Mizuki and Sone [9] in 2009 proposed anefficient finite-runtime XOR protocol that requires only four cards
and one shuffle.
Thus, in contrast to AND protocols (as shown in Table 1), there
are only three XOR protocols including the Crèpeau–Kilian protocol
as shown in Table 2.2

1.2

Contribution

See Table 2 again. The Mizuki–Sone XOR protocols [9] is the mostefficient one with respect to the numbers of required cards andshuffles. Their protocol uses a shuffling action called a random
bisection cut (not a random cut) that bisects a sequence of cards
and then shuffles the two halves. A random bisection cut can be
implemented securely by using additional tools [13]. Therefore,
the random cut is better than the random bisection cut in terms ofeasy implementation. However, we note that there exists no finiteruntime XOR protocol using only random cuts, as known from
Table 2. This means that showing the possibility or impossibility forfinding such a protocol remains a challenging task in the researcharea of card-based protocols. It should be noted that in 2017 Kochand Walzer [5] proposed actively secure protocols depending only
on random cuts and they implied that finding new protocols using
only random cuts is an interesting open challenge.
In this paper, we affirmatively answer the above question. Thatis, we give a finite-runtime XOR protocol using only random cuts.
See the bottom row in Table 2. Our proposed protocol requires six
cards (i.e., two input commitments, a helping black card, and a red
2 In

2015 Koch, Walzer, and Härtel [6] presented a general protocol for any
𝑛 -ary Boolean function with 2𝑛 cards. This implies the existence of a secure
XOR protocol without any additional card using a non-practical shuffle, namely(shuf, { (2 3), (1 2), (3 4), (1 3 4 2) }), although it needs to restart with a probabilityof 3/4.

#Shuf.
8 (exp.)7.5 (exp.)
2 (exp.)1
7 (exp.)14/3 (exp.)
8 (exp.)

RuntimeLas Vegas
Las Vegas
Las Vegas
finiteLas Vegas
finiteLas Vegas

Type of shuf.
RC
RC
RC
RBC
RC & RBC
not practical
not practicalcard):? ? ? ? ♣ ♥ → ··· → ? ? .
| {z } | {z }| {z }𝑎𝑎 ⊕𝑏𝑏

The number of required shuffles (namely, random cuts) is exactly
two (which is fixed).
We will prove the correctness and security of our proposed sixcard XOR protocol by using the KWH-tree (whose idea and notion
were invented in [6]), from which we can visually confirm statetransitions of the protocol.

1.3Outline

The remainder of this paper is organized as follows. In Section 2, we
introduce the Mizuki–Uchiike–Sone XOR protocol [10] to present
what a card-based protocol is and what a random cut is. In Section 3,
we present our six-card finite-runtime XOR protocol. In Section 4,
we prove the correctness and security of our proposed protocol
by showing its KWH-tree [6]. In Section 5, we mention the idea
behind our proposed protocol. We conclude this paper in Section 6.

2

MIZUKI–UCHIIKE–SONE XOR PROTOCOLIn this section, we introduce the Mizuki–Uchiike–Sone XOR protocol [10]; given two commitments to 𝑎, 𝑏 ∈ {0, 1} along with six
helping cards (three black and three red cards), it outputs a commitment to 𝑎 ⊕ 𝑏:
? ? ? ? ♣ ♣ ♣ ♥ ♥ ♥ → ··· → ? ? .
| {z } | {z }| {z }𝑎𝑎 ⊕𝑏𝑏

The protocol proceeds as follows.
(1) Put the ten cards as follows:? ? ? ? ♣ ♥ ♣ ♥ ♣ ♥ .
| {z } | {z }𝑎𝑏Then, turn over the face-up cards:? ? ? ? ? ? ? ? ? ? .
| {z } | {z } | {z } | {z } | {z }
𝑎

𝑏

0

0

0

Table 2: The existing card-based XOR protocols and our proposed protocol.
#Colors4
2
2
2

Crépeau–Kilian [2]Mizuki–Uchiike–Sone [10]Mizuki–Sone [9]Ours#Cards141046(2) Apply a random cut (denoted by ⟨· · · ⟩) to the rightmost four
cards:*+? ? ? ? ? ?
| {z } | {z } | {z }𝑎

? ? ? ?
| {z } | {z }

0

𝑏

0

0

𝑟

𝑟

(4) Draw the first and fifth cards without revealing them:
z}|{

z}|{

?

?

? ? ?

? ? ? ? ? .

?

?

reveal

z}|{

?

?

?

?

?

𝑎

𝑏

Then, turn over the two face-up cards:? ? ? ? ? ? .
| {z } | {z }
𝑎

𝑏

?

?

?

?

?

@
R
@
(2)

and reveal them.
(a) If the resulting sequence is ♣ ♥ or ♣ ♥ , go to Step 5.
(b) If the resulting sequence is ♣ ♣ or ♥ ♥ , return thetwo cards to the sequence (2) with their faces down. Then,go back to Step 3.
(5) Reveal the third and seventh cards:
reveal? ? ? ? ♥ ♣ .
| {z } | {z }?

Then, apply a random cut to the two drawn cards:
E
D
? ? ,

z}|{

Description(2) Rearrange the order of the sequence as follows:

𝑟

draw

In this section, we construct a six-card finite-runtime XOR protocol
using only random cuts.

Here, we give the description of our protocol.
(1) Put the two input commitments and the two helping cards
as follows:

where 𝑟 is a random bit. A random cut is to cyclically shifts
the sequence of cards at random without changing its order.
Note that a random cut can be easily implemented withhuman hands so that nobody knows the offset [14].
(3) Apply two random cuts as follows:DE DE? ? ? ?
? ? ? ?
? ? .
| {z }

draw

Type of shuf.
RC
RC
RBC
RC

OUR XOR PROTOCOL

3.1? ? ? ? ? ? ? ? ? ? ,| {z } | {z } | {z } | {z } | {z }𝑏3RuntimeLas Vegas
Las Vegas
finitefinite→0𝑎#Shuf.
10 (exp.)
7 (exp.)
1
2

?

?

?

?

?

? .

(3) Apply a random cut to the sequence of six cards:
ED→ ? ? ? ? ? ? .
? ? ? ? ? ?
(4) Reveal the first and the third cards:
revealreveal

z}|{

z}|{

?

?

?

? ? ? .

(a) If ♣ ♣ appears, then turn them face down:♣ ? ♣ ? ? ? → ? ? ? ? ? ? ,? ? ? .

(a) If the resulting sequence is ♣ ♥ or ♣ ♥ (which implies𝑎 ⊕ 𝑏 ⊕ 0 ⊕ 𝑟 (= 𝑎 ⊕ 𝑏 ⊕ 𝑟 ) = 0), the rightmost two cards(i.e., the commitment to 𝑟 ) form the output 𝑎 ⊕ 𝑏.
(b) If the resulting sequence is ♣ ♣ or ♥ ♥ , (which implies 𝑎 ⊕ 𝑏 ⊕ 0 ⊕ 𝑟 = 1), the rightmost two cards form 𝑎 ⊕ 𝑏.
Then, reverse the order of the two cards consisting of thecommitment to 𝑎 ⊕ 𝑏 to obtain a commitment to 𝑎 ⊕ 𝑏.
The numbers of required cards and shuffles for this XOR protocol
are ten and seven (which is an expected number), respectively; thisis a Las Vegas protocol because the protocol (in Step 4) has thepossibility of going back to the previous step (with a probability of
1/2). See Table 2 again.

and then rearrange the order as follows:
?

?

?

?

?

?

XXX
XXX
z
?

?

?

?

?

? .

(b) If ♥ ♥ appears, then turn them face down:♥ ? ♥ ? ? ? → ? ? ? ? ? ? ,and then rearrange the order as follows:
?

?

?

?

?

?


HH
@
@
@
H

R
@

j
R
@
R
@
9

?

?

?

?

?

? .

(c) If ♣ ♥ appears, then reveal the second card:(ii) If ♥ appears, then the fourth and second cards form acommitment to 𝑎 ⊕ 𝑏:
♣ ? ? ? ♥ ?

revealz}|{♣♥ ? ? ? .

?

HH(i) If ♣ appears, then turn over the three face-up cards:

and then rearrange the order as follows:
?

?

?

?

?

𝑎 ⊕𝑏

?

(b) If ♥ appears, then reveal the third card.
(i) If ♣ appears, then the sixth and fourth cards form acommitment to 𝑎 ⊕ 𝑏:
♥ ? ♣ ? ? ?


@
@


R
@
R
@
?

?

?

?

?

j
H

? ? .
| {z }♣ ♣ ♥ ? ? ? → ? ? ? ? ? ? ,? .

(ii) If ♥ appears, then turn over the three face-up cards:♣ ♥ ♥ ? ? ? → ? ? ? ? ? ? ,




)
?

and then rearrange the order as follows:? ? .
| {z }

?

?

?

?

?

?

𝑎 ⊕𝑏

XX
X
9 XXX

z
X
?

?

?

?

?

(ii) If ♥ appears, then the second and sixth cards form acommitment to 𝑎 ⊕ 𝑏:
♥ ? ♥ ? ? ?

? .

(d) If ♥ ♣ appears, then reveal the second card.
(i) If ♣ appears, then turn over the three face-up cards:

@
R
@

? ? .
| {z }♥ ♣ ♣ ? ? ? → ? ? ? ? ? ? ,and then rearrange the order as follows:
?

?

?

?

?

?

PP
H 
HH

P

 P

q
P
j
)

?

?

?

?

?

? .

(ii) If ♥ appears, then turn over the three face-up cards:♥ ♥ ♣ ? ? ? → ? ? ? ? ? ? ,and then rearrange the order as follows:
?

?

?

?

?

?

P
P 
H 
H
P
H
j 
q
P

)
P
?

?

?

?

?

? .

(5) Apply a random cut to the sequence of six cards:
DE→ ? ? ? ? ? ? .
? ? ? ? ? ?
(6) Reveal the first card.
(a) If ♣ appears, then reveal the fifth card:
revealz}|{♣ ? ? ?

?

? .

(i) If ♣ appears, then the second and sixth cards form acommitment to 𝑎 ⊕ 𝑏:
♣ ? ? ? ♣ ?

@
R
@





? ? .
| {z }
𝑎 ⊕𝑏





𝑎 ⊕𝑏

This is our XOR protocol. Since this protocol has no loop, it
terminates within a fixed number of shuffles (namely, random cuts),
which is exactly two. See the bottom row in Table 2 again.

3.2

Pseudocode

The following is a pseudocode for our protocol, where we definedefRC6 = {id, (1 2 3 4 5 6), (1 2 3 4 5 6) 2,(1 2 3 4 5 6) 3, (1 2 3 4 5 6) 4, (1 2 3 4 5 6) 5 },(perm, 𝜋) for a permutation 𝜋 means to permute the sequence ofcards according to 𝜋, (turn,𝑇 ) for a set of positions of cards𝑇 means
to turn over all cards whose positions are in 𝑇 , (shuf, Π) for a setof permutations Π means to apply (perm, 𝜋) such that 𝜋 is drawn
from Π uniformly, and (result, 𝑖, 𝑗) specifies output positions.
input set:n ? ? ? ? ? ?   ? ? ? ? ? ? , , , , , , , , , , , ,♥ ♣ ♥ ♣ ♥ ♣♥ ♣ ♣ ♥ ♥ ♣ ? ? ? ? ? ?   ? ? ? ? ? ? o
, , , , , , , , , , ,♣ ♥ ♥ ♣ ♥ ♣♣ ♥ ♣ ♥ ♥ ♣(perm, (4 5))(shuf, RC6 )(turn, {1, 3})
if visible seq. = (♣, ?, ♣, ?, ?, ?) then(turn, {1, 3})(perm, (2 6 5 4 3))
else if visible seq. = (♥, ?, ♥, ?, ?, ?) then(turn, {1, 3})(perm, (1 2 4 5 6))else if visible seq. = (♣, ?, ♥, ?, ?, ?) then(turn, {2})if visible seq. = (♣, ♣, ♥, ?, ?, ?) then(turn, {1, 2, 3})(perm, (3 4 5))else if visible seq. = (♣, ♥, ♥, ?, ?, ?) then(turn, {1, 2, 3})(perm, (1 6 5))else if visible seq. = (♥, ?, ♣, ?, ?, ?) then(turn, {2})if visible seq. = (♥, ♣, ♣, ?, ?, ?) then(turn, {1, 2, 3})(perm, (1 4 6 3))
else if visible seq. = (♥, ♥, ♣, ?, ?, ?) then(turn, {1, 2, 3})(perm, (1 3 6 4))(shuf, RC6 )(turn, {1})if visible seq. = (♣, ?, ?, ?, ?, ?) then(turn, {5})if visible seq. = (♣, ?, ?, ?, ♣, ?) then(result, 2, 6)
else if visible seq. = (♣, ?, ?, ?, ♥, ?) then(result, 4, 2)
else if visible seq. = (♥, ?, ?, ?, ?, ?) then(turn, {3})if visible seq. = (♥, ?, ♣, ?, ?, ?) then(result, 6, 4)
else if visible seq. = (♥, ?, ♥, ?, ?, ?) then(result, 2, 6)
In the next section, we confirm that our protocol definitively
produces a commitment to 𝑎 ⊕ 𝑏 without leaking any information
about 𝑎 and 𝑏.

4

CORRECTNESS AND SECURITY

In this section, we verify the correctness and security of the protocolpresented in Section 3.
An XOR protocol is said to be correct if, given input commitments
to 𝑥, 𝑦, it always produces a commitment to 𝑥 ⊕𝑦. We call a protocol
is secure if it leaks no information for any run of the protocol (inother words, random variables 𝐼 and 𝑉 denoting the inputs and thevisible sequence trace, respectively, are stochastically independent,
where the visible sequence trace means what can be observed on thetable). See [6–8] for the more formal definitions based on abstract
machine and information theory.
To confirm that our protocol is correct and secure, we makeuse of the KWH-tree, which is a beautiful tool developed by Koch,
Walzer, and Härtel [6]. That is, if one is able to write a KWH-treesatisfying some properties for a protocol, then it automatically
implies that the protocol is correct and secure; see [4, 6, 8] for thedetails.
We describe the KWH-tree of our proposed protocol in Figure 1.
In this figure, we call each box a state. The first state (box) in Figure 1

Table 3: Possible sequences of six cards divided into four
equivalent classes, based on cyclic rotations.
(A)(♥♣♥♣♥♣)(♣♥♣♥♣♥)(B)(♥♥♥♣♣♣)(♥♥♣♣♣♥)(♥♣♣♣♥♥)(♣♣♣♥♥♥)(♣♣♥♥♥♣)(♣♥♥♥♣♣)(C)(♥♥♣♥♣♣)(♥♣♥♣♣♥)(♣♥♣♣♥♥)(♥♣♣♥♥♣)(♣♣♥♥♣♥)(♣♥♥♣♥♣)(D)(♥♥♣♣♥♣)(♥♣♣♥♣♥)(♣♣♥♣♥♥)(♣♥♣♥♥♣)(♥♣♥♥♣♣)(♣♥♥♣♣♥)

corresponds to an initial sequence, consisting of two input commitments and two helping cards; 𝑋 00, 𝑋 01, 𝑋 10 , and 𝑋 11 represent theprobabilities of(𝑎, 𝑏) = (0, 0), (𝑎, 𝑏) = (0, 1), (𝑎, 𝑏) = (1, 0), and (𝑎, 𝑏) = (1, 1),
respectively. A polynomial annotating a card sequence in a state,such as 1/6𝑋 00 , represents the conditional probability that the current sequence is the one next to the polynomial, given the visible
sequence trace observed so far on the table. From the four states(boxes) at the bottom, one can see that a commitment to 𝑎 ⊕ 𝑏 isdefinitively obtained. Furthermore, in each state, the sum of all
polynomials is equal to 𝑋 00 + 𝑋 01 + 𝑋 10 + 𝑋 11 , implying that no
information about 𝑎 and 𝑏 leaks, i.e., the inputs and visible sequence
trace are stochastically independent. It should be noted that whena turn action is applied, for each possible visible sequence, there isa constant 𝑐 such that its probability is 𝑐 (𝑋 00 + 𝑋 01 + 𝑋 10 + 𝑋 11 ).
Thus, the KWH-tree in Figure 1 guarantees that our proposed
protocol is correct and secure. (As stated in Proposition 1 of [4], theKWH-tree is a witness for the correctness and security.)

5

IDEA BEHIND OUR PROTOCOLIn this section, we explain the idea behind our protocol.
As seen in Figure 1, the initial state of our protocol can be writtenas{(♥♣♥♣♥♣, 𝑋 11 ), (♥♣♣♥♥♣, 𝑋 10 ),(♣♥♥♣♥♣, 𝑋 01 ), (♣♥♣♥♥♣, 𝑋 00 )}.
To generate a commitment to 𝑎 ⊕ 𝑏, we want to “mix” 𝑋 11 and 𝑋 00
(where the result is 1 ⊕ 1 = 0 ⊕ 0 = 0) and mix 𝑋 10 and 𝑋 01 (where
the result is 1 ⊕ 0 = 0 ⊕ 1 = 1) so that we have the bottom-moststates in Figure 1, such as{(♣♣♥♥♣♥, 𝑋 11 + 𝑋 00 ), (♣♥♥♥♣♣, 𝑋 10 + 𝑋 01 )}.
Let us show how to achieve this, as below.
Note that there are 20 combinations of possible sequences ofsix cards (three red cards and three black cards). Considering thatthe random cut is a cyclic shuffling operation, let us divide thesesequences into four equivalent classes, as shown in Table 3. When arandom cut is applied to a sequence, the resulting sequence equally
likely becomes one of the sequences that belong to the same class.
For example, if we apply a random cut to a state{(♥♣♥♥♣♣, 𝑋 11 )}, 3

ὓ‗ὓ‗ὓ‗ὓ‗‗ὓὓ‗‗ὓὓ‗ὓ‗‗ὓ‗ὓὓ‗

ͳͳ
ͳͲ
Ͳͳ
ͲͲ

ሺǡሺͶͷሻሻὓ‗ὓὓ‗‗ὓ‗‗ὓὓ‗‗ὓὓὓ‗‗‗ὓ‗ὓὓ‗

ͳͳ
ͳͲ
Ͳͳ
ͲͲ

ሺǡ͸ሻὓ‗ὓὓ‗‗ ͳȀ͸ሺͳͳ ൅ͲͲሻ ὓ‗‗ὓὓ‗ ͳȀ͸ͳͲ ‗ὓὓὓ‗‗ ͳȀ͸Ͳͳ‗ὓὓ‗‗ὓ ͳȀ͸ሺͳͳ ൅ͲͲሻ ‗‗ὓὓ‗ὓ ͳȀ͸ͳͲ ὓὓὓ‗‗‗ ͳȀ͸Ͳͳὓὓ‗‗ὓ‗ ͳȀ͸ሺͳͳ ൅ͲͲሻ ‗ὓὓ‗ὓ‗ ͳȀ͸ͳͲ ὓὓ‗‗‗ὓ ͳȀ͸Ͳͳὓ‗‗ὓ‗ὓ ͳȀ͸ሺͳͳ ൅ͲͲሻ ὓὓ‗ὓ‗‗ ͳȀ͸ͳͲ ὓ‗‗‗ὓὓ ͳȀ͸Ͳͳ‗‗ὓ‗ὓὓ ͳȀ͸ሺͳͳ ൅ͲͲሻ ὓ‗ὓ‗‗ὓ ͳȀ͸ͳͲ ‗‗‗ὓὓὓ ͳȀ͸Ͳͳ‗ὓ‗ὓὓ‗ ͳȀ͸ሺͳͳ ൅ͲͲሻ ‗ὓ‗‗ὓὓ ͳȀ͸ͳͲ ‗‗ὓὓὓ‗ ͳȀ͸Ͳͳሺǡሼͳǡ͵ሽሻ ‗Ƭ‗ ‗Ƭὓ ὓƬ‗‗ὓὓ‗‗ὓ ͳȀʹሺͳͳ ൅ͲͲሻ‗‗ὓ‗ὓὓ ͳȀʹሺͳͳ ൅ͲͲሻ‗‗ὓὓ‗ὓ ͳȀʹͳͲ‗ὓὓ‗ὓ‗ ͳȀʹͳͲ‗ὓὓὓ‗‗ ͳȀʹͲͳ‗‗ὓὓὓ‗ ͳȀʹͲͳ‗ὓ‗ὓὓ‗ ͳͳ ൅ͲͲ‗ὓ‗‗ὓὓ ͳͲ‗‗‗ὓὓὓ Ͳͳὓὓ‗‗ὓ‗ ͳȀʹሺͳͳ ൅ͲͲሻὓ‗‗ὓ‗ὓ ͳȀʹሺͳͳ ൅ͲͲሻὓ‗‗ὓὓ‗ ͳȀʹͳͲὓὓ‗ὓ‗‗ ͳȀʹͳͲὓὓ‗‗‗ὓ ͳȀʹͲͳὓ‗‗‗ὓὓ ͳȀʹͲͳሺǡሼʹሽሻ‗‗ὓ‗ὓὓ ͳͳ ൅ͲͲ‗‗ὓὓ‗ὓ ͳͲ‗‗ὓὓὓ‗ Ͳͳ ‗‗ὓὓ‗‗ὓ ͳͳ ൅ͲͲ‗ὓὓ‗ὓ‗ ͳͲ‗ὓὓὓ‗‗ Ͳͳ ὓὓ‗‗ὓ‗ὓ ͳͳ ൅ͲͲὓ‗‗ὓὓ‗ ͳͲὓ‗‗‗ὓὓ Ͳͳሺǡሺͳ͸ͷሻሻሺǡሺ͵Ͷͷሻሻὓ‗ὓὓ‗‗ ͳͳ ൅ͲͲὓ‗ὓ‗‗ὓ ͳͲὓὓὓ‗‗‗ Ͳͳሺǡሼʹሽሻ ὓ ‗ ὓƬὓὓὓ‗‗ὓ‗ ͳͳ ൅ͲͲὓὓ‗ὓ‗‗ ͳͲὓὓ‗‗‗ὓ Ͳͳሺǡሺͳ͵͸Ͷሻሻሺǡሺʹ͸ͷͶ͵ሻሻሺǡሺͳʹͶͷ͸ሻሻሺǡሺͳͶ͸͵ሻሻ‗‗ὓὓ‗ὓ ͳͳ ൅ͲͲ‗‗‗ὓὓὓ ͳͲ‗‗ὓὓὓ‗ Ͳͳ‗ὓὓ‗ὓ‗ ͳͳ ൅ͲͲὓὓὓ‗‗‗ ͳͲ‗ὓὓὓ‗‗ Ͳͳሺǡ͸ሻ‗‗ὓὓ‗ὓ ͳȀ͸ሺͳͳ ൅ͲͲሻ ‗‗‗ὓὓὓ ͳȀ͸ሺͳͲ ൅Ͳͳሻ‗ὓὓ‗ὓ‗ ͳȀ͸ሺͳͳ ൅ͲͲሻ ‗‗ὓὓὓ‗ ͳȀ͸ሺͳͲ ൅Ͳͳሻὓὓ‗ὓ‗‗ ͳȀ͸ሺͳͳ ൅ͲͲሻ ‗ὓὓὓ‗‗ ͳȀ͸ሺͳͲ ൅Ͳͳሻὓ‗ὓ‗‗ὓ ͳȀ͸ሺͳͳ ൅ͲͲሻ ὓὓὓ‗‗‗ ͳȀ͸ሺͳͲ ൅Ͳͳሻ‗ὓ‗‗ὓὓ ͳȀ͸ሺͳͳ ൅ͲͲሻ ὓὓ‗‗‗ὓ ͳȀ͸ሺͳͲ ൅Ͳͳሻὓ‗‗ὓὓ‗ ͳȀ͸ሺͳͳ ൅ͲͲሻ ὓ‗‗‗ὓὓ ͳȀ͸ሺͳͲ ൅Ͳͳሻ
ሺǡሼͳሽሻ
 ὓ ‗ὓὓ‗ὓ‗‗ ͳȀ͵ሺͳͳ ൅ͲͲሻὓ‗ὓ‗‗ὓ ͳȀ͵ሺͳͳ ൅ͲͲሻὓ‗‗ὓὓ‗ ͳȀ͵ሺͳͳ ൅ͲͲሻὓὓὓ‗‗‗ ͳȀ͵ሺͳͲ ൅Ͳͳሻὓὓ‗‗‗ὓ ͳȀ͵ሺͳͲ ൅Ͳͳሻὓ‗‗‗ὓὓ ͳȀ͵ሺͳͲ ൅Ͳͳሻ‗‗ὓὓ‗ὓ ͳȀ͵ሺͳͳ ൅ͲͲሻ‗ὓὓ‗ὓ‗ ͳȀ͵ሺͳͳ ൅ͲͲሻ‗ὓ‗‗ὓὓ ͳȀ͵ሺͳͳ ൅ͲͲሻ‗‗‗ὓὓὓ ͳȀ͵ሺͳͲ ൅Ͳͳሻ‗‗ὓὓὓ‗ ͳȀ͵ሺͳͲ ൅Ͳͳሻ‗ὓὓὓ‗‗ ͳȀ͵ሺͳͲ ൅Ͳͳሻ

ሺǡሼ͵ሽሻሺǡሼͷሽሻ ‗‗‗ὓὓ‗ὓ ͳͳ ൅ͲͲ‗ὓὓὓ‗‗ ͳͲ ൅Ͳͳ
֜ሺǡʹǡ͸ሻ ὓ‗ὓὓ‗ὓ‗ ͳȀʹሺͳͳ ൅ͲͲሻ‗ὓ‗‗ὓὓ ͳȀʹሺͳͳ ൅ͲͲሻ‗‗‗ὓὓὓ ͳȀʹሺͳͲ ൅Ͳͳሻ‗‗ὓὓὓ‗ ͳȀʹሺͳͲ ൅Ͳͳሻ
֜ሺǡͶǡʹሻ ‗ὓὓ‗ὓ‗‗ ͳȀʹሺͳͳ ൅ͲͲሻὓ‗‗ὓὓ‗ ͳȀʹሺͳͳ ൅ͲͲሻὓὓ‗‗‗ὓ ͳȀʹሺͳͲ ൅Ͳͳሻὓ‗‗‗ὓὓ ͳȀʹሺͳͲ ൅Ͳͳሻ
֜ሺǡ͸ǡͶሻ ὓὓ‗ὓ‗‗ὓ ͳͳ ൅ͲͲὓὓὓ‗‗‗ ͳͲ ൅Ͳͳ
֜ሺǡʹǡ͸ሻ

Figure 1: The KWH-tree of our six-card finite-runtime XOR protocol.

the resulting state will be{(♥♥♣♣♥♣, 1/6𝑋 11 ), (♥♣♣♥♣♥, 1/6𝑋 11 ),(♣♣♥♣♥♥, 1/6𝑋 11 ), (♣♥♣♥♥♣, 1/6𝑋 11 ),(♥♣♥♥♣♣, 1/6𝑋 11 ), (♣♥♥♣♣♥, 1/6𝑋 11 )}.

ACKNOWLEDGMENTS
We thank the anonymous referees, whose comments have helped
us to improve the presentation of the paper. We would like tothank Yuta Abe for his helpful discussions and support. This work
was supported by JSPS KAKENHI Grant Numbers JP17K00001 and
JP19J21153.

For another example, if we apply a random cut to a state{(♥♣♥♥♣♣, 𝑋 11 ), (♣♥♣♥♥♣, 𝑋 00 )},the resulting state will be{(♥♥♣♣♥♣, 1/6(𝑋 11 + 𝑋 00 )), (♥♣♣♥♣♥, 1/6(𝑋 11 + 𝑋 00 )),(♣♣♥♣♥♥, 1/6(𝑋 11 + 𝑋 00 )), (♣♥♣♥♥♣, 1/6(𝑋 11 + 𝑋 00 )),(♥♣♥♥♣♣, 1/6(𝑋 11 + 𝑋 00 )), (♣♥♥♣♣♥, 1/6(𝑋 11 + 𝑋 00 ))}.
As in this second example, we are able to mix 𝑋 11 and 𝑋 00 by
a random cut, i.e., from the resulting sequence we cannot knowwhether the input is (0,0) or (1,1). Because just applying a random
cut to the initial state{(♥♣♥♣♥♣, 𝑋 11 ), (♥♣♣♥♥♣, 𝑋 10 ),(♣♥♥♣♥♣, 𝑋 01 ), (♣♥♣♥♥♣, 𝑋 00 )}cannot mix 𝑋 11 and 𝑋 00 , we first apply a permutation (4 5) sothat some of the resulting sequences after a random cut become
cyclically equivalent. Thus, 𝑋 11 and 𝑋 00 are now mixed as shownin the third state from the top in Figure 1.
Next, we want to mix 𝑋 10 and 𝑋 01 . For this, we first reveal somecards to “reduce” the number of possibilities. For example, if wereveal the first and third cards and they are both black, then the
resulting state will be{(♣♥♣♥♥♣, 𝑋 11 + 𝑋 00 ), (♣♥♣♣♥♥, 𝑋 10 ), (♣♣♣♥♥♥, 𝑋 01 )}.
Then, it suffices to apply a permutation (2 6 5 4 3) to make the lasttwo sequences belong to the same class (while keeping the first
sequence in a distinct class). In other cases as well, by applying a
permutation corresponding to each state and applying a random
cut, we can mix 𝑋 10 and 𝑋 01 as shown in the third state from thebottom in Figure 1.
Finally, we turn over two cards to obtain a commitment to 𝑎 ⊕ 𝑏.
For example, if we reveal the first and fifth cards and they are both
black, then the resulting state will be{(♣♣♥♥♣♥, 𝑋 11 + 𝑋 00 ), (♣♥♥♥♣♣, 𝑋 10 + 𝑋 01 )},and the second and sixth cards constitute a commitment to 𝑎 ⊕ 𝑏.

6

CONCLUSION

In this paper, we constructed a six-card finite-runtime XOR protocol
using only random cuts; it uses exactly only two random cuts. Thisis the first finite-runtime XOR protocol using only random cuts.
It is an interesting open problem whether there is an XOR protocol that uses only random cuts and less than six cards.
3 Note that this example never appears in any secure XOR protocol.

REFERENCES[1] Yuta Abe, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. 2018. Five-Card
AND Protocol in Committed Format Using Only Practical Shuffles. In 5th ACM
on ASIA Public-Key Cryptography Workshop (Incheon, Republic of Korea) (APKC’18). Association for Computing Machinery, New York, NY, USA, 3–8. https://doi.org/10.1145/3197507.3197510[2] Claude Crépeau and Joe Kilian. 1994. Discreet Solitary Games. In Advances in
Cryptology—CRYPTO’ 93 (LNCS), Douglas R. Stinson (Ed.), Vol. 773. Springer,
Berlin, Heidelberg, 319–330. https://doi.org/10.1007/3-540-48329-2_27[3] Bert Den Boer. 1990. More Efficient Match-Making and Satisfiability The Five
Card Trick. In Advances in Cryptology—EUROCRYPT ’89 (LNCS), Jean-Jacques
Quisquater and Joos Vandewalle (Eds.), Vol. 434. Springer, Berlin, Heidelberg,
208–217. https://doi.org/10.1007/3-540-46885-4_23[4] Julia Kastner, Alexander Koch, Stefan Walzer, Daiki Miyahara, Yu-ichi Hayashi,
Takaaki Mizuki, and Hideaki Sone. 2017. The Minimum Number of Cards inPractical Card-Based Protocols. In Advances in Cryptology—ASIACRYPT 2017
(LNCS), Tsuyoshi Takagi and Thomas Peyrin (Eds.), Vol. 10626. Springer, Cham,
126–155. https://doi.org/10.1007/978-3-319-70700-6_5[5] Alexander Koch and Stefan Walzer. 2017. Foundations for Actively Secure Cardbased Cryptography. Cryptology ePrint Archive, Report 2017/423. https://eprint.
iacr.org/2017/423.
[6] Alexander Koch, Stefan Walzer, and Kevin Härtel. 2015. Card-Based Cryptographic Protocols Using a Minimal Number of Cards. In Advances in Cryptology—
ASIACRYPT 2015 (LNCS), Tetsu Iwata and Jung Hee Cheon (Eds.), Vol. 9452.
Springer, Berlin, Heidelberg, 783–807. https://doi.org/10.1007/978-3-662-487976_32[7] Takaaki Mizuki and Hiroki Shizuya. 2014. A formalization of card-based cryptographic protocols via abstract machine. Int. J. Inf. Secur. 13, 1 (2014), 15–23.
https://doi.org/10.1007/s10207-013-0219-4[8] Takaaki Mizuki and Hiroki Shizuya. 2017. Computational Model of Card-Based
Cryptographic Protocols and Its Applications. IEICE Trans. Fundam. Electron.
Commun. Comput. Sci. E100.A, 1 (2017), 3–11. https://doi.org/10.1587/transfun.
E100.A.3[9] Takaaki Mizuki and Hideaki Sone. 2009. Six-Card Secure AND and Four-Card
Secure XOR. In Frontiers in Algorithmics (LNCS), Xiaotie Deng, John E. Hopcroft,
and Jinyun Xue (Eds.), Vol. 5598. Springer, Berlin, Heidelberg, 358–369. https://doi.org/10.1007/978-3-642-02270-8_36[10] Takaaki Mizuki, Fumishige Uchiike, and Hideaki Sone. 2006. Securely computing
XOR with 10 cards. The Australasian Journal of Combinatorics 36 (2006), 279–293.
https://ajc.maths.uq.edu.au/?page=get_volumes&volume=36[11] Valtteri Niemi and Ari Renvall. 1998. Secure multiparty computations without
computers. Theor. Comput. Sci. 191, 1–2 (1998), 173–183. https://doi.org/10.1016/
S0304-3975(97)00107-2[12] Anton Stiglic. 2001. Computations with a deck of cards. Theor. Comput. Sci. 259,
1–2 (2001), 671–678. https://doi.org/10.1016/S0304-3975(00)00409-6[13] Itaru Ueda, Daiki Miyahara, Akihiro Nishimura, Yu-ichi Hayashi, Takaaki Mizuki,
and Hideaki Sone. 2020. Secure implementations of a random bisection cut. Int.
J. Inf. Secur. 19, 4 (2020), 445–452. https://doi.org/10.1007/s10207-019-00463-w[14] Itaru Ueda, Akihiro Nishimura, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki
Sone. 2016. How to Implement a Random Bisection Cut. In Theory and Practice of
Natural Computing (LNCS), Carlos Martín-Vide, Takaaki Mizuki, and Miguel A.
Vega-Rodríguez (Eds.), Vol. 10071. Springer, Cham, 58–69. https://doi.org/10.
1007/978-3-319-49001-4_5