VOL. E100-A NO. 1
JANUARY 2017
The usage of this PDF file must comply with the IEICE Provisions
on Copyright.
The author(s) can distribute this PDF file for research andeducational (nonprofit) purposes only.
Distribution by anyone other than the author(s) is prohibited.

IEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.1 JANUARY 20173

INVITED PAPER

Special Section on Cryptography and Information Security

Computational Model of Card-Based Cryptographic Protocols and
Its Applications
Takaaki MIZUKI†a) and Hiroki SHIZUYA†† , Members

SUMMARY Card-based protocols enable us to easily perform cryptographic tasks such as secure multiparty computation using a deck of physicalcards. Since the first card-based protocol appeared in 1989, many protocols
have been designed. A protocol is usually described with a series of somewhat intuitive and verbal descriptions, such as “turn over this card,” “shuﬄethese two cards,” “apply a random cut to these five cards,” and so on. On
the other hand, a formal computational model of card-based protocols via
abstract machine was constructed in 2014. By virtue of the formalization,
card-based protocols can be treated more rigorously; for example, it enables
one to discuss the lower bounds on the number of cards required for securecomputations. In this paper, an overview of the computational model with
its applications to designing protocols and a survey of the recent progressin card-based protocols are presented.
key words: card-based protocols, card games, cryptography without computers, real-life hands-on cryptography, secure multiparty computations

1.

⇌

z}|{

? ? → ? ? → ? ?.

|{z}

|{z}

a

ā

Thus, one can easily negate a commitment while keeping its
value secret.
As another example of protocols, we here introduce
the Mizuki-Sone AND protocol [1], which receives commitments to Alice’s bit a and Bob’s bit b, and generates acommitment to a ∧ b, as follows.
1. Put a black card and a red card between the two commitments, and turn them over:? ? ♣ ♡ ? ? → ? ? ? ? ? ?.

Introduction

Card-based protocols allow cryptographic tasks, such as secure multiparty computation, to be performed easily using a
deck of physical cards. Assume two types of several cards
with faces that are either black ( ♣ ) or red ( ♡ ) and identical backs ( ? ). Using two cards of diﬀerent colors, one caneasily encode a bit value, for example,♣ ♡ = 0, ♡ ♣ = 1.

(1)

According to the above encoding (1), a player, Alice, cancommit her private bit a ∈ {0, 1} to a pair of face-down cards

? ?,

|{z}
a

which we call a commitment to bit a. Typically, a card-based
protocol receives a few commitments as its input and applies
a series of actions to produce its output.
Let us start with one of the simplest protocols, the NOT
protocol. Given a commitment to a bit a as input, the NOT
protocol swaps only the two cards constituting the commitment so that a commitment to the negation ā as output isobtained:
Manuscript received June 30, 2016.
Manuscript revised August 26, 2016.
† The author is with the Cyberscience Center, Tohoku University, Sendai-shi, 980-8578 Japan.
†† The author is with the Center for Information Technology in
Education, Tohoku University, Sendai-shi, 980-8576 Japan.
a) E-mail: tm-paper+cardieiceinv@g-mail.tohoku-university.jp
DOI: 10.1587/transfun.E100.A.3

|{z}

|{z}

a

b

|{z} |{z} |{z}a0bNote that the two face-down cards in the middle constitute a commitment to 0.
2. Rearrange the sequence of six cards:? ? ? ? ? ?
QQQs? ? ? ? ? ?.
3. Apply a random bisection cut, which means bisecting
the sequence and shuﬄing the two portions:[]? ? ? ? ? ? → ? ? ? ? ? ?.
Therefore, the resulting sequence of six cards is either
the same as the original one or a sequence, the two
halves of which have been switched with a probabilityof 1/2.
4. Rearrange the sequence of six cards:? ? ? ? ? ?

@
@

R @
@
R
+


? ? ? ? ? ?.
5. Reveal the first two cards (from the left). Then, a commitment to a ∧ b is obtained as♣ ♡ ? ? ? ? or ♡ ♣ ? ? ? ? .
|{z}
|{z}
a∧b

a∧b

This protocol produces a commitment to a ∧ b without leaking any information about a and b. We explain its correctness

Copyright © 2017 The Institute of Electronics, Information and Communication Engineers

IEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.1 JANUARY 2017

4
Table 1

Some of the existing card-based protocols.
# ofcolors◦ Committed AND protocols
Crépeau-Kilian [3]4Niemi-Renvall [4]2Stiglic [5]2Mizuki-Sone [1] (§1, 2, 4)2
Koch-Walzer-Härtel [6] (§5)
2
Koch-Walzer-Härtel [6] (§5)
2
◦ Committed XOR protocols
Crépeau-Kilian [3]4Mizuki-Uchiike-Sone [7]2Mizuki-Sone [1]2◦ Non-committed AND protocols
den Boer [2]2
Mizuki-Kumamoto-Sone [8]
2

# of
cards

Avg. #of trials

10
12
8
6
5
4

6
2.5
2
1
1
1.8

14
10
4

6
2
1

5
4

1
1

