A Formalization of Card-Based Cryptographic Protocols
via Abstract Machine∗
Takaaki Mizuki

Hiroki Shizuya

Tohoku University
tm-paper+ijisw[atmark]g-mail.tohoku-university.jp

Abstract
Consider a face-down card lying on the table such that we do not know whether its
suit color is black or red. Then, how do we make identical copies of the card while keeping its color secret? A partial solution has been devised: using a number of additional
black and red cards, Niemi and Renvall proposed an excellent protocol which can copy aface-down card while allowing only a small probability of revealing its color. In contrast,
this paper shows the non-existence of a perfect solution, namely, the impossibility of
copying a face-down card with perfect secrecy. To prove such an impossibility result, weconstruct a rigorous mathematical model of card-based cryptographic protocols; giving
this general computational model is the main result of this paper.

1

Introduction

Consider a face-down card ? lying on the table such that we do not know whether its suitcolor is black ( ♣ ) or red ( ♥ ). Then, how do we make identical copies of the card, say
two copies ? ? (having the same color as the original card), while keeping its color secret?
A partial solution has been presented in the literature: using a number of additional
black and red cards ♣ ♣ · · · ♣ ♥ ♥ · · · ♥ (whose backs ? are identical), Niemi and Renvall [11] proposed an excellent protocol which can copy a face-down card ? while allowing
only a small probability of revealing its color; as seen later, in their protocol, a large numberof cards reduces the probability of failure (namely, leaking the color information).
Because of nonzero probability of leaking information about the color of the face-downcard to be copied, Niemi-Renvall’s copy protocol provides a partial solution to the above
problem. In contrast, to the best of our knowledge, the question “what about perfectsolutions?” has not yet been answered. In this paper, we deal with this problem, and show
the non-existence of a perfect solution. That is, we prove the impossibility of copying aface-down card with perfect secrecy. To prove such an impossibility result, we construct
a rigorous mathematical model of card-based cryptographic protocols; giving a generalcomputational model via abstract machine is the main result of this paper.
This paper begins with an example of executing Niemi-Renvall’s copy protocol.
∗

This paper appears in International Journal of Information Security. The final publication is available
at link.springer.com (DOI: 10.1007/s10207-013-0219-4).

1

1.1

Making two copies with success probability 7/8

Given a face-down card ? , Niemi-Renvall’s copy protocol [11] allows us to securely make its
k copies with success probability 1−1/2s+1 using (k+1)+(2s+1 −2) pairs of additional blackand red cards (where the integer s ≥ 0 is a security parameter; see [11] for details). Here,take the simple case of k = s = 2 as an example. Then, the protocol uses (2+1)+(22+1 −2) =9 pairs of ♣ ♥ , and thus we have a sequence of cards?

♣♥♣♥♣♥♣♥♣♥ ♣♥♣♥♣♥♣♥(1)x

on the table, where the leftmost card is the given face-down card (to be copied) whose
secret color is denoted by x ∈ {♣, ♥} attached below it. Starting from the sequence (1),the protocol proceeds as follows.
First, turn over all face-up cards so that they are facing down:?
x? ? ? ? ? ?

♣ ♥ ♣ ♥ ♣ ♥? ? ? ? ? ? ? ? ? ? ? ?

♣ ♥ ♣ ♥♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥(where a symbol indicating the color is provided below each card for convenience), andapply three random cuts, each of which is denoted by ·:

 


?
? ? ? ? ? ?
? ? ? ?
? ? ? ? ? ? ? ? .
xA random cut means that, as in the case of usual card games, a random number of cards
on the left are moved on the right side of the sequence without changing their order (ofcourse, the random number must be unknown). Therefore, we now have1

2?

? ? ? ? ? ?

? ? ? ?

? ? ? ? ? ? ? ?

xy

r1 r1 r1 r1

r2 r2 r2 r2 r2 r2 r2 r2

3
y

4
y

5
y

6
y

7
y

8

9 10 11

12 13 14 15 16 17 18 19(2)

for three random colors y, r1 , r2 ∈ {♣, ♥}, where y denotes the color opposite to that of y,i.e., {y} = {♣, ♥} − {y} (r1 and r2 are deﬁned similarly). Next, consider the 1st, 2nd, 8th,
10th, 12th, 14th, 16th and 18th cards (from the left):
1

2

8 10

?

?

? ?

? ? ? ? .

x

y

r1 r1

r2 r2 r2 r2

12 14 16 18

Note that if x = y, i.e., both colors of the ﬁrst and second cards are the same, then thenumber of black cards (as well as the number of red cards) among these eight cards mustbe even; if x = y, i.e., x = y, then it must be odd. Finally, after shuﬄing all eight cards(namely, after applying a random permutation), reveal all of them. If an even number ofblack cards appear, then the fourth and sixth cards
6

4

? ?
y

y

in the sequence (2) are two copies having the color x (because x = y), as desired. If an odd
number of black cards appear, then the ﬁfth and seventh cards
5

