An Implementation of Non-Uniform Shuffle for Secure
Multi-Party Computation∗

Akihiro NishimuraYu-ichi Hayashi

Takaaki Mizuki

Graduate School ofInformation Sciences,
Tohoku University
6-3 Aramaki-Aza-Aoba,
Aoba, Sendai 980-8578,
Japan

Faculty of Engineering,Tohoku Gakuin University
1-13-1 Chuo, Tagajo,
Miyagi 985-8537, Japan

Cyberscience Center,
Tohoku University
6-3 Aramaki-Aza-Aoba,
Aoba, Sendai 980-8578,
Japan

tmpaper+cardshimw[at]gmail.tohoku-university.jp
Hideaki Sone
Cyberscience Center
Tohoku University
6-3 Aramaki-Aza-Aoba,
Aoba, Sendai 980-8578,
Japan

ABSTRACT
Card-based cryptographic protocols provide secure multi-party computation using a deck of physical cards. The most important primitive of those protocols is the shuﬄing operation, and most known
protocols rely on uniform shuﬄes (such as the random cut andrandom bisection cut) in which each possible outcome is equally
likely. However, several protocols with non-uniform shuﬄes haverecently been proposed by Koch et al. Compared to other protocols,
their protocols require fewer cards to securely produce a hidden
AND value, although implementation of the non-uniform shuﬄeappearing in their protocols remains an open problem. This paper
presents a secure implementation of their non-uniform shuﬄe. To
implement the shuﬄe, we utilize physical cases that can store pilesof cards, such as boxes and envelopes. Therefore, humans are able
to perform the non-uniform shuﬄe using these everyday objects.

Keywords
Card-based cryptographic protocols; Secure multi-party computations; Real-life hand-on cryptography

1. INTRODUCTION
Card-based cryptographic protocols provide secure multi-party
computation using a deck of physical cards. A protocol consistsof a combination of rearranging, shuﬄing, and turning-over operations for a sequence of cards along with some encoding scheme.
∗

