Securely Computing the Three-Input Majority Function with
Eight Cards∗
Takuya Nishida

Takaaki Mizuki

Hideaki Sone

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

Abstract
Assume that Alice, Bob and Carol, each of whom privately holds a one-bit input,
want to learn the value of the majority function of their inputs without revealing moreof their own secret inputs than is necessary. In this paper, we show that such a securemajority computation can be done with a deck of real cards; speciﬁcally, the threeplayers can learn only the majority of their inputs using eight physical cards—four
black cards and four red cards—with identical backs.

1

Introduction

Assume that there are three players, Alice, Bob and Carol, who privately hold one-bit
inputs a ∈ {0, 1}, b ∈ {0, 1} and c ∈ {0, 1}, respectively. The private inputs could be, forexample, their YES/NO answers (held in mind) regarding their support for some new plan.
In such a case, majority voting is often conducted to ﬁnd the majority of their answers,
and sometimes it is not preferable to reveal all of the individual inputs. Thus, we assume
that Alice, Bob and Carol all want to learn the value of the majority function maj(a, b, c)of their inputs a, b, c ∈ {0, 1} without revealing more of their own private inputs than isnecessary, i.e., they wish to know only the value of

defmaj(a, b, c) =if a + b + c ≥ 2;
if a + b + c ≤ 1.

1
0Note thatmaj(a, b, c) = (a ∧ b) ∨ (b ∧ c) ∨ (c ∧ a).
In this paper, we show that such a secure majority computation can be conductedusing a deck of ‘real’ cards; speciﬁcally, it can be done using eight physical cards—four
black cards ♣ ♣ ♣ ♣ and four red cards ♥ ♥ ♥ ♥ —with identical backs ( ? ). As
shown below, our secure majority computation, which is a kind of cryptographic task,
relies on simple properties of physical cards; we do not need a conventional computer orcommunication network system.
This paper starts with a review of card-based cryptographic protocols.
∗

This paper appears in Proceedings of TPNC 2013.
www.springerlink.com.

1

The original publication is available at1.1

Card-Based Cryptographic Protocols

Card-based cryptographic protocols enable us to perform secure computations. The mainstream research on secure computations (e.g. [5, 13]) initiated by the seminal work of
Yao [15] usually aims to implement protocols on computers communicating with eachother via network systems. In contrast, card-based protocols require only a small deckof cards, which is portable, handy and inexpensive, and furthermore, needs no electricity.
Also, it is easy for even non-specialists to understand why card-based protocols can compute functions properly while maintaining secrecy. Considering the fact that, even in thedigital era, elections are often conducted with physical paper ballots, we believe that physical implementations of secure computations are still quite important (e.g. [1, 6, 10, 11]).
We ﬁrst mention the properties of the cards appearing in this paper. All cards of thesame type ( ♣ or ♥ ) are assumed to be indistinguishable from one another. We use ? todenote a card lying face down. We also assume that the backs ? of all cards are identical.
To deal with Boolean values, we use the following encoding:♣ ♥ = 0, ♥ ♣ = 1.

(1)

Next, we deﬁne a “commitment.” Given a bit x ∈ {0, 1}, a pair of face-down cards? ? whose value is equal to x (according to the encoding rule (1) above) is called acommitment to x and is expressed as? ?.

  
x

Note that swapping the two cards constituting a commitment to a bit x results in acommitment to negation x̄:  

? ? → ? ? → ? ?.

    

xx̄

Thus, a secure NOT operation is trivial.
Several card-based protocols have been described in the literature for securely computing other operations such as AND, XOR and Adder, as listed in Table 1. There are
two types of protocols with regard to output format. The ﬁrst two protocols in Table 1
produce their outputs (the value of a ∧ b) publicly, whereas the remaining nine protocols
produce their outputs in a committed format, i.e., their output is described as a sequencesuch as? ? and ? ?
    

a∧b

a⊕b

following the encoding rule (1).
In addition to the protocols listed in Table 1, there are copy protocols, one of which is
introduced later, in Section 2.3.

2