7

? ?
y

y

2

are the desired two copies.
When all eight revealed cards have the same color, i.e., x = y = r1 = r2 , one can deducethe color x unambiguously, of course, and hence the secure copy fails; this event occurs withprobability 1/23 . When x = y = r1 = r2 does not hold, one obtains no information about
the color x from looking at the colors of the eight shuﬄed cards. (See [11] for a formal
proof.) Thus, Niemi-Renvall’s copy protocol for k = s = 2 nicely makes two copies withsuccess probability 7/8.

1.2

Our results and related work

As mentioned in the previous subsection, if a small probability of leaking information about
the color of a given face-down card is acceptable, then one can construct a protocol forcopying the card; this may be suﬃcient for some practical purposes.
In contrast, this paper deals with perfect secrecy. Intuitively, it seems impossible todesign a perfectly secure copy protocol. However, relying on intuition sometimes leads toerrors. Therefore, to prove such an impossibility result, we construct a rigorous mathematical model of card-based protocols. Based on such a general computational model, we show
the impossibility of copying a face-down card with perfect secrecy.
Our computational model (constructed later in Section 2) is rather general, and hence
we believe that it can be used for proving the impossibility, ﬁnding lower bounds, or showing
the optimality of certain protocols. For example, several card-based cryptographic protocols
for secure computation are listed in Table 1, and it might be possible to show that a
protocol is optimal under some criteria, such as the number of required cards, by using
our computational model; more speciﬁcally, for instance, the six-card “committed format”
secure AND protocol given in [8] could be proven to be best possible or not. In this context,
constructing a formal computational model itself is worthwhile work.
# of colors # of cards◦ Secure AND in a non-committed format
den Boer [2]25
Mizuki-Kumamoto-Sone [7]24◦ Secure AND in a committed format
Crépeau-Kilian [3]410
Niemi-Renvall [11]212Stiglic [13]28Mizuki-Sone [8]26◦ Secure XOR in a committed format
Crépeau-Kilian [3]414
Mizuki-Uchiike-Sone [9]210Mizuki-Sone [8]24◦ Secure Half Adder in a committed format
Mizuki-Asiedu-Sone [6]28◦ Secure Full Adder in a committed format
Mizuki-Asiedu-Sone [6]210Avg. # of trials
1
1
6
2.5
2
1
6
2
1
1
1

Table 1: Known card-based protocols for secure computation.

3

The research area of card-based protocols along with other physically implemented cryptographic protocols (e.g. [1, 4, 10]) can aid professional cryptographers to intuitively explain
to nonspecialists the nature of their constructed cryptographic protocols or what cryptography is in general. Some card-based protocols are implemented and used in online games[12].
The remainder of this paper is organized as follows. In Section 2, we give a generalcomputational model of card-based protocols. In Section 3, based on our constructed model,
we present a framework for copy protocols. In Section 4, we prove the impossibility of
copying a face-down card with perfect secrecy. This paper is concluded in Section 5 withpossible directions of future work.

2

Computational Model of Card-Based Protocols

In this section, we formally deﬁne a computational model which captures what can possibly
be done in playing cards. Speciﬁcally, we deﬁne a deck, cards and sequences (on a table)in Section 2.1, consider operations (which can be applied to sequences) in Section 2.2, andgive a formal deﬁnition of a protocol in Section 2.3.
As seen below, we introduce many terms and notations. However, we believe that such along deﬁnition would be unavoidable when constructing a computation model that precisely
captures a new concept (not formalized before).

2.1

A deck, cards and sequences

We refer to a non-empty ﬁnite multiset D with D ∩ {?} = ∅ as a deck, where ’?’ is the“back-side” symbol (as easily imagined). Any element c ∈ D in a deck D is called an atomic
card. For instance, as seen in Section 1.1, Niemi-Renvall’s copy protocol for k = s = 2
implicitly assumes a deck
D ex = [ ♣, ♣, ♣, ♣, ♣, ♣, ♣, ♣, ♣, ♣, ♥, ♥, ♥, ♥, ♥, ♥, ♥, ♥, ♥, ♥ ]consisting of 10 ♣ s and 10 ♥ s (where we use square brackets to represent a multiset),because in addition to the nine pairs of ♣ ♥ , another pair is necessary for producing an
unknown face-down card?
x

to be copied (recall the sequence (1)).
Next, we consider a card lying on the table. For a deck D, an expression ?c with c ∈ D
is called a face-up card (of D), and ?c with c ∈ D is called a face-down card (of D). For
instance, in accordance with the expressions appearing before, a face-up card ♣? means ♣ ,and a face-down card ♥? means?.
♥