This is the Accepted Version.

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than theauthor(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.

AsiaPKC’16, May 30-29 2016, Xi’an, China
c 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM.
⃝ISBN 978-1-4503-4286-5/16/05. . . $15.00
DOI: http://dx.doi.org/10.1145/2898420.2898425

Many protocols have been proposed to perform AND computation(e.g. [1, 2, 4, 6, 8, 12]), XOR computation (e.g. [1, 6, 7]), andany Boolean function (e.g. [9]). In particular, there has been considerable research on designing a committed AND protocol that
produces a hidden AND value. Table 1 shows some of the known
committed AND protocols. For example, on one hand, the protocol proposed in [12] requires eight cards and uses a random cut, inwhich the card sequence is randomly shifted; on the other hand, theprotocol proposed in [6] requires six cards and uses a random bisection cut, in which the card sequence is bisected into two piles thatare then randomly switched. Thus, the number of required cards
diﬀers depending on individual protocols. Specifically, shuﬄing
operations play an important role in designing eﬃcient protocols;that is, the number of required cards could be decreased by adopting other shuﬄing operations.
Actually, a four-card committed AND protocol was recently proposed by Koch et al. at Asiacrypt 2015 [3]. They succeeded in
reducing the number of cards required to securely generate a committed AND value through the use of an unconventional shuﬄe
operation, namely a non-uniform shuﬄe. In this technique, they
consider a shuﬄe operation that has a non-uniform probability distribution. However, finding a feasible implementation (for humans)of the non-uniform shuﬄe remains an open problem [3].
This paper provides a solution to the problem; i.e., we present
a secure implementation of the non-uniform shuﬄe appearing intheir protocols. To implement the shuﬄe, we use physical casesthat can store a pile of cards, such as boxes and envelopes. Therefore, it is possible for humans to perform the shuﬄe using such
everyday objects.
The remainder of this paper is organized as follows. The rest of
this section presents several notations related to card-based cryptographic protocols. Section 2 introduces the two AND protocols
proposed by Koch et al. at Asiacrypt 2015 [3]. Section 3 describes
thechniques to utilize the cases that we assume. Section 4 proposesa general description of our implementation. Section 5 explicitly
shows that the AND protocols by Koch et al. [3] can be executedby humans. Section 6 concludes our paper.

Rearrangement
By S d , we denote the symmetric group of degree d. Given a
permutation π ∈ S d for a sequence Γ = (α1 , α2 , · · · , αd ), wewrite (perm, π) to express a rearrangement operation after
which we have the resulting sequence:

Table 1: Committed AND protocol# of# of Type of Avg. #Reference colors cards shuﬄe of trials
[1]

4

10

RC

6

[8]

2

12

RC

2.5

[12]

2

8

RC

2

[6]

2

6

RBC

1

(απ−1 (1) , απ−1 (2) , · · · , απ−1 (d) ).
Consider cyclic permutation (1 3 4 2) as an example. For asequence of four face-down cards, operation (perm, (1 3 4 2))
works as

RC: Random Cut, RBC: Random Bisection Cut

?

?

?

?

?

?

?

? .

HH @



H
j @
R

1.1 Preliminary Notations
Here, we provide preliminary notations regarding card-based cryptographic protocols.
First, we assume that cards satisfy the following properties.

Shuﬄing
Given a probability distribution F on a permutation set Π ⊆S d for a sequence Γ = (α1 , α2 , · · · , αd ), we write

1. All cards of the same type (black ♣ or red ♡ ) are indistinguishable from one another.

(shuffle, Π, F )2. The back side of each card ? is the same, and hence, allface-down cards are indistinguishable from one another.

to represent a shuﬄing operation that probabilistically applies (perm, π) to Γ where π is chosen from Π according toF.

Next, the encoding scheme to handle Boolean values is defined as:

Hereafter, id denotes the identify permutation. For example,
for two commitments♣ ♡ = 0, ♡ ♣ = 1.

? ? ? ? ,| {z } | {z }(1)Given a bit x ∈ {0, 1}, when a pair of face-down cards ? ?
describes the value of x with encoding scheme (1), it is called acommitment to x and is expressed asaoperation(shuffle, {id, (1 3)(2 4)}, id 7→ 1/2, (1 3)(2 4) 7→ 1/2)

? ? .
| {z }

results in eitherx? ? ? ? or ? ? ? ?
| {z } | {z }| {z } | {z }Given commitments to a, b ∈ {0, 1}, the committed AND protocols listed in Table 1 produce their output as a commitment toa ∧ b.

aΓ = (α1 , α2 , · · · , αd )? ? ,| {z }
0which is a commitment to 0.

a

The random bisection cut is a popular shuﬄing operation,and used in many known protocols (e.g. [3, 4, 6, 9]). Anotherpopular type of uniform shuﬄe is the random cut, whichmeans cyclic shifting; for example,

represents a sequence of d cards for some d ∈ IN where αi is a facedown or face-up card, 1 ≤ i ≤ d. The operations that can be appliedin a protocol are defined below.

operation (turn, {1, 2}) results inb

The example above is a type of “uniform” shuﬄe; i.e., possible permutations id and (1 3)(2 4) are uniformly distributed.
In this case, we simply write (shuffle, {id, (1 3)(2 4)}). Generally, we write (shuffle, Π) instead of (shuffle, Π, F ) if F isa uniform distribution.

Here, we briefly introduce the computational model and the methodof describing a protocol [3, 5].
A tuple♣ ♡ ,bwhere each occurs with a probability of exactly 1/2. Such a
shuﬄing operation is called a random bisection cut [6].

1.2 Computational Model

Turning Over
Given a turn set T ⊆ {1, 2, · · · , d} for a sequence Γ = (α1 , α2 ,· · · , αd ), we write (turn, T ) to express a turning-over operation where all cards whose positions in T are turned over.
For example, given a sequence of two cardsb(shuffle, {id, (1 2 3), (1 3 2)}).
In the next section, we will describe a “non-uniform” shuﬄe.
ResultThe operation (result, i, j) implies that the i-th and j-th cards
constitute the output commitment.

2.

KOCH’S AND PROTOCOLS USING NONUNIFORM SHUFFLE

This section introduces the descriptions of the AND protocols
proposed by Koch et al [3]. They proposed two AND protocols: thefirst is a four-card Las Vegas protocol, and the second is a five-cardfinite-runtime protocol. Hereafter, we refer to the former as Koch’s
four-card AND protocol and the latter as Koch’s five-card AND
protocol; these are described in Sections 2.1 and 2.2, respectively.

and hence, it is a sort of random bisection cut although the two possible outcomes are not uniformly distributed. The former shuﬄe (2)means
12.1 Koch’s Four-Card Las Vegas AND Protocol

3

4

2

1

4

3

? ? ? ? 7→ 2/3.

Because an implementation of these shuﬄing operations has notappeared in the literature, we will provide a solution in Sections 4
and 5.

Given two commitments? ? ? ? ,| {z } | {z }a2

? ? ? ? 7→ 1/3 ,b

Koch’s four-card AND protocol produces a commitment to a ∧ b.
That is, it requires only four cards to perform a committed AND
computation. It contains a “cycle” because of the "goto" operations,and hence, it is a Las Vegas algorithm.

Koch’s Five-Card Finite-Runtime AND Protocol

Koch et al. slightly modified the four-card protocol to create afive-card finite-runtime AND protocol. Using five cards, it allows
a "break-out" of the cycle, that is, given? ? ? ? ♡ ,| {z } | {z }Koch’s four card AND protocol.
(shuffle, {id, (1 3)(2 4)})
(shuffle, {id, (2 3)})(turn, {2})if (visible seq. is ? ♣ ? ? ) then(turn, {2})(shuffle, {id, (1 3)})• (shuffle, {id, (1 2)(3 4)}, id 7→ 1/3, (1 2)(3 4) 7→ 2/3)
(turn, {4})if (visible seq. is ? ? ? ♣ ) then(result, 1, 2)
else if (visible seq. is ? ? ? ♡ ) then(turn, {4})(shuffle, {id, (1 3)})
(perm, (1 3 4 2))
goto ◦
else if (visible seq. is ? ♡ ? ? ) thenturn,{2})(shuffle, {id, (3 4)})◦ (shuffle, {id, (1 3)(2 4)}, id 7→ 1/3, (1 3)(2 4) 7→ 2/3)
(turn, {1})if (visible seq. is ♡ ? ? ? ) then(result, 2, 4)
else if (visible seq. is ♣ ? ? ? ) then(turn, {1})(shuffle, {id, (3 4)})
(perm, (1 2 4 3))
goto •ab