Table 1: Known card-based protocols for secure computation.
# of colors # of cards Avg. # of trials◦ Secure AND in a non-committed format
den Boer [3]2
51
Mizuki-Kumamoto-Sone [7]241◦ Secure AND in a committed format
Crépeau-Kilian [2]4106
Niemi-Renvall [11]212
2.5
Stiglic [14]282Mizuki-Sone [8] (§2.2)
2
6
1◦ Secure XOR in a committed format
Crépeau-Kilian [2]4146Mizuki-Uchiike-Sone [9]2102
Mizuki-Sone [8]241◦ Secure Half Adder in a committed format
Mizuki-Asiedu-Sone [6]281◦ Secure Full Adder in a committed format
Mizuki-Asiedu-Sone [6]
2
10
1

1.2

Our Results

Recall our goal: given three commitments? ? ? ? ? ?,

        abc

we desire to obtain a commitment? ?

  

maj(a,b,c)

to the majority. As mentioned in the previous subsection, the card-based protocol enables
us to perform secure computations of NOT, AND and XOR in a committed format as wellas to securely copy commitments. Consequently, it is well known that any function canbe securely computed using some number of cards. In fact, using the existing protocols(which are described later in Section 2), we can construct a trivial protocol for securely
computing the majority function maj(a, b, c), although doing so needs eight additionalcards, by using 14 cards in total (including the six cards for the three commitments), as
shown in Section 3.
In contrast, this paper shows that such a secure majority computation can be donewith only two additional cards, namely eight cards in total (as mentioned before). Our
novel protocol is presented in Section 4. This paper concludes in Section 5 with somediscussions and open problems.

3

2

Known Protocols

In this section, after explaining a shuﬄing operation called a “random bisection cut,” weintroduce an existing AND protocol and an existing copy protocol [8] for our use later(and for the readers to become familiar with card-based protocols).

2.1

Random Bisection Cuts

A random bisection cut was invented in [8]. We demonstrate it by taking six cards as an
example.
1. Assume that there are six cards as follows:? ? ? ? ? ?.
2. Bisect the deck of cards, and let the two sections be α and β:? ? ? ? ? ?.

     αβ3. Shift α and β randomly:
shift



 ? ? ?.
? ? ?   
α  
β

4. After applying such a random shift, the cards are either in their initial state or in ashifted state, as follows:? ? ? ? ? ? or ? ? ? ? ? ? ,     αβ     βαeach of which occurs with probability of exactly 1/2.
This kind of shuﬄing is referred to as a random bisection cut denoted by [ · | · ]. Belowis the expression of a random bisection cut for six cards:


2.2




? ? ?? ? ? .

The Six-Card AND Protocol

Using the random bisection cut, we can construct a six-card AND protocol [8] that securely
computes the function f (a, b) = a ∧ b with a total of six cards: three ♣ s and three ♥ s.
Before going into the details of the protocol, we deﬁne two operations, get and shift.
Given a pair of bits (x, y), we deﬁne
get0 (x, y) = x;get1 (x, y) = y;shift0 (x, y) = (x, y);shift1 (x, y) = (y, x).
4Thus, get0 (x, y) returns the ﬁrst bit, get1 (x, y) returns the second bit, shift0 (x, y) returns
the two bits identically, and shift1 (x, y) swaps the two bits.
Note that using the operations above, the AND function can be written asa ∧ b = geta (0, b) = geta (shift0 (0, b))becauseif a = 0;
if a = 1.

0
b

a∧b =
Furthermore, sincegeta (0, b) = geta⊕1 (b, 0) = geta⊕1 (shift1 (0, b)),it holds thata ∧ b = geta⊕r (shiftr (0, b))(2)

for a random bit r ∈ {0, 1}.
As will be seen soon, the idea behind the AND protocol described below is based on
Eq. (2). Hereafter, for two bits x and y, the notation? ? ? ?







(x,y)

means

? ? ? ?.

     xy

1. Arrange the six cards as follows:? ? ♣♥ ? ? → ? ? ? ? ? ?.

    a        
a

b

0

b

2. Rearrange the sequence of six cards as follows:? ? ? ? ? ?
QQ
sQ? ? ? ? ? ?.
3. Apply a random bisection cut:
? ? ?? ? ? .

4. Rearrange the sequence of six cards as follows:? ? ? ? ? ?

@

R@
@
R
@

+

? ? ? ? ? ?.
Then, we have