Hereafter, any face-up or face-down card α of D (i.e., α = ?c or α = ?c with c ∈ D) is calleda lying card (of D). Given a lying card α of D, we denote its atomic card by atom(α), thatis, we deﬁne atom(α) = c for a lying card α = ?c or α = ?c . For instance, atom( ♣? ) = ♣,and atom( ♥? ) = ♥.
We say that a d-tuple Γ = (α1 , α2 , . . . , αd ) consisting of d lying cards from a deck Dwith d = |D| (namely, d is the number of atomic cards in D) is a sequence from D ifdef

4

[ atom(α1 ), atom(α2 ), . . . , atom(αd ) ] = D. For instance, the initial “sequence” (1) seen in
Section 1.1 can be expressed as a sequence from the above deck D ex :
Γex1 =

 ? ? ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥
, , , , , , , , , , , , , , , , , , ,♥ ♣ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

Γex2 =

 ? ? ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥
, , , , , , , , , , , , , , , , , , ,.
♣ ♥ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

orNote that the ﬁrst two face-down cards (in both Γex1 and Γex2 ) are intended to be utilized
for producing an unknown face-down card?
x

(to be copied); if we regard the second face-down card as the unknown one, then the sequenceΓex1 corresponds to x = ♣, and Γex2 corresponds to x = ♥. Thus, in Niemi-Renvall’s copy
protocol, given Γex1 or Γex2 , it suﬃces to copy the second face-down card while ignoring
the ﬁrst one. (Throughout this paper, the sequences Γex1 and Γex2 together with the deck
D ex and so on are used as a ﬁxed example to illustrate our terminology and computationalmodel.)
To employ later, we denote by SeqD the set of all (possible) sequences from a deck D:
we deﬁne
def
SeqD = {Γ | Γ is a sequence of D}
for a deck D.

2.2

Operations

Given a sequence Γ = (α1 , α2 , . . . , αd ) ∈ SeqD from a deck D (on the table), we have threenatural operations and one new operation, as described below.
2.2.1

Turning over
def

def

Deﬁne swap( ?c ) = ?c and swap( ?c ) = ?c for an atomic card c. To express the operation ofturning over lying cards, we introduce an operation turnT (·) with a turn set T ⊆ {1, 2, . . . , d}for a sequence Γ = (α1 , α2 , . . . , αd ):defturnT ((α1 , α2 , . . . , αd )) = (β1 , β2 , . . . , βd )such thatβi =swap(αi ) if i ∈ T ;otherwise
αifor every i, 1 ≤ i ≤ d. Thus, every card whose position is in the turn set T is turned overby turnT (·).
For example, for the sequence Γex1 above,turn{3,4,...,20} (Γex1 )? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?, , , , , , , , , , , , , , , , , , ,.
=♥ ♣ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥ ♣ ♥5

2.2.2

Rearrangement

One may sometimes want to change the order of a sequence. To this end, we introduce anoperation permπ (·) based on a permutation π ∈ Sd for a sequence Γ = (α1 , α2 , . . . , αd ):defpermπ ((α1 , α2 , . . . , αd )) = (απ−1 (1) , απ−1 (2) , . . . , απ−1 (d) )where Sd denotes the symmetric group of degree d (throughout this paper).
2.2.3

Shuﬄing

Remember that Niemi-Renvall’s copy protocol utilizes a random cut, which is a type of
shuﬄe operation. All existing protocols listed in Table 1 also utilize some form of shuﬄe
operation. Unquestionably, shuﬄing must be the most important operation for card-based
cryptographic protocols. Here, we consider as general a treatment of shuﬄing as possible.
Whereas the operations turnT (·) and permπ (·) are deterministic as seen above, the shuﬄe
operation is randomized.
For a sequence Γ = (α1 , α2 , . . . , αd ), we deﬁne an operation shuf Π,F (·) with a shuﬄepair (Π, F) where Π ⊆ Sd is called a permutation-set and F is a probability distribution onΠ:def
shuf Π,F ((α1 , α2 , . . . , αd )) = permπ ((α1 , α2 , . . . , αd ))such that π is a permutation drawn from Π according to the probability distribution F.
Thus, shuf Π,F (Γ) probabilistically chooses a permutation π from the permutation-set Π
according to the distribution F, and applies it to the sequence Γ.
For example, let Πex1 = {π1 , π2 , . . . , π6 } with
π1 = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
π2 = (1, 2, 8, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)..
.
π6 = (1, 2, 4, 5, 6, 7, 8, 3, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20),and let F ex1 be such that
PrF ex1 (πi ) = 1/6
for every i, 1 ≤ i ≤ 6. Then, shuf Πex1 ,F ex1 (Γ) means a random cut to the stack consisting of
the 3rd, 4th, 5th, 6th, 7th and 8th cards in the sequence Γ = turn{3,4,...,20} (Γex1 ) (as appliedin Niemi-Renvall’s copy protocol).
To use later, we present a notation for the set of all (possible) shuﬄe pairs under a deck
D with d = |D|:def