the protocol proceeds as follows.

As seen above, this protocol relies on two types of non-uniform
shuﬄe:(shuffle, id 7→ 1/3, (1 2)(3 4) 7→ 2/3)

2.2

Koch’s five-card AND protocol.
(turn, {5})(shuffle, {id, (1 3)(2 4)})
(shuffle, {id, (2 3)})(turn, {2})if (visible seq. is ? ♣ ? ? ? ) then(turn, {2})(shuffle, {id, (1 3)})• (perm, (1 5 2 4))(shuffle, id 7→ 2/3, (5 4 3 2 1) 7→ 1/3)
(turn, {5})if (visible seq. is ? ? ? ? ♣ ) then(result, 4, 3)
else if (visible seq. is ? ? ? ? ♡ ) then(result, 3, 1)
else if (visible seq. is ? ♡ ? ? ? ) then(turn,{2})(shuffle, {id, (3 4)})
(shuffle, id 7→ 1/3, (1 3)(2 4) 7→ 2/3)
(turn, {1})if (visible seq. is ♡ ? ? ? ? ) then(result, 2,4)
else if (visible seq. is ♣ ? ? ? ? ) then(turn, {1})(shuffle, {id, (3 4)})
(perm, (1 2 4 3))
goto •(2)
The first non-uniform shuﬄe in this protocol isand(shuffle, id 7→ 1/3, (1 3)(2 4) 7→ 2/3),