? ? ? ? ? ?,

   a⊕r

shiftr (0,b)



where r is a random bit because of the random bisection cut.
5

5. Reveal the leftmost two cards to ﬁnd the value of a ⊕ r, that tells us which commitment of the possible two is desired. (Recall Eq. (2), from which if a ⊕ r = 0,then a ∧ b = get0 (shiftr (0, b)) and otherwise a ∧ b = get1 (shiftr (0, b)).) Therefore, acommitment to a ∧ b is obtained as follows:♣ ♥ ? ? ? ? or ♥ ♣ ? ? ? ? .
    

a∧ba∧bNote that revealing the leftmost commitment to a ⊕ r in step 5 does not leak any
information about a because r is random. In addition, the leftmost two face-up cards areavailable for another computation.
A six-card OR protocol can be easily constructed in a similar manner [6].

2.3

The Copy Protocol with a Random Bisection Cut

Given a commitment to a bit x, four additional cards are suﬃcient to make two copies of
the commitment [8].
1. Arrange the four additional cards to the right of the given commitment:? ? ♣♥♣♥ → ? ? ? ? ? ?.

          

x

x

0

0

2. Rearrange the sequence of six cards as follows:? ? ? ? ? ?
Q 
@
Q

R
+

s @
Q

? ? ? ? ? ?.
3. Apply a random bisection cut:

? ? ?? ? ? .

4. Rearrange the sequence of six cards as follows:? ? ? ? ? ?
Q
@

R Q
@
s
Q

+

? ? ? ? ? ?.
Then, we have

? ? ? ? ? ?,

        
r

x⊕r

r

where r is a random bit because of the random bisection cut.
5. Reveal the leftmost two cards. Then, we have♣♥ ? ? ? ?

     xxor ♥ ♣ ? ? ? ? .
     x̄x̄Remember that a commitment to x is easily obtained from a commitment to x̄.
63Straightforward Secure Majority Computations

In this section, by applying the existing protocols (introduced in the previous section), weshow that a three-input secure majority computation can be naively done with 14 cards.
That is, given three commitments? ? ? ? ? ?

        abctogether with eight additional cards, we can obtain a commitment? ?

  

maj(a,b,c)

to the majority value, as follows.
First, remember that applying the copy protocol mentioned in Section 2.3 to a commitment along with four additional cards results in two copied commitments as well as
two available cards. Therefore, by applying the copy protocol three times, one at a time,
we can copy the three commitments using eight additional cards so that we have

? ? ? ? ? ? ? ? ? ? ? ? ♣ ♥.

                 
a

b

b

c

c

a

Next, sincemaj(a, b, c) = (a ∧ b) ∨ (b ∧ c) ∨ (c ∧ a),
we can easily obtain a commitment to maj(a, b, c) by applying the AND protocol and theOR protocol mentioned in Section 2.2. (Recall that the AND/OR protocol needs only two
additional cards.)
Thus, a three-input secure majority computation can be straightforwardly conductedwith eight additional cards. Alternatively, using the Full Adder protocol [6] (also shownin Table 1) with three input commitments and four additional cards, we can obtain acommitment to the carry (a ∧ b) ∨ ((a ⊕ b) ∧ c), which is equal to maj(a, b, c). In thispaper, we improve the results further, that is, in the next section, we design a tailor-madeprotocol for a secure majority computation that is simple and needs only two additionalcards.

4

An Improved Secure Majority Protocol

In this section, we propose an eﬃcient and simple secure majority protocol that requires
six fewer cards than the naive method presented above (and two fewer cards than the Full
Adder protocol [6]).
In Section 4.1, we ﬁrst introduce the idea behind our new protocol. We then describe
our protocol in Section 4.2.

7

4.1

The Idea

Given three bits a, b, c ∈ {0, 1}, if a = b, then maj(a, b, c) is equal to a; otherwise,
maj(a, b, c) is determined by c. Therefore, it holds thatmaj(a, b, c) = geta⊕b (a, c).
Hence, our protocol ﬁrst makes the following sequence:? ? ? ? ? ?.

        
a

a⊕b

c