SPd = {(Π, F) | F is a probability distribution on Π ∈ 2Sd }.
It should be noted that the rearrangement operation permπ (·) above can be expressed
exactly as shuf {π},F (·) such that PrF (π) = 1. Therefore, if preferable, one could exclude theoperation permπ (·) from the model without loss of generality. Furthermore, note that any
number of consecutive shuﬄe operations can be combined into a single shuﬄe operation;for example, let (Πex2 , F ex2 ) be a shuﬄe pair corresponding to a random cut to the stack6

consisting of the 9th, 10th, 11th and 12th cards (as also applied in Niemi-Renvall’s copy
protocol), then shuf Πex2 ,F ex2 (shuf Πex1 ,F ex1 (·)) can be expressed as shuf Π ,F  (·) such thatΠ = {σ 2 ◦ σ 1 | σ 1 ∈ Πex1 , σ 2 ∈ Πex2 }and PrF  (π) = 1/24 for every π ∈ Π . (On the other hand, removing rearrangement
operations or combining shuﬄe operations might lead to a protocol that is not playerfriendly.)
2.2.4

Random ﬂip

As seen above, we obtained the shuﬄe operation shuf Π,F (·) by adding randomization to
the rearrangement operation permπ (·). Analogically, one may add randomization to theturn over operation turnT (·). For example, given a sequence, one might want to reveal aface-down card at a random position in the sequence.
For a sequence Γ = (α1 , α2 , . . . , αd ), we deﬁne an operation rflipΦ,G (·) with a ﬂip-pair(Φ, G) where G is a probability distribution on Φ ⊆ 2{1,2,...,d} :defrflipΦ,G ((α1 , α2 , . . . , αd )) = turnT ((α1 , α2 , . . . , αd ))such that T is a turn set drawn from Φ according to the probability distribution G. We also
deﬁne
def
FPd = {(Φ, G) | G is a probability distribution on Φ ⊆ 2{1,2,...,d} }.
A random ﬂip operation has not been used in the construction of any of the existing
protocols, and at present, its usefulness and potential power (and even the diﬃculty of its
implementation) are unclear. However, we positively include this operation in our model
because we desire as general a model as possible.

2.3

A protocol

In this subsection, we provide a formal deﬁnition of a “protocol.” Roughly speaking, aprotocol, which has a ﬁnite state control and a table, speciﬁes an operation to be applied toa current sequence step by step, depending on its internal state and the view of looking down
the sequence on the table. Our formalization of protocols is partially based on the ideas
behind the Turing machine [14] with a random tape and Fischer-Wright’s communication
model [5].
2.3.1

Notations

Let D be a deck.
First of all, we have to consider the “input” to a protocol. For example, as seen before,Niemi-Renvall’s copy protocol for k = s = 2 starts from the sequence Γex1 or Γex2 (illustrated
in Section 2.1), and hence we can consider the set {Γex1 , Γex2 } as an input. Thus, the input
set U to a protocol is a set of sequences from D, i.e., U ⊆ SeqD .
Next, consider what one can look at on the table during the execution of a protocol.
That is, the action of a protocol can depend on the view on the table. Therefore, we deﬁne
the visible sequence vis(Γ) of a sequence Γ = (α1 , α2 , . . . , αd ) as:defvis((α1 , α2 , . . . , αd )) = (top(α1 ), top(α2 ), . . . , top(αd ))
7

def

def

where top( ?c ) = c and top( ?c ) = ? for an atomic card c. For instance, for the above sequenceΓex1 ,
vis(Γex1 ) = (?, ?, ♣, ♥, ♣, ♥, ♣, ♥, ♣, ♥, ♣, ♥, ♣, ♥, ♣, ♥, ♣, ♥, ♣, ♥).
Furthermore, we deﬁne the visible sequence set VisD of D as:
VisD = {vis(Γ) | Γ ∈ SeqD };defrecall that SeqD is the set of all sequences from D.
The action of a protocol also depends on its state. The state set Q is a ﬁnite set of states
having an initial state q0 ∈ Q and a ﬁnal state qf ∈ Q.
Given a state q ∈ Q − {qf } and a visible sequence v ∈ VisD , a protocol has to specify an
operation, turnT (·), permπ (·), shuf Π,F (·) or rflipΦ,G (·), to be performed at that step. Thiscan be captured by a partial function, called an action function,
A : (Q − {qf }) × VisD → Q × (2{1,2,...,d} ∪ Sd ∪ SPd ∪ FPd )where d = |D|. Recall that Sd is the symmetric group of degree d, and that SPd and FPd
are the set of all shuﬄe pairs and the set of all ﬂip-pairs, respectively; therefore, note that2{1,2,...,d} , Sd , SPd and FPd are pairwise disjoint. The action function determines both thenext state and the operation to be performed. That is, A(q, v) = (q  , T ) with q  ∈ Q andT ∈ 2{1,2,...,d} means that the state in the ﬁnite state control becomes q  and the sequenceon the table becomes turnT (Γ) where Γ is the current sequence and hence v = vis(Γ).
Similarly, A(q, v) = (q  , π) with π ∈ Sd means that the sequence turns into permπ (Γ)
from Γ, A(q, v) = (q  , (Π, F)) with (Π, F) ∈ SPd means that the sequence probabilistically
becomes shuf Π,F (Γ), and A(q, v) = (q  , (Φ, G)) with (Φ, G) ∈ FPd means that the sequence
probabilistically becomes rflipΦ,G (Γ).
2.3.2