where we omit the descriptions of permutation sets {id, (1 2)(3 4)}and {id, (1 3)(2 4)}. (Hereafter, we simply write (shuffle, F ) insteadof (shuffle, Π, F ) as above if F is a non-uniform distribution.) The
latter shuﬄe (3) means, given
1

2

3

4

? ? ? ? ,we have1

2

3

4? ? ? ? 7→ 1/3 ,

3

4

1

2

? ? ? ? 7→ 2/3,

(shuffle, id 7→ 2/3, (5 4 3 2 1) 7→ 1/3).

(3)

(4)

On the other hand, the second non-uniform shuﬄe already appears
in Koch’s four card AND protocol presented in the previous subsection.
As mentioned above, finding an implementation of the non-uniform
shuﬄe remains an open problem. We will solve it in the succeeding
sections.

3.

CARD CASES FOR NON-UNIFORM SHUFFLEIn this section, we discuss how to implement a non-uniform shuffle through the use of “card cases.”

3.1 How to Utilize Cases
Nishimura et al. considered the card cases shown in Figure 1 to
implement unequal division shuﬄes [10]. We also utilize the same
type of cases to implement non-uniform shuﬄes. Each case canstore a deck of cards and has two sliding covers: an upper coverand a lower cover. We assume that the weight of a deck of cards is
negligible compared to the case.

Figure 3: Stacking the three cases

Figure 1: Card cases having two sliding covers
Figure 4: Removing the covers

Now, consider the non-uniform shuﬄe (3) appearing in Koch’s
four-card AND protocol (Section 2.1); remember that, given a sequence of four face-down cards
1

2

3

Table 2: All possibilities to confirm shuﬄe (3)4? ? ? ? ,Case sequence

Card sequence(C1 , C2 , C3 )? ? ? ?

1

we must obtain
1

2

3

4

? ? ? ? 7→ 1/3 ,

3

4

1

3

2

(C3 , C1 , C2 )? ? ? ? 7→ 2/3.

(C2 , C3 , C1 )

1

2

3

4

1. Divide the sequence into two piles: ? ? and ? ? .
2. Store the first pile in C1 , store the second pile in C3 , and leave
C2 empty, as illustrated in Figure 2.

4

3

1

4

1/3

2

1/3

? ? ? ?
3

To implement this, we use three cases, referred to as C1 , C2 , andC3 for the sake of convenience.

2

Probability

4

1

2

1/3

? ? ? ?

From Table 2, one can easily confirm that the non-uniform shuffle
1

2

3

4

? ? ? ? 7→ 1/3 ,

3

4

1

2

? ? ? ? 7→ 2/3

has been implemented.
3. Apply a “random cut” to the case sequence (C1 , C2 , C3 ); inother words, randomly shift these three cases. We call suchan operation a pile-shifting scramble.
4. Stack the three cases as illustrated in Figure 3.
5. Remove all sliding covers except for the top-most and bottommost covers simultaneously, as illustrated in Figure 4.
Then, we have a sequence of four face-down cards. Table 2 shows
all three possibilities of case sequences together with card sequences
and probabilities.

Figure 2: The first and second piles are stored in the first andthird cases, respectively.

3.2 Necessary Properties for Cases
To be used in the pile-shifting scramble, cases must have certain
properties. Thus, we assume physical cases that satisfy the following properties.
1. It is possible to store a pile of cards in a case without changing its order.
2. It is possible to eject a pile of cards from a case withoutchanging its order.
3. It is possible to eject multiple piles without changing theirorders by opening multiple cases at the same time. No information leaks will be caused by this action.
4. A number of cases that possibly contain piles of cards are indistinguishable from one another, and we cannot obtain any
information about the cards inside. (For instance, the weightof any pile of cards is negligible compared to the weight ofthe case. Hence, the weights of these cases leak no information about the internal states. Furthermore, any case containing a pile is assumed to make no sound.)We believe we can use boxes or envelopes as such cases.