and security in Sect. 4. The protocol, which uses six cards,
is hereinafter referred to as the six-card AND protocol.
Similarly to the six-card AND protocol [1] describedabove, a protocol producing a commitment to the value ofthe AND function is called a committed AND protocol. As
shown in Table 1, several committed AND protocols as wellas committed XOR protocols have been proposed. Furthermore, as seen also in Table 1, non-committed AND protocols
have been developed. In fact, the first card-based protocol
designed by den Boer in 1989 [2] was a non-committed AND
protocol; given two commitments as input, the protocol produces its output in a format that diﬀers from encoding (1).
In addition to the NOT protocol and the committed
AND/XOR protocols, there are copy protocols [1], [3], [9]that can make identical copied commitments from a given
commitment. Thus, as easily imagined, combining theseelementary protocols, one can construct a protocol for any
function (see, e.g., [10]). Moreover, eﬃcient protocols havebeen developed for specific functions, such as the adder [11],three-variable functions [12], and the conjunction of multiple
variables [13].
As seen in the above descriptions of the protocols, a protocol is usually described with a series of somewhat intuitive
illustrations and verbal descriptions, for example, “turn overthis card,” “shuﬄe these two cards,” “apply a random cut tothese five cards,” and so on. In contrast, a formal computational model of card-based protocols via abstract machine
was constructed by Mizuki and Shizuya [14] in 2014. By
virtue of the formalization, it has become possible to treat
card-based protocols more rigorously. For example, it enables one to discuss the lower bounds on the number of cards
required for secure computations. In fact, Koch, Walzer, andHärtel [6] proved that there does not exist a finite-runtime
committed AND protocol using four cards. They also proposed an excellent method, based on the formal computational model, for describing a protocol by which one caneasily confirm its correctness and security [6]. In this paper, an overview of the computational model of card-based
protocols with its applications to designing protocols and asurvey of the recent progress in card-based cryptography arepresented.
Historically, card games may stem from the cards invented in the 9th century, but card protocols for cryptographic purposes were not known until Peter Winkler’s 1981
article [15]. Fischer, Paterson, and Rackoﬀ [16] extended
the idea presented in [15] to implement a secret bit transmission between two players. Following their results, many
researchers designed secret bit transmission and secret key
exchange schemes using a deck of cards (see, e.g., [17]–[21]); it should be noted that they do not intend that a real
deck of cards be used, i.e., dealing cards is rather an abstract notion to capture a priori information distributed toplayers. In contrast, as mentioned before, card-based protocols are supposed to use a real deck of physical cards, i.e.,
humans can practically execute a card-based protocol witheveryday objects. There are other physically implemented
cryptographic protocols, e.g., those presented in [22]–[26].
The remainder of this paper is organized as follows.
We review the computational model of card-based protocols formalized by Mizuki and Shizuya [14] in Sect. 2 andmention a framework for committed protocols in Sect. 3. In
Sect. 4, we present the “Koch-Walzer-Härtel diagram [6],”which enriches descriptions of protocols. We then introduce
the recent AND protocols developed by Koch, Walzer, andHärtel [6] in Sect. 5 and some lower bounds in Sect. 6. In
Sect. 7, we mention additional recent progress in card-based
cryptography. This paper is concluded in Sect. 8 with possible directions of future work.
2. Computational Model
As mentioned above, a formal computational model of cardbased protocols was constructed in 2014 [14]. Then, Koch,
Walzer, and Härtel [6] made some improvement to the descriptions of the model in 2015. In this section, according
to these two papers [6], [14], we overview the computationalmodel by taking the six-card AND protocol [1] shown in
Sect. 1 as an example to exhibit the concepts.
2.1 Notations
Clearly, the most important object for card-based protocols is a deck of cards, for example, a deck of six cards♣ ♣ ♣ ♡ ♡ ♡ , as used in the six-card AND protocol[1]. To represent a deck, we use a multiset such as
D ex = [ ♣, ♣, ♣, ♡, ♡, ♡ ] ,where “ex” represents “example.” Formally, such a nonempty finite multiset D is called a deck if D ∩ {?} = ∅ where“?” is the “back-side” symbol. We call any element c ∈ D
in a deck D (such as ♣ and ♡) an atomic card.
When a card is placed on the table, there are two options:
it is either face-up (e.g., ♣ ) or face-down ( ? ). To capture
this property, we use an expression ♣? or ♣? . Formally, c?
with c ∈ D represents a face-up card (of a deck D), and c?
represents a face-down card. We call a face-up or face-down

MIZUKI and SHIZUYA: COMPUTATIONAL MODEL OF CARD-BASED CRYPTOGRAPHIC PROTOCOLS AND ITS APPLICATIONS

5

card a lying card. Given a lying card c? or c? , we denote its
atomic card by atom ( c? ) = atom ( c? ) = c; further, we denotewhat we can see when looking at the lying card on the tableby top ( c? ) = c and top ( c? ) = ?.
Let us remember the input to the six-card AND protocol[1], namely, a sequence of six cards put on the table:? ? ♣ ♡ ? ?.

|{z}

|{z}

a

b

In order to represent such lying cards, we have to consider
four possible sequences because we do not know the valuesof a and b:(? ? ♣ ♡ ? ?)
Γ00 = , , , , , ,♣ ♡ ? ? ♣ ♡(? ? ♣ ♡ ? ?)
Γ01 = , , , , , ,♣ ♡ ? ? ♡ ♣(? ? ♣ ♡ ? ?), , , , , ,Γ10 =♡ ♣ ? ? ♣ ♡and(? ? ♣ ♡ ? ?), , , , , .
Γ11 =♡ ♣ ? ? ♡ ♣Note that Γ00 corresponds to (a, b) = (0, 0), Γ01 corresponds
to (a, b) = (0, 1), and so on. Thus, the set {Γ00, Γ01, Γ10, Γ11 }is considered to be the input set to the protocol, as seen
again in the next subsection. Formally, we say that ad-tuple Γ = (α1, α2, . . . , α d ) consisting of d lying cards
from a deck D with d = |D| is a sequence from D if
[ atom (α1 ), atom (α2 ), . . . , atom (α d ) ] = D. We define
Seq D = {Γ | Γ is a sequence of D}
def

for a deck D. That is, Seq D is the set of all (possible)
sequences from a deck D.
Next, we extend the use of top (·) to use for a sequence:
given a sequence Γ = (α1, α2, . . . , α d ), we write
top (Γ) = (top (α 1 ), top (α 2 ), . . . , top (α d )),and we call it the visible sequence of Γ. For instance, for theabove sequence Γ00 , the visible sequence is
top (Γ00 ) = (?, ?, ♣, ♡, ?, ?).

