Five-Card Secure Computations
Using Unequal Division Shuffle?
Akihiro Nishimura1 , Takuya Nishida1 , Yu-ichi Hayashi2 , Takaaki Mizuki3 , andHideaki Sone3
1

Sone-Mizuki Lab., Graduate School of Information Sciences, Tohoku University
6-3 Aramaki-Aza-Aoba, Aoba, Sendai 980-8578, Japan
2
Faculty of Engineering, Tohoku Gakuin University
1-13-1 Chuo, Tagajo, Miyagi 985-8537, Japan
3
Cyberscience Center, Tohoku University
6-3 Aramaki-Aza-Aoba, Aoba, Sendai 980-8578, Japantm-paper+card5copw[atmark]g-mail.tohoku-university.jp

Abstract. Card-based cryptographic protocols can perform secure computation of Boolean functions. Cheung et al. recently presented an elegant
protocol that securely produces a hidden AND value using five cards;
however, it fails with a probability of 1/2. The protocol uses an unconventional shuffle operation called unequal division shuffle; after a sequenceof five cards is divided into a two-card portion and a three-card portion,these two portions are randomly switched. In this paper, we first showthat the protocol proposed by Cheung et al. securely produces not onlya hidden AND value but also a hidden OR value (with a probability of
1/2). We then modify their protocol such that, even when it fails, we canstill evaluate the AND value. Furthermore, we present two five-card copy
protocols using unequal division shuffle. Because the most efficient copy
protocol currently known requires six cards, our new protocols improveupon the existing results.
Keywords: Cryptography, Card-based protocols, Card games, Cryptography without computers, Real-life hands-on cryptography, Secure
multi-party computations

1

Introduction

Suppose that Alice and Bob have Boolean values a ∈ {0, 1} and b ∈ {0, 1},
respectively, each of which describes his/her private opinion (or something similar),and they want to conduct secure AND computation, i.e., they wish to know
only the value of a ∧ b. In such a situation, a card-based cryptographic protocol
is a convenient solution. Many such protocols have already been proposed (seeTable 1), one of which can be selected by them for secure AND computation. For
example, if they select the six-card AND protocol [6], they can securely produce?

This paper appears in Proceedings of TPNC 2015. The final publication is available
at Springer via http://dx.doi.org/10.1007/978-3-319-26841-5 9.

2

A. Nishimura, T. Nishida, Y. Hayashi, T. Mizuki, and H. Sonea hidden value of a ∧ b using six playing cards, e.g., ♣ ♣ ♣ ♥ ♥ ♥ , along witha “random bisection cut.”
Recently, Cheung et al. presented an elegant protocol that securely produces
a hidden AND value using only five cards ( ♣ ♣ ♣ ♥ ♥ ); however, it fails
with a probability of 1/2 [2] (we refer to it as Cheung’s AND protocol in thispaper). The protocol uses an unconventional shuffling operation that we referto as “unequal division shuffle”; after a sequence of five cards is divided intoa two-card portion and a three-card portion, these two portions are randomly
switched. The objective of this paper is to improve Cheung’s AND protocol andpropose other efficient protocols using unequal division shuffle.
This paper begins by presenting some notations related to card-based protocols.
Table 1. Known card-based protocols for secure computation# of # of Type of Avg. # Failurecolors cards shuffle of trials rate
◦ Secure AND in a non-committed format
den Boer [1]

2

5

RC

1

0

Mizuki-Kumamoto-Sone [5]

2

4

RBC

1

0

◦ Secure AND in a committed format
Crépeau-Kilian [3]

4

10

RC

6

0

Niemi-Renvall [8]

2

12

RC

2.5

0

Stiglic [10]

2

8

RC

2

0

Mizuki-Sone [6]

2

6

RBC

1

0

Cheung et al. [2] (§2.3)

2

5

UDS

1

1/2

◦ Secure XOR in a committed format
Crépeau-Kilian [3]

4

14

RC

6

0

Mizuki-Uchiike-Sone [7]

2

10

RC

2

0

Mizuki-Sone [6]
2
4
RBC
1
0
RC = Random Cut, RBC = Random Bisection Cut,
UDS = Unequal Division Shuffle

1.1

Preliminary Notations