4. NON-UNIFORM SHUFFLE VIA PILESHIFTING SCRAMBLE
This section proposes a general method to implement a nonuniform shuﬄe using the pile-shifting scramble.

Although the card sequence is split into two piles in each of theseexamples, we can, of course, split it into three or more piles; forinstance,
C1

C2

1

2

3

?

?

?

4.1 Idea
As seen in Section 3.1, a non-uniform shuﬄe

C3

C4
,

(shuffle, id 7→ 1/3, (1 3)(2 4) 7→ 2/3)
can be implemented by using three cases:
C1
1

C2

achieves(shuffle, id 7→ 1/4, (1 2 3) 7→ 1/4, (2 3 1) 7→ 1/2),

C3

2

3

? ?

which is a “non-uniform” random cut.
In the next subsection, we generalize this idea.

.

4

? ?

4.2
As can be easily noticed, the number of cases and the initial positions of the piles determine the probabilities. For example, if wehave five cases and store the piles as
C1

C2
1

C3

C4

C5

2

3

? ?

The Power of a Pile-Shifting Scramble

Here, we discuss the shuﬄe types that can be implemented by
the pile-shifting scramble.
Basically, the pile-shifting scramble achieves a “pile-based” random cut; i.e., if we split a sequence of d cards into k piles where
the size of the i-th pile is si , then the permutation set of the shuﬄeconsists of k permutations:

,

4

(

? ?

1 · · · s1 s1 + 1 · · · s1 + s2 · · · d − sk + 1 · · · d)−11 · · · s1 s1 + 1 · · · s1 + s2 · · · d − sk + 1 · · · d(then another type of non-uniform shuﬄe· · · sk sk + 1 · · · sk + s1 · · ·1d − sk + 1 · · · d(shuffle, id 7→ 2/5, (1 3)(2 4) 7→ 3/5)

1···d − sk−1 + 1

C3

1

2

?

? ? ? ?

3

4

5

.

Then, after a pile-shifting scramble (randomly shifting the threecases), we haveCase sequence

Card sequence(C1 , C2 , C3 )? ? ? ? ?

1

2

2

3

3

4

4

(C3 , C1 , C2 )? ? ? ? ?

(C2 , C3 , C1 )? ? ? ? ?

1

2

3

1/3
.

1

4

,

(

1

···

s2

s2 + 1· · · s2 + s3 + 1 · · · d − s1 + 1 · · · d
1· · · s1)−1.

We denote the permutation set defined above by Π(s1 ,s2 ,··· ,sk ) .
If we use exactly k cases to store k piles, we obtain a uniform
shuﬄe (shuffle, Π(s1 ,s2 ,··· ,sk ) ) i . As seen in the previous subsection,by preparing empty cases, we are able to obtain a non-uniform
shuﬄe. We now discuss a general treatment.
Assume that we want to implement a non-uniform shuﬄe(shuffle, Π(s1 ,s2 ,··· ,sk ) , F )such that the probabilities of distribution F are
p1 p2
pk, ,··· , ,q qqProbability

5

5

)−1

· · · d − sk − sk−1 + 1 · · · d − sk

s1

s1 + 1 · · · s1 + s2 s1 + s2 + 1 · · · s1 + s2 + s3 · · ·

C2

d

..
.

can be implemented.
Furthermore, the pile sizes should not necessarily be the same;for instance, consider a one-card pile and a four-card pile alongwith three cases:
C1

···

,

1/3

5

1/3

where each probability is a non-zero rational number and the greatest common divisor of pi for 1 ≤ i ≤ k is relatively prime to q. Notethatk∑pi = q.
i=1