How to move

We are now ready to formally deﬁne a protocol. A protocol (having a ﬁnite state control
and a table on which a single sequence is placed) is a quadruple P = (D, U, Q, A) where• D is a deck;• U ⊆ SeqD is an input set;
• Q is a state set having an initial state q0 ∈ Q and a ﬁnal state qf ∈ Q;
• A : (Q − {qf }) × VisD → Q × (2{1,2,...,|D|} ∪ S|D| ∪ SP|D| ∪ FP|D| ) is an action function.
A protocol P = (D, U, Q, A) proceeds as expected: starting from the initial instantaneous description (q0 , Γ0 ) for some input Γ0 ∈ U , its instantaneous description, namely apair of its current state and sequence on the table moves to another one according to the
output of the action function A. When the state becomes the ﬁnal state qf , the protocol terminates. Note that when A outputs a shuﬄe pair (Π, F) or a ﬂip-pair (Φ, G), themove is randomized (unless PrF (π) = 1 for some π ∈ Π or PrG (T ) = 1 for some T ∈ Φ).
If the action function A(q, Γ) for some instantaneous description (q, Γ) is undeﬁned during the execution of the protocol, then the execution aborts. For an execution where theprotocol P terminates, the enumeration (Γ0 , Γ1 , ..., Γt ) of all sequences appearing on thetable is called a sequence-trace (of P), and such Γt is called a ﬁnal sequence; similarly, such
8

(vis(Γ0 ), vis(Γ1 ), ..., vis(Γt )) and vis(Γt ) are called a visible sequence-trace and a ﬁnal visible
sequence, respectively.
Consider Niemi-Renvall’s copy protocol for k = s = 2 (seen in Section 1.1) as an
example to be speciﬁed by using our model: it can be formally described by a quadruple(D ex , {Γex1 , Γex2 }, {q0 , q1 , q2 , q3 , q4 , q5 , qf }, Aex ) such that
Aex (q0 , vis(Γex1 )) = (q1 , {3, 4, . . . , 20})Aex (q1 , (?, ?, . . . , ?)) = (q2 , (Πex1 , F ex1 ))Aex (q2 , (?, ?, . . . , ?)) = (q3 , (Πex2 , F ex2 ))Aex (q3 , (?, ?, . . . , ?)) = (q4 , (Πex3 , F ex3 ))Aex (q4 , (?, ?, . . . , ?)) = (q5 , (Πex4 , F ex4 ))Aex (q5 , (?, ?, . . . , ?)) = (qf , {2, 3, 9, 11, 13, 15, 17, 19})
where the shuﬄe pair (Πex3 , F ex3 ) (which represents a random cut) can be deﬁned similarly
to (Πex1 , F ex1 ) and (Πex2 , F ex2 ),Πex4 = {π ∈ S20 | ∀ i ∈ {1, 4, 5, 6, 7, 8, 10, 12, 14, 16, 18, 20} π(i) = i}and PrF ex4 (π) = 1/8! for every π ∈ Πex4 . Note that vis(Γex1 ) = vis(Γex2 ), and that(Πex4 , F ex4 ) represents a shuﬄe of the eight cards.

3

Framework for Copy Protocol

In the previous section, we have constructed a formal computational model of the card-based
protocols. In this section, based on it, we deal with a framework for copying a face-downcard, by using Niemi-Renvall’s copy protocol
P NR = (D ex , {Γex1 , Γex2 }, {q0 , q1 , q2 , q3 , q4 , q5 , qf }, Aex )(speciﬁed above in Section 2.3) as an example. Note that the size of every sequence-trace(Γ0 , Γ1 , ..., Γ6 ) of P NR is equal to 7.
Before proceeding further, we deﬁne an “execution-trace” as follows. Remember thatduring an execution of a protocol P, its current sequence Γ is changing from Γ into either(i) turnT (Γ) for a turn set T or (ii) permπ (Γ) for a permutation π; we call such T or π atransformer. Enumerating such transformers τi ∈ 2{1,2,...,d} ∪ Sd together with the sequencetrace (Γ0 , Γ1 , ..., Γt ), we have the execution-trace(Γ0 , Γ1 , ..., Γt ), (τ1 , τ2 , ..., τt )of the protocol P.

3.1

Being a copy protocol