If we turned over the leftmost two cards, then we could determine the position of thedesired commitment to geta⊕b (a, c), but the value of a⊕ b would also be leaked. Therefore,
our protocol next adds randomization to hide the value of a ⊕ b, in a manner similar to
how the six-card AND protocol shown in Section 2.2 does: it produces a sequence? ? ? ? ? ?

   

a⊕b⊕r



shiftr (a,c)



where r is a random bit. Based on the equality
maj(a, b, c) = geta⊕b⊕r (shiftr (a, c)),we can obtain a commitment to maj(a, b, c) by revealing the leftmost two cards.
The full description of our protocol is presented in the next subsection.

4.2

An Eight-Card Secure Majority Protocol

Given three commitments to bits a, b and c together with two additional cards, our securemajority protocol proceeds as follows.
1. Arrange the three commitments and the two additional cards as shown below:? ? ? ? ♣♥ ? ? → ? ? ? ? ? ? ? ?.

     a             

c

b

a

b

2. Rearrange their order:? ? ? ? ? ? ? ?
Q 
@
Q

R
s @
Q
+


  
c? ? ? ? ? ? ? ?.
  
c

3. Apply a random bisection cut to the leftmost six cards:

? ? ?? ? ?

? ?.

  
c

80c

4. Rearrange the order again:? ? ? ? ? ? ? ?

  

Q

@

R Q
@
s
Q
+


c

? ? ? ? ? ? ? ?.
  
cThen, we have

? ? ? ? ? ? ? ?,

           r1

a⊕r1 b⊕r1cwhere r1 is a random bit because of the random bisection cut.
5. Reveal the leftmost two cards. Then, we have eitheror (ii) ♥ ♣ ? ? ? ? ? ? .

(i) ♣ ♥ ? ? ? ? ? ?

        a⊕ba        

c

a⊕b

ā

c

In case (ii), apply the secure NOT operation to each of the commitments to a ⊕ r
and ā. Hence, in either case, we have three commitments? ? ? ? ? ?.

        
a

a⊕b

c

From now on, we are working only on the six face-down cards above.
6. Rearrange the sequence of six cards as follows:? ? ? ? ? ?
QQ
sQ? ? ? ? ? ?.
7. Apply a random bisection cut:

? ? ?? ? ? .

8. Rearrange the order again:? ? ? ? ? ?

@
@

R@
@
R

+

? ? ? ? ? ?.
Then, we have

? ? ? ? ? ?,

   a⊕b⊕r2 shiftr2 (a,c)

where r2 is a random bit because of the random bisection cut.
9. Reveal the leftmost two cards to ﬁnd the value of a ⊕ b ⊕ r2 . Then, a commitment
to maj(a, b, c) is obtained as follows:♣♥? ?

  

? ? or ♥ ♣ ? ?

maj(a,b,c)? ? .

  

maj(a,b,c)9

5Conclusion

In this paper, we designed an eight-card three-input secure majority protocol whose output
is in a committed format. Since the naive implementation of a secure majority computation
requires 14 cards, we have succeeded in reducing the number of required cards by six.
Furthermore, our protocol is simple and easy to understand.
Generally, when a function f can be securely computed with some number of cards,
any function derived from f by (i) negation of variables, (ii) permutation of variables or(iii) negation of f can also be securely computed with the same number of cards. Therefore,
when focusing on the three-variable symmetric Boolean functions, it is suﬃcient to consider
the following six representatives of the “NPN-equivalence [12]” classes:
3
3
3
3
3
, S{1,2}, S{1,3}, S{2,3}, S{0,2,3}S∅3 , S{3}3 for X ⊆ {0, 1, 2, 3} represents a three-variable symmetric Boolean function suchwhere SXthat
1 if a + b + c ∈ X;
def
3(a, b, c) =SX
0 otherwise.
3(a, b, c) = maj(a, b, c). There is nothing to do with S∅3 = 0. Since
Note that S{2,3}
3 (a, b, c) = a ∧ b ∧ c and S 3
S{3}{1,3} (a, b, c) = a ⊕ b ⊕ c, they can be securely computed3andwith eight cards and six cards, respectively. The remaining two functions S{1,2}3S{0,2,3} can also be securely computed with eight cards by using the equations:
3(a, b, c) = geta⊕b (a ⊕ c, 1)
S{1,2}