Therefore, the non-uniform shuﬄe
1

2?

? ? ? ? 7→ 2/3 ,

3

4

5

2

3

4

5

? ? ? ?

1

? 7→ 1/3,

namelyThen, we require q cases that satisfy the properties mentioned in
Section 3.2. The cases are named C1 , C2 , · · · , Cq . The case sequence C = (C1 , C2 , · · · , Cq ) consists of C1 , C2 , · · · , Cq . The j-th
pile is stored in case Cℓ j , where 1 ≤ j ≤ k, according to the following condition:(shuffle, id 7→ 2/3, (5 4 3 2 1) 7→ 1/3)
can be implemented. Actually, this is an exact representation of
shuﬄe (4), which appears in Section 2.2.

ℓj =

j
∑

pi .

i=1
i

Such a shuﬄing operation is called a cyclic shuﬄe in [11].

This means that the first pile is stored in the p1 -th case, the second
pile is stored in the (p1 + p2 )-th case, and so on. The last pile,
namely the k-th pile, is stored in the q-th case (namely, the lastcase). The other cases are left empty.
After applying a pile-shifting scramble to case sequence C, there
are q possibilities for the case sequence; each case sequence is generated with a probability of exactly 1/q. Then, all sliding covers(except for the top-most and bottom-most covers) are removed toobtain the resulting sequence of cards.
Among the q possibilities mentioned above, there are p1 possibilities that the sequence starts with the first pile (and ends withthe k-th pile). More generally, there are p j possibilities that the sequence starts with the j-th pile for every j, 1 ≤ j ≤ k. Therefore,
the probability that the j-th pile leads the sequence is exactly p j /q,
as desired.
Thus, our implementation can be applied if the probability ofeach possible outcome is a non-zero rational number.
Theorem 1. Let s1 , s2 , · · · , sk be integers. Any shuﬄe(shuffle, Π(s1 ,s2 ,··· ,sk ) , F )5. REAL EXECUTION OF KOCH’S PROTOCOLSIn this section, we demonstrate how to practically implement
Koch’s AND protocols, which were introduced in Sections 2.1 and
2.2.
Note that, aside from non-uniform shuﬄes (2), (3), and (4), theknown protocols could be executed by humans. Therefore, our nonuniform shuﬄe implementation will complete the implementationof their AND protocols.
Because we have already shown the realization of shuﬄes (3)and (4) in Section 4.1, it suﬃces to focus on shuﬄe (2), which
results in:
1

2

3

4

2

1

4

3

? ? ? ? 7→ 2/3.

It appears that shuﬄe (2) is not a“pile-based” random cut, but it
is implemented by performing additional permutations before andafter the pile-shifting scramble. First, apply (perm, (2 3)) to thesequence
1

2

3

4

? ? ? ? .
Then, we have1

3

2Case sequence

4? ? ? ? .
Next, apply shuﬄe (3) to the sequence. Finally, apply (perm, (2 3))
to the sequence.
Table 3 confirms that shuﬄe (2) is surely implemented.

6. CONCLUSION
In this paper, we proposed a method to securely implement a
non-uniform shuﬄe. That is, we showed that a non-uniform distribution on possible shuﬄing outcomes can be generated by considering physical cases that could hold a pile of cards. As such physical cases, we can use everyday objects such as boxes and envelopes.
Therefore, we believe that humans can practically perform a nonuniform shuﬄe. Our non-uniform shuﬄe implementation can be,of course, applied to the two AND protocols designed by Koch etCard sequence
1(C1 , C2 , C3 )(C3 , C1 , C2 )(C2 , C3 , C1 )

3

2

4

after (perm,(2 3))
1

2

3? ? ? ?

? ? ? ?

2

2

4

1

3

1

4

? ? ? ?

2

2

1

3

? ? ? ?

1

4

1/3

3

? ? ? ?
4

Prob.

4

1/3

3

? ? ? ?

1/3