Consider the characteristics allowing the protocol P NR to make identical copies of a facedown card:• it has a suitable input set;
• it always terminates with a sequence-trace of a ﬁnite size;9• every visible sequence-trace (more speciﬁcally, the number of ♣ s in the ﬁnal visible
sequence) determines the positions at which correct copies certainly reside;• it does not touch the ﬁrst lying card.
Carrying this observation further, we obtain the following deﬁnition without loss of generality.
Deﬁnition 1. We say that a protocol P = (D, {Γ♣ , Γ♥ }, Q, A) achieves making two copies
if• the two sequences in the input set are
Γ♣ =

? ?

, , α3 , α4 , . . . , α|D|
♥ ♣

Γ♥ =

? ?

, , α3 , α4 , . . . , α|D|
♣ ♥

and

for face-up cards α3 , α4 , . . . , α|D| ;• it terminates with an execution-trace having a ﬁnite average number of sequences;• there exist two functions
f1 : (VisD )∗ → {2, 3, . . . , |D|}andf2 : (VisD )∗ → {2, 3, . . . , |D|}such that, for every sequence-trace(Γ0 , Γ1 , ..., (β1 , β2 , . . . , β|D| ))of P and its visible sequence-traceν = (vis(Γ0 ), vis(Γ1 ), ..., vis((β1 , β2 , . . . , β|D| ))),
f1 (ν) = f2 (ν) andβf1 (ν) = βf2 (ν) =where(VisD )∗ =

?
♣
?
♥

if Γ0 = Γ♣if Γ0 = Γ♥ ,(VisD )i .
i≥1

• the action function A does nothing against the ﬁrst lying card, i.e., each transformer
in every execution-trace of P is either a turn set T with 1 ∈/ T or a permutation πwith π(1) = 1.

10

Note that, as implied by the second item in Deﬁnition 1, we admit a copy protocol to
be a Las Vegas algorithm. (Actually, as seen in the last column of Table 1, some existing
protocols are Las Vegas algorithms.)
The protocol P NR satisﬁes all of the conditions in Deﬁnition 1, of course: in regard to
the third condition, it suﬃces to set
f1 (ν) = 5, f2 (ν) = 7
for any visible sequence-trace ν whose ﬁnal visible sequence has an even number of ♣ s, andf1 (ν) = 6, f2 (ν) = 8
for any ν whose ﬁnal visible sequence has an odd number of ♣ s.

3.2

Security

We next consider the security. To make an information-theoretical argument, we need todeﬁne two random variables (as below); to this end, it is necessary to take a probability
distribution on the input set U into account.
Given a protocol P = (D, U, Q, A), a probability distribution M on U is called an input
distribution for P. A protocol P together with an input distribution M for it speciﬁes theentire world; we call such a pair (M, P) a system (following the terminology in FischerWright’s communication model [5]).
Let P = (D, {Γ♣ , Γ♥ }, Q, A) be a protocol achieving making two copies, and let M be
an input distribution for P. Then, the system (M, P) induces a probability distribution
on the input set {Γ♣ , Γ♥ }, of course. Therefore, we can characterize the secret color of theunknown faced-down card (to be copied) by a random variable X (M,P) (whose superscript
is omitted if it is clear from context); X = ♣ means that the secret color is ♣, and X = ♥means that it is ♥. Similarly, we use a random variable V (M,P) (whose superscript is also
omitted if it is clear from context) to express the visible sequence-trace; V = (v0 , v1 , . . . , vt )means that we have seen each visible sequence vi , 0 ≤ i ≤ t, on the table in this order.
Note that the randomization comes from not only the input distribution M but also therandomized operations shuf Π,F (·) and rflipΦ,G (·) output by the action function A.
The two random variables X and V are suﬃcient for evaluating the security. Take theprotocol P NR as an example. (Remember that P NR fails to securely copy with probability
1/8 as mentioned in Section 1.1.) Using random variables X and V along with the (Shannon)
entropy H(·) and the conditional entropy H(·|·), we can information-theoretically write that
• H(X|V = ν) = H(X) and Pr[V = ν] = 7/8 for any visible sequence-trace ν =(v0 , v1 , . . . , v6 ) such that the ﬁnal visible sequence v6 contains at least one ♣ and at
least one ♥;• H(X|V = ν) = 0 and Pr[V = ν] = 1/8 for any ν = (v0 , v1 , . . . , v6 ) such that v6contains only cards of a single color.

4

Impossibility of Perfectly Secure Copy

In this section, we prove that there does not exist a protocol that achieves making two
copies with perfect secrecy.
We ﬁrst formally deﬁne perfectly secure copy protocols.
11