Throughout this paper, we assume that cards satisfy the following properties.
1. All cards of the same type (black ♣ or red ♥ ) are indistinguishable fromone another.
2. Each card has the same pattern ? on its back side, and hence, all face-downcards are indistinguishable from one another.

Five-Card Secure Computations Using Unequal Division Shuffle3

We define the following encoding scheme to deal with a Boolean value:♣ ♥ = 0, ♥ ♣ = 1.

(1)

Given a bit x ∈ {0, 1}, when a pair of face-down cards ? ? describes the valueof x with encoding scheme (1), it is called a commitment to x and is expressed as? ? .
| {z }(2)x

For a commitment to x ∈ {0, 1}, we sometimes write?
?
|{z} |{z}x0x1instead of expression (2), where x0 := x and x1 := x. In other words, wesometimes use a one-card encoding scheme, ♣ = 0, ♥ = 1, for convenience.
Given commitments to players’ private inputs, a card-based protocol is supposed to produce a sequence of cards as its output. The committed protocols
listed in Table 1 produce their output as a commitment. For example, any AND
protocol outputs? ?
| {z }a∧b

from input commitments to a and b. On the other hand, non-committed protocols
produce their output in another form.
Hereafter, for a sequence consisting of n ∈ IN cards, each card of the sequence
is sequentially numbered from the left (position 1, position 2, . . . , position n),
e.g.,
1

2

3

n

? ♣ ♥ ··· ? .
1.2

Our Results

As mentioned above, given commitments to Alice’s bit a and Bob’s bit b together
with an additional card ♣ , Cheung’s AND protocol produces a commitment
to a ∧ b with a probability of 1/2; when it fails, the players have to create their
input commitments again. This paper shows that in the last step of Cheung’s
AND protocol, a commitment to the OR value a ∨ b is also obtained when the
protocol succeeds in producing a commitment to a ∧ b. Next, we show that, evenwhen the protocol fails, we can still evaluate the AND value (more precisely, any
Boolean function) by slightly modifying the last step of the protocol. Thus, theimproved protocol never fails to compute the AND value.
Furthermore, we present two five-card copy protocols using unequal division
shuffle. Because the most efficient copy protocol currently known requires six
cards [6], our new protocols improve upon the existing results in terms of thenumber of required cards, as shown in Table 2. Note that our protocols require
an average of two trials.

4

A. Nishimura, T. Nishida, Y. Hayashi, T. Mizuki, and H. Sone
Table 2. Protocols for making two copied commitments# of # of Type of Avg. # Failurecolors cards shuffle of trials rateCrépeau-Kilian [3]

2

8

RC

1

0

Mizuki-Sone [6]

2

6

RBC

1

0

Ours (§4)

2

5

UDS

2

0

The remainder of this paper is organized as follows. Section 2 first introduces
Cheung’s AND protocol along with known shuffle operations and then presents
a more general definition of unequal division shuffle. Section 3 describes ourslight modification to the last step of Cheung’s AND protocol to expand its
functionality. Section 4 proposes two new copy protocols that outperform theprevious protocols in terms of the number of required cards. Finally, Section 5summarizes our findings and concludes the paper.

2

Card Shuffling Operations and Known Protocol

In this section, we first introduce a random bisection cut [6]. Then, we give ageneral definition of unequal division shuffle. Finally, we introduce Cheung’s
AND protocol [2].
2.1

Random Bisection Cut

Suppose that there is a sequence of 2m face-down cards for some m ∈ IN:
◦