and3(a, b, c) = geta⊕b⊕c (1, a ∧ c).
S{0,2,3}Thus, any three-variable symmetric function can be securely computed with eight cards
or less: that is, within two additional cards. An intriguing open question is whether any
four-variable (or larger) symmetric Boolean function can be securely computed within two
additional cards. Furthermore, it is also interesting to examine the question of whether
there exists a “non-committed format” majority protocol that requires no additional card.
Aside from the practical importance of implementing secure computations, the researcharea of card-based protocols along with other physically implemented cryptographic protocols (e.g. [1, 4, 10]) can aid professional cryptographers in providing intuitive explanations
to non-specialists about what cryptography is in general. We believe that such protocols
will also be helpful for information science education in the classroom.

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

10References[1] József Balogh, János A. Csirik, Yuval Ishai, and Eyal Kushilevitz. Private computation using a PEZ dispenser. Theoretical Computer Science, 306(1–3):69–84, 2003.
[2] Claude Crépeau and Joe Kilian. Discreet solitary games. In Douglas R. Stinson,
editor, Advances in Cryptology — CRYPTO ’93, volume 773 of Lecture Notes in
Computer Science, pages 319–330. Springer Berlin Heidelberg, 1994.
[3] Bert den Boer. More eﬃcient match-making and satisﬁability: the ﬁve card trick. In
Jean-Jacques Quisquater and Joos Vandewalle, editors, Advances in Cryptology —EUROCRYPT ’89, volume 434 of Lecture Notes in Computer Science, pages 208–217.
Springer Berlin Heidelberg, 1990.
[4] Ronald Fagin, Moni Naor, and Peter Winkler. Comparing information without leaking it. Communications of the ACM, 39(5):77–85, 1996.
[5] Oded Goldreich. Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press, New York, NY, USA, 2004.
[6] Takaaki Mizuki, Isaac Kobina Asiedu, and Hideaki Sone. Voting with a logarithmic number of cards. In Giancarlo Mauri, Alberto Dennunzio, Luca Manzoni, andAntonio E. Porreca, editors, Unconventional Computation and Natural Computation,
volume 7956 of Lecture Notes in Computer Science, pages 162–173. Springer Berlin
Heidelberg, 2013.
[7] Takaaki Mizuki, Michihito Kumamoto, and Hideaki Sone. The ﬁve-card trick canbe done with four cards. In Xiaoyun Wang and Kazue Sako, editors, Advances in
Cryptology — ASIACRYPT 2012, volume 7658 of Lecture Notes in Computer Science,
pages 598–606. Springer Berlin Heidelberg, 2012.
[8] Takaaki Mizuki and Hideaki Sone. Six-card secure AND and four-card secure XOR. In
Xiaotie Deng, John E. Hopcroft, and Jinyun Xue, editors, Frontiers in Algorithmics,
volume 5598 of Lecture Notes in Computer Science, pages 358–369. Springer Berlin
Heidelberg, 2009.
[9] Takaaki Mizuki, Fumishige Uchiike, and Hideaki Sone. Securely computing XOR
with 10 cards. The Australasian Journal of Combinatorics, 36:279–293, 2006.
[10] Tal Moran and Moni Naor. Polling with physical envelopes: A rigorous analysis
of a human-centric protocol. In Serge Vaudenay, editor, Advances in Cryptology —EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 88–
108. Springer Berlin Heidelberg, 2006.
[11] Valtteri Niemi and Ari Renvall. Secure multiparty computations without computers.
Theoretical Computer Science, 191(1–2):173–183, 1998.
[12] Tsutomu Sasao. Switching Theory for Logic Synthesis. Kluwer Academic Publishers,
Norwell, MA, USA, 1st edition, 1999.

11

[13] Thomas Schneider. Engineering Secure Two-Party Computation Protocols: Design,
Optimization, and Applications of Eﬃcient Secure Function Evaluation. Springer
Berlin Heidelberg, 2012.
[14] Anton Stiglic. Computations with a deck of cards. Theoretical Computer Science,259(1–2):671–678, 2001.
[15] Andrew C. Yao. Protocols for secure computations. In Proceedings of the 23rd IEEE
Symposium on Foundations of Computer Science, FOCS 1982, pages 160–164, Washington, DC, USA, 1982. IEEE Computer Society.

12