al. [3] (which are the first two protocols that rely on non-uniform
shuﬄes); this means that their excellent protocols can be practically
executed by humans using an actual deck of physical cards.
We hope that our implementation will motivate further researchon developing new card-based protocols using non-uniform shuffles.

7.

can be implemented by the pile-shifting scramble if every probability in F is a non-zero rational number.

? ? ? ? 7→ 1/3 ,Table 3: All possibilities to confirm shuﬄe (2)REFERENCES[1] C. Crépeau and J. Kilian. Discreet solitary games. In D. R.
Stinson, editor, Advances in Cryptology — CRYPTO ’93,
volume 773 of Lecture Notes in Computer Science, pages
319–330. Springer Berlin Heidelberg, 1994.
[2] B. den Boer. More eﬃcient match-making and satisfiability:
the five card trick. In J.-J. Quisquater and J. Vandewalle,
editors, Advances in Cryptology — EUROCRYPT ’89,
volume 434 of Lecture Notes in Computer Science, pages
208–217. Springer Berlin Heidelberg, 1990.
[3] A. Koch, S. Walzer, and K. Härtel. Card-based cryptographic
protocols using a minimal number of cards. In T. Iwata and
J. Cheon, editors, Advances in Cryptology – ASIACRYPT
2015, volume 9452 of Lecture Notes in Computer Science,
pages 783–807. Springer Berlin Heidelberg, 2015.
[4] T. Mizuki, M. Kumamoto, and H. Sone. The five-card trick
can be done with four cards. In X. Wang and K. Sako,
editors, Advances in Cryptology — ASIACRYPT 2012,
volume 7658 of Lecture Notes in Computer Science, pages
598–606. Springer Berlin Heidelberg, 2012.
[5] T. Mizuki and H. Shizuya. A formalization of card-based
cryptographic protocols via abstract machine. International
Journal of Information Security, 13(1):15–23, 2014.
[6] T. Mizuki and H. Sone. Six-card secure AND and four-card
secure XOR. In X. Deng, J. E. Hopcroft, and J. Xue, editors,
Frontiers in Algorithmics, volume 5598 of Lecture Notes in
Computer Science, pages 358–369. Springer Berlin
Heidelberg, 2009.
[7] T. Mizuki, F. Uchiike, and H. Sone. Securely computing
XOR with 10 cards. The Australasian Journal of
Combinatorics, 36:279–293, 2006.
[8] V. Niemi and A. Renvall. Secure multiparty computations
without computers. Theoretical Computer Science,
191(1–2):173–183, 1998.
[9] T. Nishida, Y. Hayashi, T. Mizuki, and H. Sone. Card-based
protocols for any boolean function. In R. Jain, S. Jain, and
F. Stephan, editors, Theory and Applications of Models ofComputation, volume 9076 of Lecture Notes in Computer
Science, pages 110–121. Springer International Publishing,
2015.
[10] A. Nishimura, T. Nishida, Y. Hayashi, T. Mizuki, and
H. Sone. Five-card secure computations using unequal
division shuﬄe. In A.-H. Dediu, L. Magdalena, andC. Martín-Vide, editors, Theory and Practice of Natural
Computing, volume 9477 of Lecture Notes in Computer
Science, pages 109–120. Springer International Publishing,
2015.
[11] K. Shinagawa, T. Mizuki, J. Schuldt, K. Nuida,
N. Kanayama, T. Nishide, G. Hanaoka, and E. Okamoto.
Multi-party computation with small shuﬄe complexity using
regular polygon cards. In M.-H. Au and A. Miyaji, editors,
Provable Security, volume 9451 of Lecture Notes in
Computer Science, pages 127–146. Springer International
Publishing, 2015.
[12] A. Stiglic. Computations with a deck of cards. TheoreticalComputer Science, 259(1–2):671–678, 2001.

Acknowledgments
We thank the anonymous referees, whose comments helped us to
improve the presentation of the paper. This work was supported by
JSPS KAKENHI Grant Number 26330001.