•

}|
{z
}|
{
z
? ? ··· ? ? ? ··· ? .
|
{z
}|
{z
}
m cards

m cards

Then, a random bisection cut [6] (denoted by [·|·])hi? ? ··· ? ? ? ··· ?
means that we bisect the sequence and randomly switch the two portions (of sizem). Thus, the result of the operation will be either
◦

•

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

•

◦

z
}|
{z
}|
{
or ? ? · · · ? ? ? · · · ? ,where each occurs with a probability of exactly 1/2.
The random bisection cut enables us to significantly reduce the number ofrequired cards and trials for secure computations. See Table 1 again; the four-card
non-committed AND protocol [5], the six-card committed AND protocol [6], andFive-Card Secure Computations Using Unequal Division Shuffle5

the four-card committed XOR protocol [6] all employ random bisection cuts.
Using random bisection cuts, we can also construct a six-card copy protocol[6] (as seen in Table 2), adder protocols [4], protocols for any three-variable
symmetric functions [9], and so on.
Whereas the most efficient committed AND protocol [6] currently known (thatalways works) uses a random bisection cut and requires six cards as stated above,
Cheung et al. introduced unequal division shuffle whereby they constructed afive-card committed AND protocol that works with a probability of 1/2. Its
details are presented in the next two subsections.
2.2

Unequal Division Shuffle

Here, we present a formal definition of unequal division shuffle, which first
appeared in Cheung’s AND protocol [2].
Suppose that there is a sequence of ` ≥ 3 (` ∈ IN) face-down cards:? ? ··· ? .
|{z}` cards

Divide it into two portions of unequal sizes, say, j cards and k cards, wherej + k = ` , j 6= k, as follows:` cards}|{z? ? ··· ? ? ? ··· ? .
|
{z
}|
{z
}
j cards

k cards

We consider an operation that randomly switches these two portions of unequal
sizes; we refer to it as unequal division shuffle or (j, k)-division shuffle (denotedby [·|·]) :hi? ? ··· ?
? ? ··· ? .
|
{z
} |
{z
}
j cards

k cards

Thus, the result of the operation will be either? ? · · · ? ? ? · · · ? or ? ? · · · ? ? ? · · · ? ,
|
{z
}|
{z
}
|
{z
}|
{z
}
j cards

k cards

k cards

j cards

where each case occurs with a probability of exactly 1/2.
We demonstrate an implementation of unequal division shuffle in Appendix
A.
2.3

Cheung’s AND Protocol

In this subsection, we introduce Cheung’s AND protocol. It requires an additionalcard ♣ to produce a commitment to a ∧ b from two commitments? ? ? ?
| {z } | {z }
a

b

6

A. Nishimura, T. Nishida, Y. Hayashi, T. Mizuki, and H. Sone

placed by Alice and Bob, respectively. As mentioned in Section 2.2, the protocol
uses unequal division shuffle, specifically (2, 3)-division shuffle, as follows.
1. Arrange the cards of the two input commitments and the additional card as? ? ? ? ? .
|{z} |{z} |{z} |{z} |{z}
♣

a0

a1

b0

b1

2. Apply (2, 3)-division shuffle:
h

? ?

i
? ? ? .

3. Reveal the card at position 1.
(a) If the card is ♣ , then the cards at positions 2 and 3 constitute a
commitment to a ∧ b:
♣ ? ? ? ? .
| {z }a∧b(b) If the card is ♥ , then Alice and Bob create input commitments again
to restart the protocol.
This is Cheung’s AND protocol. As seen from step 3, it fails with a probabilityof 1/2 (in this case, we have to start from scratch). We verify the correctness ofthe protocol in the next section.

3

Improved Cheung’s AND Protocol

In this section, we discuss Cheung’s AND protocol and change its last step todevelop an improved protocol.
Here, we confirm the correctness of Cheung’s AND protocol. As discussed in
Section 2.3, the input to Cheung’s AND protocol consists of commitments toa, b ∈ {0, 1} along with an additional card ♣ . There are two possibilities due tothe outcome of (2, 3)-division shuffle:?
?
?
?
? and ?
?
?
?
? .
|{z} |{z} |{z} |{z} |{z}|{z} |{z} |{z} |{z} |{z}
a0

♣

a1

b0

b1

a1

b0

b1

a0

♣

We enumerate all possibilities of input and card sequences after step 2 of the
protocol in Table 3 (recall encoding scheme (1)). Looking at the cards at positions
2 and 3 when the card at position 1 is ♣ in Table 3, we can easily confirm thecorrectness of the protocol, i.e., the cards at positions 2 and 3 surely constitute a
commitment to a ∧ b.
In the remainder of this section, we analyze Cheung’s AND protocol further
to obtain an improved protocol.

Five-Card Secure Computations Using Unequal Division Shuffle

7

Table 3. All possibilities of input and card sequences after step 2
Input
Card sequences(a, b) a0 ♣ a1 b0 b1 a1 b0 b1 a0 ♣3.1

(0, 0)♣ ♣ ♥ ♣ ♥ ♥ ♣ ♥ ♣ ♣(0, 1)♣ ♣ ♥ ♥ ♣ ♥ ♥ ♣ ♣ ♣(1, 0)♥ ♣ ♣ ♣ ♥ ♣ ♣ ♥ ♥ ♣(1, 1)♥ ♣ ♣ ♥ ♣ ♣ ♥ ♣ ♥ ♣Bonus Commitment to OR

When we succeed in obtaining a commitment to a ∧ b, i.e., when the card at
position 1 is ♣ in the last step of Cheung’s AND protocol, we are also able tosimultaneously obtain a commitment to the OR value a ∨ b. Thus, as indicatedin Table 3, if the card at position 1 is ♣ , then the cards at positions 4 and 5
constitute a commitment to a ∨ b.
3.2

In Case of Failure

Suppose that the card at position 1 is ♥ in the last step of Cheung’s AND
protocol. This means that the AND computation failed and we have to startfrom scratch, i.e., Alice and Bob need to create their private input commitments
again. However, we show that they need not do so: they can evaluate the AND
value even when Cheung’s AND protocol fails, as follows.
From Table 3, if the card at position 1 is ♥ , the sequence of five cards♥ ? ? ? ?

(3)

is one of the four possibilities shown in Table 4, depending on the value of (a, b).
Table 4. Possible sequences when Cheung’s AND protocol fails
Input (a, b) Sequence of five cards(0, 0)♥ ♣ ♥ ♣ ♣(0, 1)♥ ♥ ♣ ♣ ♣(1, 0)♥ ♣ ♣ ♣ ♥(1, 1)♥ ♣ ♣ ♥ ♣Therefore, the card at position 4 indicates the value of a ∧ b, i.e., if the card
at position 4 is ♣ , then a ∧ b = 0, and if the card is ♥ , then a ∧ b = 1. Notethat opening the card does not reveal any information about the inputs a and b

8

A. Nishimura, T. Nishida, Y. Hayashi, T. Mizuki, and H. Sone

besides the value of a ∧ b. Thus, Cheung’s AND protocol does not fail to compute
the AND value.
Actually, we can compute any Boolean function f (a, b) in a non-committed
format, given the sequence (3) above, as follows. Note that, as seen in Table 4, theposition of the face-down card ♥ (which is between 2 and 5) uniquely determines
the value of the input (a, b). We shuffle all cards at positions corresponding tof (a, b) = 1 (possibly one card as in the case of f (a, b) = a ∧ b) and reveal all thesecards. If ♥ appears anywhere, then f (a, b) = 1; otherwise, f (a, b) = 0. Thus, we
can evaluate the desired function (in a non-committed format).
3.3

Improved Protocol

From the discussion above, we have the following improved protocol.
1. Arrange the five cards as follows:? ? ? ? ? .
|{z} |{z} |{z} |{z} |{z}
a0

♣

a1

b0

b1

2. Apply (2, 3)-division shuffle:hi? ? ? .

? ?

3. Reveal the card at position 1.
(a) If the card is ♣ , then the cards at positions 2 and 3 constitute a
commitment to a ∧ b; moreover, the cards at positions 4 and 5 constitutea commitment to a ∨ b:
♣ ? ? ? ? .
| {z } | {z }
a∧b

a∨b

(b) If the card is ♥ , then we can evaluate any desired Boolean function
f (a, b). Shuffle all cards at positions corresponding to f (a, b) = 1 andreveal them. If ♥ appears, then f (a, b) = 1; otherwise, f (a, b) = 0.

4

Five-Card Copy Protocols

In this section, we focus on protocols for copying a commitment.
From Table 2, using the six-card copy protocol [6], a commitment to bita ∈ {0, 1} can be copied with four additional cards:? ? ♣ ♣ ♥ ♥ → ? ? ? ? ♣ ♥.
| {z }| {z } | {z }aaaThis is the most efficient protocol currently known for copying. In contrast,
we prove that three additional cards (two ♣ s and one ♥ ) are sufficient by
proposing a five-card copy protocol using unequal division shuffle. We also propose
another copy protocol that has fewer steps by considering a different shuffle.

Five-Card Secure Computations Using Unequal Division Shuffle

4.1

9

Copy Protocol Using Unequal Division Shuffle

Given a commitment? ?
| {z }
atogether with additional cards ♣ ♣ ♥ , our protocol makes two copied commitments, as follows.
1. Arrange the five cards as? ? ? ? ? .
|{z} |{z} |{z} |{z} |{z}
♣

♥

a0

a1

♣

2. Apply (2, 3)-division shuffle:
h

? ?

i
? ? ? .

3. Rearrange the sequence of five cards as? ? ? ? ?
PP 
q
+PP

? ? ? ? ? .
4. Reveal the card at position 5.
(a) If the card is ♣ , then we have two commitments to a as follows:? ? ? ? ♣.
| {z } | {z }aa(b) If the card is ♥ , then we have
? ? ? ? ♥.
| {z }a

Swap the cards at positions 1 and 2 to obtain a commitment to a. Afterrevealing the cards at positions 3 and 4 (which must be ♣ ♣ ), returnto step 1.
After step 3, there are two possibilities due to the shuffle outcome: thesequence of five cards is either ♣ ♥ ♣ a1 a0 or ♥ ♣ a0 ♣ a1 . Table 5 enumerates
all possibilities of input and card sequences after step 3 of the protocol. As canbe easily seen in the table, we surely have two copied commitments in step 4(a).
Note that opening the card at position 5 does not reveal any information about
the input a. Thus, we have designed a five-card copy protocol that improves upon
the previous results in terms of the number of required cards. It should be notedthat the protocol is a Las Vegas algorithm with an average of two trials.

10

A. Nishimura, T. Nishida, Y. Hayashi, T. Mizuki, and H. Sone
Table 5. Possible sequences after step 3 of our first copy protocol
Input
a

4.2

Card sequences♣ ♥ ♣ a1 a0 ♥ ♣ a0 ♣ a10

♣ ♥ ♣ ♥ ♣♥ ♣ ♣ ♣ ♥1

♣ ♥ ♣ ♣ ♥♥ ♣ ♥ ♣ ♣Copy Protocol Using Double Unequal Division Shuffle

In this subsection, we reduce the number of steps for achieving copy computation
by modifying the unequal division shuffle approach.
Remember that (2,3)-division shuffle changes the order of the two portions:
1 2 . 3 4 5
3 4 5 . 1 2? ? .. ? ? ? → ? ? ? .. ? ? .

Here, we consider a further division of the three-card portion:
3 4 . 5
? ? .. ?

5 . 3 4
1 2
? ? → ? .. ? ?

1

2

? ? .

Thus, given a sequence of five cards
1

2

3

4

5

? ? ? ? ? ,a shuffle operation resulting in either
1

2

3

4

5

5

or

? ? ? ? ?

3

4

1

2

? ? ? ? ?

is called double unequal division shuffle.
Using such a shuffle, we can avoid rearranging the cards in step 3 of the
protocol presented in Section 4.1.
1. Arrange the five cards as? ? ? ? ? .
|{z} |{z} |{z} |{z} |{z}
a0

♣

♥

♣

a1

2. Apply double unequal division shuffle:
h

? ?

i
.
? .. ? ? .

3. Reveal the card at position 1.
(a) If the card is ♣ , then we have two commitments to a:♣ ? ? ? ? .
| {z } | {z }aaFive-Card Secure Computations Using Unequal Division Shuffle

11(b) If the card is ♥ , then we have
♥ ? ? ? ? .
| {z }a

Swap the cards at positions 2 and 3 to obtain a commitment to a. Afterrevealing the cards at positions 4 and 5, return to step 1.
This protocol has two possibilities after step 2: the sequence of five cards
is either a0 ♣ ♥ ♣ a1 or a1 ♥ ♣ a0 ♣ . Table 6 confirms the correctness of the
protocol.
Table 6. Possible sequences after step 2 of our second protocol
Input
Card sequences0aa ♣ ♥ ♣ a1 a1 ♥ ♣ a0 ♣0♣ ♣ ♥ ♣ ♥♥ ♥ ♣ ♣ ♣1

♥ ♣ ♥ ♣ ♣♣ ♥ ♣ ♥ ♣Although this protocol requires fewer steps, we are not sure whether double
unequal division shuffle can be easily implemented by humans.

5

Conclusion

In this paper, we discussed the properties of the AND protocol designed by
Cheung et al. and proposed an improved protocol. Although their original
protocol produces only a commitment to the AND value with a probability of
1/2, our improved protocol either produces commitments to the AND and OR
values or evaluates any Boolean function. Thus, the improved protocol does not
fail at all.
Furthermore, we proposed two five-card copy protocols that can securely copy
an input commitment using three additional cards. Each of our protocols uses
unequal division shuffle. Because the most efficient copy protocol currently known
requires six cards, our new protocols improve upon the existing results in termsof the number of required cards.
An open problem is whether unequal division shuffle enables us to compute
any other function using fewer cards than the existing protocols.

A

How to Perform Unequal Division Shuffle

Here, we discuss how to implement unequal division shuffle. We consider the card
cases shown in Figure 1. Each case can store a deck of cards and has two sliding

12

A. Nishimura, T. Nishida, Y. Hayashi, T. Mizuki, and H. Sone

covers, an upper cover and a lower cover. We assume that the weight of a deckof cards is negligible compared to the case. To apply unequal division shuffle, westow each portion in such a case and shuffle these two cases. Then, the cases arestacked one on top of the other. Removing the two middle sliding covers resultsin the desired sequence.

Fig. 1. Card cases suited for unequal division shuffle

Acknowledgments
This work was supported by JSPS KAKENHI Grant Numbers 25289068 and26330001.

References
1. den Boer, B.: More efficient match-making and satisfiability: the five card trick. In:
Quisquater, J.J., Vandewalle, J. (eds.) Advances in Cryptology — EUROCRYPT’89, Lecture Notes in Computer Science, vol. 434, pp. 208–217. Springer Berlin
Heidelberg (1990)
2. Cheung, E., Hawthorne, C., Lee, P.: CS 758 project: secure computation with playing cards. http://csclub.uwaterloo.ca/˜cdchawth/static/secure playing cards.pdf(2013), accessed: 2015-06-22
3. Crépeau, C., Kilian, J.: Discreet solitary games. In: Stinson, D.R. (ed.) Advancesin Cryptology — CRYPTO ’93, Lecture Notes in Computer Science, vol. 773, pp.
319–330. Springer Berlin Heidelberg (1994)
4. Mizuki, T., Asiedu, I.K., Sone, H.: Voting with a logarithmic number of cards.
In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds.) Unconventional
Computation and Natural Computation, Lecture Notes in Computer Science, vol.
7956, pp. 162–173. Springer Berlin Heidelberg (2013)
5. Mizuki, T., Kumamoto, M., Sone, H.: The five-card trick can be done with four
cards. In: Wang, X., Sako, K. (eds.) Advances in Cryptology — ASIACRYPT
2012, Lecture Notes in Computer Science, vol. 7658, pp. 598–606. Springer Berlin
Heidelberg (2012)
6. Mizuki, T., Sone, H.: Six-card secure AND and four-card secure XOR. In: Deng, X.,
Hopcroft, J.E., Xue, J. (eds.) Frontiers in Algorithmics, Lecture Notes in Computer
Science, vol. 5598, pp. 358–369. Springer Berlin Heidelberg (2009)
7. Mizuki, T., Uchiike, F., Sone, H.: Securely computing XOR with 10 cards. The
Australasian Journal of Combinatorics 36, 279–293 (2006)

Five-Card Secure Computations Using Unequal Division Shuffle

13

8. Niemi, V., Renvall, A.: Secure multiparty computations without computers. Theoretical Computer Science 191(1–2), 173–183 (1998)
9. Nishida, T., Mizuki, T., Sone, H.: Securely computing the three-input majority
function with eight cards. In: Dediu, A.H., Martı́n-Vide, C., Truthe, B., VegaRodrı́guez, M.A. (eds.) Theory and Practice of Natural Computing, Lecture Notes
in Computer Science, vol. 8273, pp. 193–204. Springer Berlin Heidelberg (2013)
10. Stiglic, A.: Computations with a deck of cards. Theoretical Computer Science259(1–2), 671–678 (2001)