Deﬁnition 2. We say that a protocol P achieves making two copies with perfect secrecy if
it achieves making two copies, and moreover,H(X (M,P) |V (M,P) ) = H(X (M,P) )holds for any system (M, P).
We next prove that such a protocol does not exist. Roughly speaking, the idea behind
our proof is based on a simple fact: when the unknown card (to be copied) is possibly
turned over, its entropy must decrease.
Take a system (M, P NR ) of the protocol P NR with Pr[X = ♣] > 0 and Pr[X = ♥] > 0
as an example. Consider when the eight cards are revealed in the ﬁnal step, i.e., when theoperation
turn{2,3,9,11,13,15,17,19} (Γ5 )is applied, where (Γ0 , Γ1 , ..., Γ5 , Γ6 ) will be the sequence-trace. For convenience, we virtually
split the turn over operation into turn{2} (Γ5 ) andturn{3,9,11,13,15,17,19} (Γ5.5 ),that is, we focus on the case when the second (face-down) card has just been turned over.
Assume that the revealed (face-up) card is ♣? . Then, the probability that the second card
revealed now has come from the unknown card (to be copied) is exactly 1/8, and hence
Pr[X = ♣ | E] ==(1/8) · Pr[X = ♣] + (7/8) · Pr[X = ♣] · (1/2)(1/8) · Pr[X = ♣] + (7/8) · (1/2)
9 Pr[X = ♣]> Pr[X = ♣]2 Pr[X = ♣] + 7

where E is such an event. Therefore, the entropy must decrease (as formally shown below inLemma 1). Note that E is an “intermediate” event; subsequently, the remaining seven cards
are turned over, i.e., turn{3,9,11,13,15,17,19} (Γ5.5 ) is applied, and the protocol terminates witha visible sequence-trace ν such that H(X|V = ν) = H(X) or H(X|V = ν) = 0 (as describedNR
NR
NR
in the previous section), and hence we have H(X (M,P ) |V (M,P ) ) < H(X (M,P ) ).
For a random variable Z, we denote by Z −1 (z) the (maximal) event resulting in Z = z.
We say that an event E respects a random variable Z if either Z −1 (z) ⊆ E or Z −1 (z) ∩ E = ∅for any z [5]. We have the following lemma.
Lemma 1. Let Y, Z be random variables, and let E be an event respecting Z. If Pr[Y =y | E] = Pr[Y = y] for some y, then H(Y |Z) < H(Y ).
Proof. Assume that Pr[Y = y | E] = Pr[Y = y] for some y, and suppose for a contradictionthat H(Y |Z) = H(Y ). Then, Y and Z are independent, and hence Pr[Y = y, Z = z] =Pr[Y = y] Pr[Z = z] for any z. Since E respects Z, there exists η such that {Z −1 (z) | z ∈ η}
partitions E. Thus,
Pr[Y = y | E] =Pr[Y = y, E]=
Pr[E]z∈η Pr[Y = y, Z = z]z∈η Pr[Z = z]which contradicts Pr[Y = y | E] = Pr[Y = y].
We are now ready to prove our theorem.
12= Pr[Y = y],Theorem 1. There exists no protocol that achieves making two copies with perfect secrecy.
Proof. Let (M, P) be a system of a protocol P = (D, {Γ♣ , Γ♥ }, Q, A) achieving making
two copies, such that Pr[X = ♣] > 0 and Pr[X = ♥] > 0. Choose (and ﬁx) an arbitrary
execution-trace of P whose sequence-trace (Γ0 , Γ1 , ..., Γt ) satisﬁes Γ0 = Γ♣ . For every
sequence Γi , we denote by posi the position of the unknown card (which is the second
lying card ♣? in the initial sequence Γ0 = Γ♣ ). That is, we set pos0 = 2, and for every i,
1 ≤ i ≤ t, recursively deﬁne posi = π(posi−1 ) if the i-th transformer is a permutation π;
and posi = posi−1 otherwise.
/ T , i.e.,
Suppose that every i-th transformer which is a turn set T satisﬁes posi−1 ∈the unknown card has never been turned over. Then, if we started the protocol P fromthe other sequence Γ♥ (contained in the input set) instead of Γ♣ , we would necessarily
have a case where the resulting sequence-trace would be (Γ♥ , Γ1 , ..., Γt ). Since their visible
sequence-traces are the same, namely(vis(Γ♣ ), vis(Γ1 ), . . . , vis(Γt )) = (vis(Γ♥ ), vis(Γ1 ), . . . , vis(Γt )),we could not determine where desired identical copies are, a contradiction. Hence, there
must exist an i-th transformer which is a turn set T such that posi−1 ∈ T .
Focus on the case where such a transformer, namely a turn set T , ﬁrst appears, andassume that such T appears as the -th transformer. Hence, turnT (Γ−1 ) = Γ . Without lossof generality, one may assume that T is a singleton set, i.e., T = {k} for some k. Then, thek-th lying card in Γ−1 is ♣? , and that in Γ is ♣? . We now consider an event, denoted by E,
in which the ﬁrst ( + 1) visible sequences are the same as vis(Γ♣ ), vis(Γ1 ), . . . , vis(Γ ). Notethat the event E respects the random variable V (expressing visible sequence-traces). Also,
denote by E − the event that the ﬁrst visible sequences are vis(Γ♣ ), vis(Γ1 ), . . . , vis(Γ−1 ).
Within the event E − , we consider two events Pos ⊆ E − and O♣ ⊆ (E − −Pos): Pos represents
that “the k-th lying card in the -th sequence (counting from 1) is the unknown card,” andO♣ represents that “it comes from other cards and is ♣? .” Then, we have
Pr[Pos] Pr[X = ♣] + (1 − Pr[Pos]) Pr[X = ♣] Pr[O♣ ]Pr[Pos] Pr[X = ♣] + (1 − Pr[Pos]) Pr[O♣ ]> Pr[X = ♣].