We also define the visible sequence set Vis D of D as
Vis D = {top (Γ) | Γ ∈ Seq D }.
def

2.2

Protocols

In this subsection, we formally define a “protocol.” As seen
below, starting from an initial sequence, a protocol specifies
an action to be applied to a current sequence step by step,
depending on its internal state and the visible sequence.
Recall the actions that the six-card AND protocol [1]applies to a sequence: turning over the two middle cards (forwhich we use the expression “turn”), rearranging the order ofthe sequence (“perm”), shuﬄing the halves of the sequence(“shuf”), and specifying the output commitment (“result”).
In addition to these four actions, there is one unfamiliar
action, random flip (“rflip”). The detailed explanations ofthese five actions are given in the following.
A protocol (having a finite state control and a table onwhich a single sequence is put) is formally specified with aquadruple P = (D, U, Q, A):• D is a deck;• U ⊆ Seq D is an input set;
• Q is a state set having an initial state q0 ∈ Q and a final
state qf ∈ Q;
• A : (Q−{qf })× Vis D → Q× Action is an action function,
where Action is the set of the following actions:– (turn, T ) for T ⊆ {1, 2, . . . , |D |};– (perm, π) for π ∈ S | D | , where Si denotes the symmetric group of degree i throughout this paper;– (shuf, Π, F ) for Π ⊆ S | D | and a probability distribution F on Π;– (rflip, Φ, G) for Φ ⊆ 2 {1,2,..., | D | } and a probability
distribution G on Φ;– (result, p1, . . . , pℓ ) for p1, p2, . . . , pℓ ∈ {1, 2, . . . ,|D |}.
The protocol P = (D, U, Q, A) proceeds as the Turing machine does: starting from the initial state q0 and the initial
sequence Γ0 for some input sequence Γ0 ∈ U, its current stateq and sequence Γ move to the next state q ′ and sequence Γ ′according to the output of the action function A. (Note thatthe action function A outputs the next state and action depending on the current state q and visible sequence top (Γ).)
Specifically, given a current sequence Γ = (α1, α2, . . . , α d )with d = |D |, each action in Action transforms the current
sequence Γ into the next sequence Γ ′:• (turn, T ): Γ ′ = ( β1, β2, . . . , β d ) such that{swap (α i ) if i ∈ T;βi =αiotherwisefor every i, 1 ≤ i ≤ d, where swap ( c? ) = c? andswap ( c? ) = c? for an atomic card c;• (perm, π): Γ ′ = (α π −1 (1), α π −1 (2), . . . , α π −1 (d) );• (shuf, Π, F ): Γ ′ resulting from applying action(perm, π) to Γ, where π is a permutation drawn from Π
according to the probability distribution F ;• (rflip, Φ, G): Γ ′ resulting from applying action (turn, T )to Γ, where T is a set drawn from Φ according to theprobability distribution G;• (result, p1, . . . , pℓ ): this action specifies the positions of
the output, and appears if and only if the first componentof the output of A is the final state qf (and the protocol
terminates).
It should be noted that the rearrangement action is a special case of the shuﬄe action, i.e., (perm, π) can be expressed

IEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.1 JANUARY 20176

as (shuf, {π}, F ) with Pr F (π) = 1. Similarly, the turn action
is a special case of the random flip action. Thus, we could
exclude the rearrangement and turn actions from the model
without loss of generality. However, in our opinion, removing these elementary actions would lead to a protocol thatis not human-friendly. Furthermore, the random flip action
has not been used in any known protocols, and at present it
is not even known how to implement it.
If the probability distribution F of a shuﬄe action(shuf, Π, F ) is uniform, then we omit F and simply write(shuf, Π). Let us take the random bisection cut[]? ? ? ? ? ? → ? ? ? ? ? ?

Six-card AND protocol
input set:{( ? ? ♣ ♡ ? ? ) ( ? ? ♣ ♡ ? ? ), , , , , , , , , , , ,♣ ♡ ? ? ♣ ♡♣ ♡ ? ? ♡ ♣( ? ? ♣ ♡ ? ? ) ( ? ? ♣ ♡ ? ? )}, , , , , , , , , , ,♡ ♣ ? ? ♣ ♡♡ ♣ ? ? ♡ ♣(shuf, {id, (1 4)(2 5)(3 6)}, id 7→ 1/2, (1 4)(2 5)(3 6) 7→ 1/2),(turn, {3, 4})(perm, (2 4 3))(shuf, {id, (1 4)(2 5)(3 6)})
(perm, (2 3 4))(turn, {1, 2})
if visible seq. = (♣, ♡, ?, ?, ?, ?) then(result, 3, 4)
else if visible seq. = (♡, ♣, ?, ?, ?, ?) then(result, 5, 6)

where id denotes the identity permutation and (i 1 i 2 . . . i ℓ )means a cyclic permutation. Since it is uniformly distributed,
we simply write

3. Framework for Committed Protocols

used in the six-card AND protocol [1] as an example. The
shuﬄe action is expressed as(shuf, {id, (1 4)(2 5)(3 6)})for the random bisection cut above.
As seen above, the formalization of the shuﬄe action(shuf, Π, F ) given in [14] is quite general, that is, Π can be
any subset of S | D | and F can be any distribution. In fact,
this yielded strong possibility results: Koch, Walzer, andHärtel [6] conceived a four-card committed AND protocol(and so on) by considering unconventional shuﬄes, as shownin Sect. 5.
2.3

Formal Description of the Six-Card AND Protocol

We are now ready to formally describe the six-card AND
protocol [1] based on the computational model explained
above.
The deck for the six-card AND protocol is D ex , shownin Sect. 2.1, and the input set is {Γ00, Γ01, Γ10, Γ11 }, shown
also in Sect. 2.1. Therefore, the quadruple isP

ex= (D , {Γ , Γ , Γ , Γ }, {q0, q1, . . . , q5, qf }, A )
ex

00

01

10

11

ex

such that
Aex (q0, (?, ?, ♣, ♡, ?, ?)) = (q1, (turn, {3, 4}))Aex (q1, (?, ?, ?, ?, ?, ?)) = (q2, (perm, (2 4 3)))Aex (q2, (?, ?, ?, ?, ?, ?)) = (q3, (shuf, {id, (1 4)(2 5)(3 6)}))
Aex (q3, (?, ?, ?, ?, ?, ?)) = (q4, (perm, (2 3 4)))Aex (q4, (?, ?, ?, ?, ?, ?)) = (q5, (turn, {1, 2}))Aex (q5, (♣, ♡, ?, ?, ?, ?)) = (qf, (result, 3, 4))
Aex (q5, (♡, ♣, ?, ?, ?, ?)) = (qf, (result, 5, 6)).
This P ex is the formal description of the six-card AND
protocol. The following type of pseudo-code makes it easierto understand it.

In this section, we introduce the framework for committed
protocols, based on the formalization given by Koch, Walzer,
and Härtel [6].
First, we mention some terms. Consider an execution where a protocol P terminates; then, the enumeration(Γ0, Γ1, ..., Γt ) of all sequences from the initial to the final
one (where Γi−1 is transformed into Γi by an action for every
i, 1 ≤ i ≤ t) is called a sequence-trace (of P). Similarly, such (top (Γ0 ), top (Γ1 ), ..., top (Γt )) is called a visible
sequence-trace. For example, there are two possible visible
sequence-traces of the six-card AND protocol P ex (presented
in Sect. 2.3):((?, ?, ♣, ♡, ?, ?), (?, ?, ?, ?, ?, ?), (?, ?, ?, ?, ?, ?), (?, ?, ?, ?, ?, ?),(?, ?, ?, ?, ?, ?), (♣, ♡, ?, ?, ?, ?), (♣, ♡, ?, ?, ?, ?)) (2)and((?, ?, ♣, ♡, ?, ?), (?, ?, ?, ?, ?, ?), (?, ?, ?, ?, ?, ?), (?, ?, ?, ?, ?, ?),(?, ?, ?, ?, ?, ?), (♡, ♣, ?, ?, ?, ?), (♡, ♣, ?, ?, ?, ?)). (3)Next, we show a formal definition of a committed protocol. To make the treatment general, let us assume that
we have commitments to n bits x 1, x 2, . . . , x n and want toproduce a commitment to the value of f (x 1, x 2, . . . , x n ) fora Boolean function f : {0, 1} n → {0, 1}. Without loss ofgenerality, we obey the encoding scheme (1) (and hence a
deck D is supposed to contain suﬃcient numbers of ♣ and♡, as seen in the following Definition 1).
Definition 1: Let f : {0, 1} n → {0, 1} be a Boolean function. We say that P = (D, U, Q, A) is a committed protocol
for f if the following holds:• the deck D has at least n atomic cards of ♣ and n atomic
cards of ♡;MIZUKI and SHIZUYA: COMPUTATIONAL MODEL OF CARD-BASED CRYPTOGRAPHIC PROTOCOLS AND ITS APPLICATIONS

7♣♡♣♡♣♡ X00♣♡♣♡♡♣ X01♡♣♣♡♣♡ X10♡♣♣♡♡♣ X11• the input set U consists of 2n sequences
Γ (x1,x2,...,xn ) = (α1, α2, . . . , α | D | )(where the superscript (x 1, x 2, . . . , x n ) runs in {0, 1} n )such that)(? ?

if x i = 0;,♡♣(α2i−1, α2i ) = 
 ( ? , ? ) if x = 1i ♡ ♣(perm, (2 4 3))♣♣♡♡♣♡ X00♣♣♡♡♡♣ X01♡♣♡♣♣♡ X10♡♣♡♣♡♣ X11

for every i, 1 ≤ i ≤ n;
• the protocol terminates with a sequence-trace having afinite average number of sequences;• for an execution starting with Γ (x1,x2,..., xn ) , it terminateswith an action (result, p1, p2 ) such that
(
)
? ?

,♡
if f (x 1, x 2, . . . , x n ) = 0;♣()
( β p1 , β p2 ) = 
 ?, ?
if f (x 1, x 2, . . . , x n ) = 1, ♡ ♣(shuf, {id, (1 4)(2 5)(3 6) })♣♣♡♡♣♡♡♣♡♣♣♡♣♣♡♡♡♣♡♡♣♣♣♡♡♣♡♣♡♣♣♡♣♡♣♡

where ( β1, β2, . . . , β | D | ) is the final sequence;• it is secure in the sense of the following Definition 2.

(perm, (2 3 4))♣♡♣♡♣♡♡♣♣♡♣♡♣♡♣♡♡♣♡♣♡♣♣♡♡♣♣♡♡♣♣♡♡♣♣♡

We next consider the security of protocols. Given a protocol P = (D, U, Q, A), let M be a probability distribution
on the input set U; then, we denote the random variable associating probability to a visible sequence-trace by V (M, P) .
Definition 2: We say that a protocol P = (D, U, Q, A) is
secure if, for any probability distribution M on the input set
U, M and V (M, P) are independent of each other, where M(induced by M) is the random variable associating probability to a sequence of U.

Koch-Walzer-Härtel Diagram

In 2015, Koch, Walzer, and Härtel [6] proposed an excellent
method to describe a protocol using a type of diagram, which
we call a Koch-Walzer-Härtel diagram. This diagram provides good understanding of the manner in which a protocol
works correctly and securely.
Figure 1 displays the Koch-Walzer-Härtel diagram ofthe six-card AND protocol
P ex = (D ex, {Γ00, Γ01, Γ10, Γ11 }, {q0, q1, . . . , q5, qf }, Aex )presented in Sect. 2.3. In the diagram, there are six boxes,
each of which contains several atomic sequences (such as♣♡♣♡♣♡ and ♣♣♡♡♣♡) together with polynomials (such as
X00 and 21 X00 + 12 X10 ).
Each box is associated to a prefix of the visible
sequence-trace. (Recall the two visible sequence-traces (2)and (3) shown in Sect. 3.) For instance, the first (topmost)box in Fig. 1 is associated with the prefix((?, ?, ♣, ♡, ?, ?), (?, ?, ?, ?, ?, ?)),
that is, it occurs immediately after turning over the two middle cards. The second box is associated with

1
1
2 X00 + 2 X10
1
1
2 X00 + 2 X10
1
2 X01
1
2 X01
1
2 X11
1
2 X11

(turn, {1, 2}) revealed ♣♡ (turn, {1, 2}) revealed ♡♣♣♡♣♡♣♡ X00 + X10♣♡♣♡♡♣ X01♣♡♡♣♣♡ X11⇒ (result, 3, 4)

We see in the next section that P ex is secure, and hence,is a committed protocol for the AND function (a, b) 7→ a∧b.
4.

1
1
2 X00 + 2 X10
1
1
2 X00 + 2 X10
1
2 X01
1
2 X01
1
2 X11
1
2 X11

Fig. 1♡♣♣♡♣♡ X00 + X10♡♣♡♣♣♡ X01♡♣♣♡♡♣ X11⇒ (result, 5, 6)

Koch-Walzer-Härtel diagram of the six-card AND protocol.

((?, ?, ♣, ♡, ?, ?), (?, ?, ?, ?, ?, ?), (?, ?, ?, ?, ?, ?)),
that is, it occurs immediately after applying action(perm, (2 4 3)). The two bottommost boxes are associatedwith the visible sequence-traces (2) and (3) themselves.
The variable X00 (X01 , X10 , X11 ) represents the probability that the input sequence Γ00 (Γ01, Γ10, Γ11 , respectively)
occurs.
Each polynomial next to an atomic sequence inside abox represents the conditional probability that the atomic sequence occurs, given the prefix of the visible sequence. Let
us take the third box in Fig. 1 as an example. The topmost
polynomial 12 X00 + 21 X10 inside the box represents the probability that the current atomic sequence is ♣♣♡♡♣♡, given
the prefix of the visible sequence((?, ?, ♣, ♡, ?, ?), (?, ?, ?, ?, ?, ?),(?, ?, ?, ?, ?, ?), (?, ?, ?, ?, ?, ?)).
In fact, considering the two actions (perm, (2 4 3)) and(shuf, {id, (1 4)(2 5)(3 6)}), one can confirm that the atomic
sequence ♣♣♡♡♣♡ comes from the input sequence Γ00 or Γ10

IEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.1 JANUARY 20178with a probability of 1/2. One can also easily confirm that
other polynomials (and those in other boxes) are compatible
with the corresponding atomic sequences.
From the observation thus far, one can imagine themanner in which the Koch-Walzer-Härtel diagram of a given
protocol can be derived (see [6] for the details).
Just by looking at the Koch-Walzer-Härtel diagram of a
protocol, we can easily check that it works correctly. Indeed,
the last boxes in the diagram (i.e., Fig. 1) of the six-card AND
protocol immediately show that the actions (result, 3, 4) and(result, 5, 6) correctly specify the location of a commitment
to the AND value.
Furthermore, the security of the six-card AND protocol
can be confirmed through the Koch-Walzer-Härtel diagram.
When summing up all polynomials in any of the six boxes,
we always have X00 + X01 + X10 + X11 , that is, the coefficient of every variable is 1. This implies that the input
sequence and the visible sequence-trace are stochasticallyindependent, and hence, P ex is secure. In general, if, foreach box of the Koch-Walzer-Härtel diagram of a protocol,
the coeﬃcient of every variable is 1 when summing up all
polynomials in the box, then the protocol is secure; see [6]for the details.
Thus, we can formally say that P ex is a committed
protocol for the AND function.
5.

Koch-Walzer-Härtel AND Protocols

We elaborated on the six-card AND protocol in the previous sections. Recall that it is a committed AND protocol,
proposed in 2009, using six cards. Recently, in 2015, Koch,
Walzer, and Härtel [6] improved on the result in terms of thenumber of required cards, i.e., they constructed a four-card
committed AND protocol and a five-card committed AND
protocol. While the former needs to take an average number of trials, the latter always terminates within a bounded
number of actions (i.e., with a sequence-trace of bounded
length). See Table 1 again.
Their four-card AND protocol is as follows.
Koch-Walzer-Härtel four-card AND protocol
input set:{( ? ? ? ? ) ( ? ? ? ? ) ( ? ? ? ? ) ( ? ? ? ? )}, , , , , , , , , , , , , , ,♣ ♡ ♣ ♡♣ ♡ ♡ ♣♡ ♣ ♣ ♡♡ ♣ ♡ ♣
(shuf, {id, (1 3)(2 4)})
(shuf, {id, (2 3)})(turn, {2})if visible seq. = (?, ♣, ?, ?) then(turn, {2})(shuf, {id, (1 3)})1 (shuf, {id, (1 2)(3 4)}, id 7→ 1/3, (1 2)(3 4) 7→ 2/3)
(turn, {4})if visible seq. = (?, ?, ?, ♣) then(result, 1, 2)
else if visible seq. = (?, ?, ?, ♡) then(turn, {4})(shuf, {id, (1 3)})
(perm, (1 3 4 2))
goto 2else if visible seq. = (?, ♡, ?, ?) then(turn, {2})(shuf, {id, (3 4)})2 (shuf, {id, (1 3)(2 4)}, id 7→ 1/3, (1 3)(2 4) 7→ 2/3)
(turn, {1})if visible seq. = (♡, ?, ?, ?) then(result, 2, 4)
else if visible seq. = (♣, ?, ?, ?) then(turn, {1})(shuf, {id, (3 4)})
(perm, (1 2 4 3))
goto 1

It can be seen in the Koch-Walzer-Härtel diagram ofthe protocol depicted in [6] (although we omit it in thispaper) that one can confirm that the protocol above is surely
a committed protocol for the AND function. Notice that the
protocol has a loop, and the expected number of times theloop is repeated is calculated as 9/5 = 1.8 (see [6] for thedetails).
Since we need at least four cards for input commitments
to a and b, this four-card AND protocol is optimal in termsof the number of required cards.
The protocol uses somewhat unusual shuﬄe actions:(shuf, {id, (1 2)(3 4)}, id 7→ 1/3, (1 2)(3 4) 7→ 2/3)
and(shuf, {id, (1 3)(2 4)}, id 7→ 1/3, (1 3)(2 4) 7→ 2/3).
That is, the probability distributions are non-uniform. Whenthe protocol was designed, finding a feasible implementationof such a non-uniform shuﬄe action (by humans) was anopen problem [6] (although a solution was proposed more
recently in 2016 [27]; see Sect. 7.1).
Koch, Walzer, and Härtel [6] also provided a five-card
committed AND protocol that always terminates before abounded number of actions are executed. The protocol uses
one additional card ♡ in addition to the four cards for the
input commitments, as follows.
Koch-Walzer-Härtel five-card AND protocol
input set:{( ? ? ? ? ♡ ) ( ? ? ? ? ♡ ), , , , , , , , , ,♣ ♡ ♣ ♡ ?
♣ ♡ ♡ ♣ ?
( ? ? ? ? ♡ ) ( ? ? ? ? ♡ )}, , , , , , , , ,♡ ♣ ♣ ♡ ?
♡ ♣ ♡ ♣ ?
(turn, {5})(shuf, {id, (1 3)(2 4)})
(shuf, {id, (2 3)})(turn, {2})if visible seq. = (?, ♣, ?, ?, ?) thenMIZUKI and SHIZUYA: COMPUTATIONAL MODEL OF CARD-BASED CRYPTOGRAPHIC PROTOCOLS AND ITS APPLICATIONS

9(turn, {2})(shuf, {id, (1 3)})⋆ (perm, (1 5 2 4))(shuf, {id, (5 4 3 2 1)}, id 7→ 2/3, (5 4 3 2 1) 7→ 1/3)
(turn, {5})if visible seq. = (?, ?, ?, ?, ♣) then(result, 4, 3)
else if visible seq. = (?, ?, ?, ?, ♡) then(result, 3, 1)
else if visible seq. = (?, ♡, ?, ?, ?) then(turn, {2})(shuf, {id, (3 4)})
(shuf, {id, (1 3)(2 4)}, id 7→ 1/3, (1 3)(2 4) 7→ 2/3)
(turn, {1})if visible seq. = (♡, ?, ?, ?, ?) then(result, 2, 4)
else if visible seq. = (♣, ?, ?, ?, ?) then(turn, {1})(shuf, {id, (3 4)})
(perm, (1 2 4 3))
goto ⋆
This protocol also uses non-uniform shuﬄe actions:(shuf, {id, (5 4 3 2 1)}, id 7→ 2/3, (5 4 3 2 1) 7→ 1/3)
and(shuf, {id, (1 3)(2 4)}, id 7→ 1/3, (1 3)(2 4) 7→ 2/3).
Note that, while the latter shuﬄe, which already appears in the four-card protocol above, is “closed” (because((1 3)(2 4)) 2 = id), the former shuﬄe is not. These two
unconventional shuﬄe actions can also be implemented byhumans [27]; see Sect. 7.1.
6.

7. Recent Progress
In this section, we introduce other recent progress in cardbased cryptography.
7.1 Implementation of Non-Uniform Shuﬄe
As seen in Sect. 5, the Koch-Walzer-Härtel AND protocols[6] developed in 2015 utilize non-uniform shuﬄe actions.
In 2016, Nishimura et al. [27] presented a secure implementation of a non-uniform shuﬄe. To implement the
shuﬄe, they utilized physical cases that can store piles ofcards, such as boxes and envelopes. Therefore, humans areable to perform the non-uniform shuﬄe using these everyday
objects.
7.2 Random Permutation without Fixed Points
Card-based protocols can perform not only secure multiparty
computation but also other cryptographic tasks. In fact, in
1993, Crépeau and Kilian [3] proposed a card-based protocol that generates a random permutation having no fixed
point. Such a random permutation is preferable when nplayers want to exchange gifts, because they can avoid theundesirable situation where a player must buy a present forhimself/herself. Crépeau and Kilian’s protocol [3] requires
2n2 cards of four colors. The permutation is produced asa sequence of face-down cards and each of n players canreceive his/her portion that privately tells him/her for whomhe/she is going to buy a present.
Recently in 2015, Ishikawa, Chida, and Mizuki [28]improved on the result, i.e., they designed a new protocol tosolve the “no fixed point” problem, showing that n2 cardsof two colors are suﬃcient. They also proposed a protocol
using O(n log n) cards of two colors.

Lower Bounds
7.3 Use of Polarizing Cards and Polygon Cards

By virtue of the formal computational model presented in
Sect. 2, it is now possible to discuss impossibility results orlower bounds on the number of required cards.
The first impossibility result that was shown in [14]is that it is impossible to make two identical copied facedown cards from an unknown face-down card (with perfectsecrecy).
Next, Koch, Walzer, and Härtel [6] proved that there
is no finite-runtime committed AND protocol using four
cards. In their proof, after they supposed a four-card finiteruntime committed AND protocol, they carefully analyzed
and characterized possible atomic sequences in a box in the
Koch-Walzer-Härtel diagram of such a protocol to derive acontradiction. Therefore, this non-existence result immediately implies that their five-card AND protocol presented in
Sect. 5 is the best possible (remember that it uses five cards
and is of finite-runtime).
It will be appreciated if other lower bounds are found.

Shinagawa et al. [29] considered using a diﬀerent typeof card, i.e., they proposed protocols based on polarizing
plates. Roughly speaking, one can encode a bit value by
using two polarizing plates, depending on whether light canpass through the superimposed plates or not.
Shinagawa et al. [30] also considered the use of regularpolygon cards. This allows eﬃcient protocols to be constructed for secure computations of multi-valued input andoutput functions, because, roughly speaking, one can encode
such an i-valued input using a regular i-sided polygon card
according to its angle when it is put on the table.
8. Conclusion
In this paper, we reviewed the computational model of cardbased protocols with its applications to designing protocols
and recent progress. As considering a non-uniform shuﬄe
has contributed to reducing the number of required cards, theIEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.1 JANUARY 201710

general computational model interestingly yields not only
impossibility results but also broad feasibility results.
To conclude this paper, it is worth noting that many
issues remain to be addressed in the future, as follows.
• Past research activities have been devoted mainly to
reducing the number of cards used in a protocol. However, also of interest is the number of actions executedin a protocol. It is not yet known whether there is atrade-oﬀ between the number of cards and number ofactions. The two numbers may correspond to the spacecomplexity and time complexity, respectively. Protocols having fewer actions might be necessary for some
applications.
• As mentioned in Sect. 2.2, one can consider any complicated shuﬄe action based on a mathematical theory.
However, humans might not be able to execute suchcomplicated shuﬄes in practice. A more exact characterization of shuﬄe actions that humans can easily
implement is desirable (cf. [6]).
• The construction of more formal computational models
for polarizing cards and regular polygon cards (introduced in Sect. 7.3) is one intriguing direction of future
work.
• Card-based cryptography is useful for educational purposes; indeed, it has attracted many computer science
students (e.g., [31]). We have confirmed that nonspecialists such as high school students can easily perform card-based protocols using a real deck of cards; forexample, without experiencing a problem, 21 students
in our course were able to execute the six-card AND
protocol 20 times to determine whether they were all
keen to go for lunch together or not (avoiding an embarrassing situation). Suggestions for other attractive
applications would be welcome.
• When executing a card-based protocol in daily life, there
might be a “hardware” issue; for example, some cards
may have scuﬀ marks on their faces. Since only Mizuki
and Shizuya [32] have attempted to resolve this issue,
further research would be beneficial.
Acknowledgments
We thank the editor and the anonymous reviewers, whose
comments helped us to improve the presentation of this paper. This work was supported in part by JSPS KAKENHI
Grant Numbers 26330001 and 26330150.
References[1] T. Mizuki and H. Sone, “Six-card secure AND and four-card secure XOR,” Frontiers in Algorithmics, Lecture Notes in Computer
Science, vol.5598, pp.358–369, Springer Berlin Heidelberg, Berlin,
Heidelberg, 2009.
[2] B. den Boer, “More eﬃcient match-making and satisfiability thefive card trick,” Advances in Cryptology, EUROCRYPT’89, Lecture
Notes in Computer Science, vol.434, pp.208–217, Springer Berlin
Heidelberg, Berlin, Heidelberg, 1990.

[3] C. Crépeau and J. Kilian, “Discreet solitary games,” Advancesin Cryptology, CRYPTO’93, Lecture Notes in Computer Science,
vol.773, pp.319–330, Springer Berlin Heidelberg, 1994.
[4] V. Niemi and A. Renvall, “Secure multiparty computations without computers,” Theor. Comput. Sci., vol.191, no.1-2, pp.173–183,
1998.
[5] A. Stiglic, “Computations with a deck of cards,” Theor. Comput.
Sci., vol.259, no.1-2, pp.671–678, 2001.
[6] A. Koch, S. Walzer, and K. Härtel, “Card-based cryptographic protocols using a minimal number of cards,” Advances in Cryptology,
ASIACRYPT 2015, Lecture Notes in Computer Science, vol.9452,
pp.783–807, Springer Berlin Heidelberg, Berlin, Heidelberg, 2015.
[7] T. Mizuki, F. Uchiike, and H. Sone, “Securely computing XOR with
10 cards,” Australasian J. Combinatorics, vol.36, pp.279–293, 2006.
[8] T. Mizuki, M. Kumamoto, and H. Sone, “The five-card trick can bedone with four cards,” Advances in Cryptology, ASIACRYPT 2012,
Lecture Notes in Computer Science, vol.7658, pp.598–606, Springer
Berlin Heidelberg, Berlin, Heidelberg, 2012.
[9] A. Nishimura, T. Nishida, Y. Hayashi, T. Mizuki, and H. Sone,“Five-card secure computations using unequal division shuﬄe,” Theory and Practice of Natural Computing, Lecture Notes in Computer
Science, vol.9477, pp.109–120, Springer International Publishing,
Cham, 2015.
[10] T. Nishida, Y. Hayashi, T. Mizuki, and H. Sone, “Card-based protocols for any Boolean function,” Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol.9076,
pp.110–121, Springer International Publishing, Cham, 2015.
[11] T. Mizuki, I.K. Asiedu, and H. Sone, “Voting with a logarithmic
number of cards,” Unconventional Computation and Natural Computation, Lecture Notes in Computer Science, vol.7956, pp.162–173,
Springer Berlin Heidelberg, Berlin, Heidelberg, 2013.
[12] T. Nishida, Y. Hayashi, T. Mizuki, and H. Sone, “Securely computing
three-input functions with eight cards,” IEICE Trans. Fundamentals,
vol.E98-A, no.6, pp.1145–1152, 2015.
[13] T. Mizuki, “Card-based protocols for securely computing the conjunction of multiple variables,” Theor. Comput. Sci., vol.622, pp.34–
44, 2016.
[14] T. Mizuki and H. Shizuya, “A formalization of card-based cryptographic protocols via abstract machine,” Int. J. Inf. Secur., vol.13,
no.1, pp.15–23, 2014.
[15] P. Winkler, “Cryptologic techniques in bidding and defense: Part i,”
Bridge Magazine, pp.148–149, 1981.
[16] M.J. Fischer, M.S. Paterson, and C. Rackoﬀ, “Secret bit transmission
using a random deal of cards,” Distributed Computing and Cryptography, Proc. DIMACS Workshop, pp.173–182, Princeton, New
Jersey, USA, 1989.
[17] Z. Duan and C. Yang, “Unconditional secure communication: A
Russian cards protocol,” J. Comb. Optim., vol.19, no.4, pp.501–530,
2010.
[18] M.J. Fischer and R.N. Wright, “Bounds on secret key exchange usinga random deal of cards,” J. Cryptol., vol.9, no.2, pp.71–99, 1996.
[19] T. Mizuki, H. Shizuya, and T. Nishizeki, “A complete characterization of a family of key exchange protocols,” International Journal of
Information Security, vol.1, no.2, pp.131–142, 2002.
[20] T. Mizuki, H. Shizuya, and T. Nishizeki, “Characterization of optimal
key set protocols,” Discrete Appl. Math., vol.131, no.1, pp.213–236,
2003.
[21] C.M. Swanson and D.R. Stinson, “Combinatorial solutions providing
improved security for the generalized Russian cards problem,” Des.
Codes Cryptogr., vol.72, no.2, pp.345–367, 2014.
[22] J. Balogh, J.A. Csirik, Y. Ishai, and E. Kushilevitz, “Private computation using a PEZ dispenser,” Theor. Comput. Sci., vol.306, no.1-3,
pp.69–84, 2003.
[23] R. Fagin, M. Naor, and P. Winkler, “Comparing information without
leaking it,” Commun. ACM, vol.39, no.5, pp.77–85, 1996.
[24] T. Moran and M. Naor, “Polling with physical envelopes: A rigorous analysis of a human-centric protocol,” Advances in Cryptology,

MIZUKI and SHIZUYA: COMPUTATIONAL MODEL OF CARD-BASED CRYPTOGRAPHIC PROTOCOLS AND ITS APPLICATIONS

11EUROCRYPT 2006, Lecture Notes in Computer Science, vol.4004,
pp.88–108, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
[25] B. Fisch, D. Freund, and M. Naor, “Physical zero-knowledge proofsof physical properties,” Advances in Cryptology, CRYPTO 2014,
Lecture Notes in Computer Science, vol.8617, pp.313–336, Springer
Berlin Heidelberg, Berlin, Heidelberg, 2014.
[26] A. Glaser, B. Barak, and R.J. Goldston, “A zero-knowledge protocol
for nuclear warhead verification,” Nature, vol.510, no.7506, pp.497–
502, 2014.
[27] A. Nishimura, Y. Hayashi, T. Mizuki, and H. Sone, “An implementation of non-uniform shuﬄe for secure multi-party computation,”
Proc. 3rd ACM International Workshop on ASIA Public-Key Cryptography, AsiaPKC’16, pp.49–55, 2016.
[28] R. Ishikawa, E. Chida, and T. Mizuki, “Eﬃcient card-based protocols for generating a hidden random permutation without fixed
points,” Unconventional Computation and Natural Computation,
Lecture Notes in Computer Science, vol.9252, pp.215–226, Springer
International Publishing, Cham, 2015.
[29] K. Shinagawa, T. Mizuki, J. Schuldt, K. Nuida, N. Kanayama,
T. Nishide, G. Hanaoka, and E. Okamoto, “Secure multi-party
computation using polarizing cards,” Advances in Information andComputer Security, Lecture Notes in Computer Science, vol.9241,
pp.281–297, Springer International Publishing, Cham, 2015.
[30] K. Shinagawa, T. Mizuki, J.C.N. Schuldt, K. Nuida, N. Kanayama,
T. Nishide, G. Hanaoka, and E. Okamoto, “Multi-party computation
with small shuﬄe complexity using regular polygon cards,” Provable
Security, Lecture Notes in Computer Science, vol.9451, pp.127–146,
Springer International Publishing, Cham, 2015.
[31] A. Marcedone, Z. Wen, and E. Shi, “Secure dating with four or fewer
cards,” Cryptology ePrint Archive, Report 2015/1031, 2015.
[32] T. Mizuki and H. Shizuya, “Practical card-based cryptography,” Funwith Algorithms, Lecture Notes in Computer Science, vol.8496,
pp.313–324, Springer International Publishing, Cham, 2014.

Takaaki Mizuki
received his B.E. degree in
information engineering and his M.S. and Ph.D.
degrees in information sciences from Tohoku
University, Japan, in 1995, 1997, and 2000, respectively. He is currently an associate professorof the Cyberscience Center, Tohoku University.
His research interests include cryptology and information security. He is a member of IEICE,
IEEE, and IPSJ.

Hiroki Shizuya
received his B.E, M.E., andPh.D. degrees from Tohoku University, Japan, in
1981, 1984, and 1987, respectively. He joined
Tohoku University in 1987, and has been a Professor since 1995. He is currently with both theCenter for Information Technology in Educationand the Department of Computer and Mathematical Sciences, Graduate School of Information
Sciences. His current interests are in Cryptology and Computational Complexity Theory. He
is a member of ACM and IEEE.