Pr[X = ♣ | E] =Note that the inequality holds even when Pr[O♣ ] = 0. Hence, by Lemma 1 we have
H(X|V ) < H(X).

5Conclusion

In this paper, we constructed a rigorous mathematical model of card-based cryptographic
protocols. Based on this general computational model, we showed that it is impossible to
make identical copies of a face-down card with perfect secrecy.
Since our constructed computational model is rather general, we believe that it can beused to ﬁnd another impossibility result, or to show the optimality of a certain protocol.
For example, as listed in Table 1, six cards are suﬃcient for securely computing AND
in a committed format [8], and it is open to answer the question whether there exists a“committed format” AND protocol that requires fewer than six cards. We hope that our
computational model can provide unambiguous answers to such questions in the future.
13

The model is also expected to enable us to discuss the “time complexity” and “shuﬄecomplexity” of protocols more precisely.
As seen, the cards considered in our model (as well as in previous works [2, 3, 6, 7,
8, 9, 11, 13]) have no “polarity,” that is, we never put them upside down like ♣♥ .
Introducing polarity or rotation of a card might be one intriguing direction of future works.
♣♥

Acknowledgments
This work was supported by JSPS KAKENHI Grant Number 23700007.

References[1] J. Balogh, J. A. Csirik, Y. Ishai, and E. Kushilevitz, “Private computation using a
PEZ dispenser,” Theoretical Computer Science, vol. 306, pp. 69–84, 2003.
[2] B. den Boer, “More eﬃcient match-making and satisﬁability: the ﬁve card trick,”Proc. EUROCRYPT ’89, Lecture Notes in Computer Science, vol. 434, pp. 208–217,
Springer-Verlag, 1990.
[3] C. Crépeau and J. Kilian, “Discreet solitary games,” Proc. CRYPTO ’93, Lecture
Notes in Computer Science, vol. 773, pp. 319–330, Springer-Verlag, 1994.
[4] R. Fagin, M. Naor, and P. Winkler, “Comparing information without leaking it,”Communications of the ACM, vol. 39, no. 5, pp. 77–85, 1996.
[5] M. J. Fischer and R. N. Wright, “Bounds on secret key exchange using a random dealof cards,” Journal of Cryptology, vol. 9, no. 2, pp. 71–99, 1996.
[6] T. Mizuki, I. K. Asiedu, and H. Sone, “Voting with a logarithmic number of cards,”
Proc. UCNC 2013, Lecture Notes in Computer Science, Springer-Verlag, vol. 7956,
pp. 162–173, 2013.
[7] T. Mizuki, M. Kumamoto, and H. Sone, “The ﬁve-card trick can be done with four
cards,” Proc. ASIACRYPT 2012, Lecture Notes in Computer Science, Springer-Verlag,
vol. 7658, pp. 598–606, 2012.
[8] T. Mizuki and H. Sone, “Six-card secure AND and four-card secure XOR,” Proc.
Frontiers in Algorithmics (FAW 2009), Lecture Notes in Computer Science, vol. 5598,
pp. 358–369, Springer-Verlag, 2009.
[9] T. Mizuki, F. Uchiike, and H. Sone, “Securely computing XOR with 10 cards,” Australasian Journal of Combinatorics, vol. 36, pp.279-293, 2006.
[10] T. Moran and M. Naor, “Polling with physical envelopes: a rigorous analysis of ahuman-centric protocol,” Proc. EUROCRYPT 2006, Lecture Notes in Computer Science, vol. 4004, pp. 88–108, Springer-Verlag, 2006.
[11] V. Niemi and A. Renvall, “Secure multiparty computations without computers,” Theoretical Computer Science, vol. 191, pp. 173–183, 1998.

14

[12] H. Stamer, “Eﬃcient electronic gambling: an extended implementation of the toolbox
for mental card games,” Proc. Western European Workshop on Research in Cryptology(WEWoRC 2005), Lecture Notes in Informatics, vol. P-74, pp. 1–12, 2005.
[13] A. Stiglic, “Computations with a deck of cards,” Theoretical Computer Science,
vol. 259, pp. 671–678, 2001.
[14] A. M. Turing, “On computable numbers with an application to the Entscheidungsproblem,” Proc. London Math. Soc., vol. 42, pp. 230–265, 1936.

15