Another Use of the Five-Card Trick:
Card-Minimal Secure Three-Input Majority
Function Evaluation⋆
Kodai Toyoda1 , Daiki Miyahara2,3 , and Takaaki Mizuki1,3
1

Tohoku University, Sendai, Japanmizuki+lncs[atmark]tohoku.ac.jp
2
The University of Electro-Communications, Tokyo, Japan
3
National Institute of Advanced Industrial Science and Technology, Tokyo, Japan

Abstract. Starting from the five-card trick proposed by Den Boer (EUROCRYPT’ 89), many card-based protocols performing secure multiparty computations with a deck of physical cards have been devised.
However, the five-card trick is considered to be still the most elegant,easy-to-understand and practical protocol, which enables two players tosecurely evaluate the AND value of their private inputs using five cards.
In other words, for more than thirty years, in the research area of cardbased cryptography, we have not discovered any protocols that are as
simple and beautiful as the five-card trick.
In this study, making use of the five-card trick, we design a novel easy-tounderstand protocol which securely evaluates the three-input majority
function using six cards. That is, by applying a simple shuffle, we reducea secure three-input majority computation to evaluating the AND value.
By virtue of a direct application of the five-card trick, our proposed majority protocol is extremely simple enough for lay-people to execute. In
addition, one advantage is that ordinary people such as high school students will be able to learn the concept of logical AND/OR operations
and the majority function as well as their relationship through our majority protocol, providing a nice tool of pedagogical significance. Thus,
we believe that our new protocol is no less practical and beautiful than
the five-card trick.

1

Introduction

To perform cryptographic tasks such as secure multiparty computations, cardbased cryptography uses a deck of physical cards such as black ♣ and red cards♡ where their backs are all identical ? . Using these cards, Boolean values are
typically represented as follows:♣ ♡ = 0, ♡ ♣ = 1.
⋆

(1)This paper appears in Proceedings of INDOCRYPT 2021. The final authenticatedversion is available online at https://doi.org/10.1007/978-3-030-92518-5_24.

2

K. Toyoda, D. Miyahara, and T. Mizuki

When a one-bit value x ∈ {0, 1} is encoded by two face-down cards according
to the encoding rule (1) above, we call such a pair of cards a commitment to x,
which is denoted by
? ?.
|{z}
x

This paper begins with introducing the first card-based protocol in history, called
the five-card trick, designed by Den Boer [6].
1.1

The Five-Card Trick

Assume that Alice and Bob hold private input bits x ∈ {0, 1} and y ∈ {0, 1},
respectively, and that each of them creates a commitment to his/her private bit.
The five-card trick securely evaluates the AND value x ∧ y of their private bits,
given commitments to bits x, y ∈ {0, 1} along with an additional card ♡ :→♡? ? ? ?
|{z} |{z}x···→ x∧y.

y

The procedure is as follows. (Here, we slightly rearrange the order of cards fromthe original reference [6] for the sake of later explanation.)
1. By swapping the two cards constituting the commitment to y (which means
the NOT computation), obtain a commitment to the negation y, and turnover the additional card:♡? ? ? ?
|{z} |{z}x→? |{z}? ? |{z}
? ?.
♡

y

x

y

Note that the three ♡ s are cyclically consecutive (i.e., the first, second, andfifth cards are red) if and only if x ∧ y = 1:

? ? ? ? ? if (x, y) = (0, 0),♡♣♡♡♣? ? ? ? ? if (x, y) = (0, 1),♡♣♡♣♡? ? ? ? ? if (x, y) = (1, 0),♡♡♣♡♣? ? ? ? ? if (x, y) = (1, 1).
♡♡♣♣♡

2. Apply a random cut to the sequence of five cards; a random cut, denotedby ⟨·⟩, is a shuffling operation that cyclically shifts a sequence of cards at
random without changing its order:⟨? ? ? ? ?⟩→? ? ? ? ?.

Card-Minimal Secure Three-Input Majority Function Evaluation

3

Thus, the resulting sequence becomes one of the following five cases withthe equal probability (i.e., 1/5), where we attach a number to each card forconvenience sake:
1 2 3 4 5
?
? ? ? ?,
2 3 4 5 1

? ? ? ?,

?
1 2 3 4 5
3 4 5 1 2
? ? ? ? ? → ? ? ? ? ? ,
4 5 1 2 3

? ? ? ? ?,
5 1 2 3 4 .
?????
It is well-known that humans can securely implement a random cut easily
so that nobody learns which case occurs [24].
3. Reveal all the five cards; then, we know the value of x ∧ y depending onwhether the three ♡ s are cyclically consecutive:♡ ♣ ♡ ♡ ♣♣ ♡ ♡ ♣ ♡♡ ♡ ♣ ♡ ♣♡ ♣ ♡ ♣ ♡♣ ♡ ♣ ♡ ♡x∧y =0or♡ ♡ ♣ ♣ ♡♡ ♣ ♣ ♡ ♡♣ ♣ ♡ ♡ ♡♣ ♡ ♡ ♡ ♣♡ ♡ ♡ ♣ ♣x ∧ y = 1.

This is the five-card trick, whereby Alice and Bob can learn only the valueof x ∧ y without leaking any information about x and y more than necessary. As
seen above, the five-card trick is extremely easy-to-understand: even lay-people
can easily understand why this AND protocol works, and it is simple enough for
non-experts such as high school students to execute without any difficulty.
1.2

Our Target

Since the invention of the five-card trick, many card-based protocols have beendevised; refer to [9,14,23] for surveys. However, the five-card trick is considered
to be still the most elegant, easy-to-understand, and practical protocol. The
five-card trick provides a way of “secure dating” for two people [12] as well as
it can be used for teaching the concept of secure multiparty computation to
students [20,22].
While it is quite certain that the five-card trick is beautiful, many lay-people
would consider that such a secure two-input AND computation may be somewhat
useless because once Alice having a private bit of x = 1 knows that the resultof the computation is x ∧ y = 0, she gets to know that Bob’s bit is y = 0,
implying that information about the other private input is leaked. Of course,
this is inherent, but it would be worthwhile to find more suitable functions foreducational purpose.

4

K. Toyoda, D. Miyahara, and T. Mizuki

In this study, as a promising function, we consider the three-input majority
function maj : {0, 1}3 → {0, 1} defined as(
1 if a + b + c ≥ 2,
(2)
maj(a, b, c) =0 if a + b + c ≤ 1.
That is, we solicit card-based protocols that securely evaluate maj(a, b, c); wecall them three-input majority protocols. By using such a three-input majority
protocol, Alice, Bob, and Carol can know only whether or not there are two or
more players having ‘Yes.’ We believe that the three-input majority function ismore convincing than the two-input AND function when teaching the conceptof secure multiparty computation.
1.3

The Existing Protocols

There are several existing three-input majority protocols. Here, we review thehistory.
In 2013, Nishida et al. [17] presented for the first time a three-input majority
protocol using eight cards. Their protocol takes commitments to bits a, b, c ∈{0, 1} along with two additional cards and outputs a commitment to the valueof maj(a, b, c) using two shuffles:? ? ? ? ? ? ♣ ♡ → ··· →?? .

|{z} |{z} |{z}

|{z}

a

b

c

maj(a,b,c)

Such a protocol is called a committed-format protocol (because it outputs acommitment). It has been an open problem to reduce the number of required
additional cards (to 0 or 1).
In 2017, Nakai et al. [16] showed that the three-input majority function can be
securely evaluated with four cards by introducing “private operations.” Allowing
private operations is a strong assumption4 that a player may manipulate thecards privately, say behind their back, while making sure that the other players
do not see the movement (cf. private PEZ protocols [1,5]). The protocol proposed
by Nakai et al. includes a private rearranging operation and a private turning
operation.
In 2018, Watanabe et al. [25] showed that the same task can be conductedwith only three cards. Their protocol uses an oral response to reverse the value
depending on the input value. In other words, this protocol uses a private negation.
In 2020, Yasunaga [26] proposed a protocol using six cards based on simple
private operations. This protocol needs to reconstruct the input commitment to
a in the middle. Yasunaga [26] also provided a protocol that does not use private
operation by making a copy of the input commitment to a in advance, resulting
in an eight-card protocol.
4

Malicious behaviors during the private operations have been discussed in [2,11,18,19].

Card-Minimal Secure Three-Input Majority Function Evaluation

5

Table 1. The existing three-input majority protocols (without private operations) andour proposed protocols#Cards #Shuf. Committed format Runtime
82✓
finite8
3
finite62
finite68 (exp.)✓Las Vegas

Nishida et al., 2013 [17]Yasunaga, 2020 [26]Ours (Section 2)
Ours (Appendix A)

This paper focuses on protocols that do not rely on any private operation;
hence, in our setting, all the previous works are the protocol by Nishida etal. [17] and the second protocol by Yasunaga [26], as shown in Table 1. The
open problem mentioned above has not been resolved yet; we will close it byproposing “card-minimal” protocols, as explained below.
1.4

Our Contribution

In this paper, we construct two protocols using six cards that improve upon theexisting three-input majority protocol proposed by Nishida et al. [16], as shownin Table 1.
Our first protocol is the main contribution of this paper: it securely evaluatesmaj(a, b, c) without any additional card:??????

→···→ maj(a, b, c).

|{z} |{z} |{z}acbBecause any three-input majority protocol requires six cards due to three input
commitments (in our setting) and our protocol needs no additional card, i.e.,
only three input commitments (consisting of six cards) suffice, our protocol is
optimal in terms of the number of required cards under the encoding rules (1),i.e., it is card-minimal. Therefore, this is the first card-minimal protocol for thethree-input majority function maj(a, b, c).
As seen later, our protocol makes use of the five-card trick [6]. That is, byapplying a simple shuffle, we reduce the three-input majority computation toevaluating the AND value. Thus, our card-minimal protocol uses only a simple shuffle along with an execution of the five-card trick. As the five-card trick
is famous for its brevity, our protocol is also simple enough for lay-people toexecute.
As the second protocol, we will also provide a committed-format version,
which we will present in Appendix A:??????
|{z} |{z} |{z}
a

b

c

→

···

→

?? .
|{z}

maj(a,b,c)This protocol is obtained by amending our first protocol using the idea behind
the AND protocol proposed by Abe et al. [3]. Although the runtime of the6

K. Toyoda, D. Miyahara, and T. Mizuki

protocol is Las Vegas, it is interesting to note that we can achieve the minimum
number of cards without complex shuffling operations such as those required
for the card-minimal AND protocol proposed by Koch et al. [10] and the one
modified by Ruangwises and Itoh [21].
1.5OutlineThe outline of this paper is as follows. In Section 2, we present a simple and easyto-understand three-input majority protocol which is card-minimal. In Section 3,
we formally describe our protocol and give a formal proof for correctness and security. In Appendix A, we present a committed-format version of a card-minimal
three-input majority protocol. We conclude this paper in Section 4.

2

Our Card-Minimal Majority Protocol

In this section, we design a three-input majority protocol without any additionalcard.
In our construction, we make use of the following simple fact on the threeinput majority function maj(a, b, c) [16]:(b ∧ c if a = 0,maj(a, b, c) =(3)b ∨ c if a = 1.
That is, we will reduce the computation of maj(a, b, c) to the computation of b∧cor b ∨ c . As we can compute b ∧ c using the five-card trick shown in Section 1.1,
let us consider how to compute b ∨ c in a similar manner, i.e., we first propose
the five-card “OR” protocol by modifying the five-card trick slightly. We also
describe variants of the five-card trick and the five-card OR protocol by replacing
the additional red card ♡ with a black card ♣ .
2.1

Variants of Five-Card Trick

In this subsection, based on the idea behind the five-card trick, we describe its
four variants: the ♡-based AND, ♡-based OR, ♣-based AND, and ♣-based OR
protocols.
The ♡-based AND protocol is exactly the five-card trick itself because it uses
♡ as an additional card and evaluates the AND value. We can obtain the ♡based OR protocol by modifying the rearrangements in the five-card trick. As forthe ♣-based protocols, let the output be 0 if three ♣ s are cyclically consecutive;
otherwise, let the output be 1. (Note that this encoding is the opposite casewhere ♡ is the additional card.) Then, we can have the ♣-based AND and OR
protocols, as seen below. For the sake of illustration, let us write commitments
to x and y using x0 , x1 , y0 and y1 as? ? ? ?,

x0 x1 y0 y1|{z} |{z}xyCard-Minimal Secure Three-Input Majority Function Evaluation

7

where x0 and x1 (y0 and y1 ) represent the two cards constituting the commitment
to x (y). For example, if x = 1, x0 is ♡ and x1 is ♣ .
The ♡-based AND protocol. This is exactly the same as the five-card trick presented in Section 1.1.
The ♡-based OR protocol.
1. Arrange the five cards as follows:→♡? ? ? ?
|{z} |{z}x? |{z}? ? |{z}
? ?.
♡

y

x

y

2. Rearrange the order of the sequence as? ? ? ? ?
PP
P
q
P
)


? ? ? ? ?.
The resulting sequence of cards becomes? ? ? ? ?.
♡ y0 x1 y1 x0

Note that the three ♡ s are cyclically consecutive if and only if x ∨ y = 1.
3. Apply a random cut to the sequence of five cards:⟨? ? ? ? ?⟩→? ? ? ? ?.

4. Reveal all the five cards. If the three red cards are cyclically consecutive♡ ♡ ♡ , we have x ∨ y = 1; otherwise, we have x ∨ y = 0.
The ♣-based AND protocol.
1. Perform Steps 1 and 2 of the ♡-based OR protocol where the additional cardis ♣ instead of ♡ . The resulting sequence of cards becomes♣? ? ? ?
|{z} |{z}x→? ? ? ? ?.
♣ y0 x1 y1 x0

yNote that the three ♣ s are not cyclically consecutive if and only if x∧y = 1.
2. Apply a random cut to the sequence of five cards:⟨? ? ? ? ?⟩→? ? ? ? ?.

3. Reveal all the five cards. If the three black cards are cyclically consecutive♣ ♣ ♣ , x ∧ y = 0; otherwise, x ∧ y = 1.

8

K. Toyoda, D. Miyahara, and T. Mizuki

The ♣-based OR protocol.
1. Perform Step 1 of the ♡-based AND protocol (namely, the five-card trick)
where the additional card is ♣ instead of ♡ . The resulting sequence of cards
becomes♣? ? ? ? → ? ? ? ? ?.
|{z} |{z}♣ |{z} |{z}
x

y

x

y

Note that the three ♣ s are not cyclically consecutive if and only if x∨y = 1.
2. Apply a random cut to the sequence of five cards:⟨? ? ? ? ?⟩→? ? ? ? ?.

3. Reveal all the five cards. If the three black cards are cyclically consecutive♣ ♣ ♣ , we have x ∨ y = 0; otherwise, we have x ∨ y = 1.
These four protocols satisfy the following relationship:
The ♡-based AND♡ ? ? ? ?
𝑥𝑦ത

Rearrange the 2nd and 5th cards♣ ? ? ? ?
𝑥𝑦ത2.2

♡ ? ? ? ?
𝑦0 𝑥1 𝑦1 𝑥0

Replace ♡ with ♣and vice versa

Replace ♡ with ♣and vice versa

The ♣-based OR

The ♡-based OR

Rearrange the 2nd and 5th cards

The ♣-based AND♣ ? ? ? ?
𝑦0 𝑥1 𝑦1 𝑥0

Idea

Here, we explain the idea behind our card-minimal three-input majority protocol.
Consider an initial state(4)? ? ? ? ? ?,|{z} |{z} |{z}abcwhere we have a commitment to c by applying the NOT computation to acommitment to c. Let us apply a random cut to the second through sixth cards
in this sequence; since the ♡-based AND will be applied (to the commitments
to b and c) if a = 0 and the ♣-based OR will be applied if a = 1, we can derive
the value of maj(a, b, c) because of the fact (3). However, depending on whether
the output is ♡-based or ♣-based, the value of a will be leaked.
To resolve this issue, using the aforementioned relationship between the four
protocols, we “randomize” the state so that if a = 0, either the ♡-based AND orthe ♣-based AND is applied with the equal probability, as follows. (Automatically, if a = 1, either the ♣-based OR or the ♡-based OR is applied in the same
way.)


with prob. 12 ,??????

|{z} |{z} |{z}(5)?????? → a b c|{z} |{z} |{z}with prob. 12 .
?
?
?
?
?
?


|{z} c0 b1 c1 b0acbaCard-Minimal Secure Three-Input Majority Function Evaluation

9

It is easy to see that if we apply a random cut to the second through sixth cards
in the above randomized state in (5), then either the ♡- or ♣-based AND isapplied when a = 0 (with the equal probability) and either the ♡- or ♣-based
OR is applied when a = 1; hence, the value of a cannot be leaked while the valueof maj(a, b, c) can be derived.
To realize the randomization in (5), we introduce a practical shuffle, called arandom bisection cut, invented by Mizuki and Sone [15]. It bisects a sequence ofcards and swaps the two halves at random (denoted by [·|·]) as follows:

2
1


2

 1
? ? ? ? with prob. 12 ,?? ?? → 2
1

? ? ? ? with prob. 12 .
We will apply a random bisection cut to the commitment to a, the third card,and the sixth card, as seen later.
A random bisection cut can be securely implemented using familiar tools;a few implementations (that can be conducted publicly) were shown in [24]. If
the backs of cards are asymmetric, a random bisection cut can be reduced toapplying a random cut without using any auxiliary tools [24].
2.3

Description

Here, we present the complete description of our three-input majority protocol.
This protocol starts with six cards of commitments to input bits a, b, and c.
1. Given commitments to a, b, and c, take the negation of the commitment toc:? ? ? ? ? ? → |{z}? ? |{z}? ? |{z}? ?.
|{z} |{z} |{z}
a

c

b

a

c

b

2. Apply a random bisection cut to the commitment to a, the third card, andthe sixth card, and return the four cards, as follows:
1

2

3

6

? ? ? ?? ? →
1

→

2

3

4

 1 3

2 6 

1

2

?? ?? ??
3

4

? ? ? ? ?? → ? ? ? ?? ? .

Note that the state of the resulting sequence becomes what is in (5).
3. Apply a random cut to the second to sixth cards as follows:? ⟨ ? ? ? ? ? ⟩→ ? ? ? ? ? ?.
4. Reveal the first card.
(a) If ♣ appears, the result is ♡-based. Reveal all the remaining five cards. If
the three red cards are cyclically consecutive ♡ ♡ ♡ , we have maj(a, b, c) =

10

K. Toyoda, D. Miyahara, and T. Mizuki

1; otherwise, we have maj(a, b, c) = 0.
♣
♣
♣
♣
♣

♡ ♣ ♡ ♡ ♣♣ ♡ ♡ ♣ ♣ ♡♣ ♡ ♡ ♣ ♡♣ ♡ ♣ ♣ ♡ ♡♡ ♡ ♣ ♡ ♣ or ♣ ♣ ♣ ♡ ♡ ♡♡ ♣ ♡ ♣ ♡♣ ♣ ♡ ♡ ♡ ♣♣ ♡ ♣ ♡ ♡♣ ♡ ♡ ♡ ♣ ♣maj(a, b, c) = 0

maj(a, b, c) = 1(b) If ♡ appears, the result is ♣-based. Reveal all the remaining five cards. If
the three black cards are cyclically consecutive ♣ ♣ ♣ , we have maj(a, b, c) =0; otherwise, we have maj(a, b, c) = 1.
♡
♡
♡
♡
♡

♣ ♣ ♡ ♡ ♣♡ ♣ ♣ ♡ ♣ ♡♣ ♡ ♡ ♣ ♣♡ ♣ ♡ ♣ ♡ ♣♡ ♡ ♣ ♣ ♣ or ♡ ♡ ♣ ♡ ♣ ♣♡ ♣ ♣ ♣ ♡♡ ♣ ♡ ♣ ♣ ♡♣ ♣ ♣ ♡ ♡♡ ♡ ♣ ♣ ♡ ♣maj(a, b, c) = 0

maj(a, b, c) = 1

Thus, this protocol does not need any additional card, and uses only two
shuffles. It is easy-to-understand as well as easy-to-implement.
We will provide a committed-format version as well in Appendix A.

3

Formal Treatment

In this section, we give a description of our majority protocol (presented in
Section 2) in a formal way based on the computation model of card-based cryptography [13]. We also prove the correctness and security of our protocol byusing the KWH-tree invented by Koch et al. [10].
3.1

Operations in Card-Based Cryptography

In card-based cryptography, there are three main operations performed on asequence of cards, namely, permuting, turning, and shuffling. Below, we assume
a sequence of n cards.
Permute. This is denoted by (perm, π) where π is a permutation applied to thesequence of cards as follows:1 2n? ? ··· ?

(perm,π)π −1 (1) π −1 (2)−−−−−→?

?

π −1 (n)

···

.

?

Turn. This is denoted by (turn, T ) where T is a set of indexes, indicating thatthe t-th card is turned over for every t ∈ T as follows:
1 2

t

n

? ? ··· ? ··· ?

(turn,T )−−−−−→

1 2

t∈T

n

? ? ··· ♣ ··· ? .

Card-Minimal Secure Three-Input Majority Function Evaluation

11

Algorithm 1 Our majority protocol
input set:n ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?, , , ,,
, , , , ,,, , , , ,,♡ ♣ ♡ ♣ ♡ ♣♡ ♣ ♡ ♣ ♣ ♡♡ ♣ ♣ ♡ ♡ ♣? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?, , , , ,,, , , , ,,, , , , ,,♡ ♣ ♣ ♡ ♣ ♡♣ ♡ ♡ ♣ ♡ ♣♣ ♡ ♡ ♣ ♣ ♡ ? ? ? ? ? ?   ? ? ? ? ? ? o
, , , , ,,, , , , ,♣ ♡ ♣ ♡ ♡ ♣♣ ♡ ♣ ♡ ♣ ♡,1. (perm, (5 6))
2. (shuf, {id, (1 2)(3 6)})3. (shuf, RC2,3,4,5,6 )4. (turn, {1})5. if visible sequence = (♡, ?, ?, ?, ?, ?) then6.
(result, 2, 3, 4, 5, 6)
7. else if visible sequence = (♣, ?, ?, ?, ?, ?) then8.
(result, 2, 3, 4, 5, 6)

Shuffle. This is denoted by (shuf, Π, F) where Π is a permutation set and F
is a probability distribution on Π, indicating that π ∈ Π is drawn according
to F and is applied to the sequence of cards as follows:1 2n? ? ··· ?

(shuf,Π, F )−−−−−−−→

π −1 (1) π −1 (2)

?

? ···

π −1 (n)?

.

We note that nobody knows which permutation in Π was applied. If theprobability distribution F is uniform, we may omit it.
3.2

Pseudocode

A pseudocode for our majority protocol is depicted in Algorithm 1, where we
defineRC2,3,4,5,6 := {id, (2 3 4 5 6), (2 3 4 5 6)2 , (2 3 4 5 6)3 , (2 3 4 5 6)4 },and (result, i, j, k, l, m) specifies output positions. The shuffle (shuf, RC2,3,4,5,6 )means that a random cut is applied to the second through sixth cards. The shuffle (shuf, {id, (1 2)(3 6)}) in Algorithm 1 represents the application of a random
bisection cut in Step 2 shown in Section 2.3.
3.3

Correctness and Security

In this subsection, we verify the correctness and security of our non-committedformat majority protocol. A three-input majority protocol is said to be correct if,
given input commitments to a, b and c, it always evaluates the value of maj(a, b, c)

12

K. Toyoda, D. Miyahara, and T. Mizuki

correctly. We say that such a protocol is secure if it leaks no information beyond
the value of maj(a, b, c) for any run of the protocol.
To verify that our majority protocol is correct and secure, we make use of theKWH-tree, which is an excellent tool developed by Koch, Walzer, and Härtel [10].
That is, if one is able to write a KWH-tree satisfying some properties for a
protocol, then it automatically implies that the protocol is correct and secure;see [8,9,10,14] for the details.
We describe the KWH-tree of our non-committed-format majority protocol
in Figure 1, following Chapter 7 of [9]. The first box in Figure 1 corresponds to an
initial sequence, consisting of three input commitments; X111 , X110 , X101 , X100 ,X011 , X010 , X001 , and X000 represent the probabilities of (a, b, c) = (1, 1, 1),(a, b, c) = (1, 1, 0), (a, b, c) = (1, 0, 1), (a, b, c) = (1, 0, 0), (a, b, c) = (0, 1, 1),(a, b, c) = (0, 1, 0), (a, b, c) = (0, 0, 1), and (a, b, c) = (0, 0, 0), respectively. In
the bottom boxes, we write X1 instead of X111 + X110 + X101 + X011 andwrite X0 instead of X100 + X010 + X001 + X000 . A polynomial annotating acard sequence in a state, such as 1/2X111 , represents the conditional probability that the current sequence is the one next to the polynomial, given thevisible sequence trace observed so far on the table. From the two boxes at thebottom, one can see that (turn, {2, 3, 4, 5, 6}) reveals the value of maj(a, b, c)
definitively. Furthermore, in each box, the sum of all polynomials is equal to
X111 + X110 + X101 + X100 + X011 + X010 + X001 + X000 , implying that no information about a, b and c leaks, i.e., the inputs and visible sequence trace arestochastically independent (before (turn, {2, 3, 4, 5, 6}) is applied finally).
Thus, the KWH-tree in Figure 1 guarantees that our proposed non-committedformat majority protocol is correct and secure.

4

Conclusion

In this paper, we constructed a three-input majority protocol using only six cards
without depending on private operations. Therefore, this is the first card-minimal
protocol for the three-input majority function maj(a, b, c). We also show that we
can obtain a committed-format majority protocol with the minimum number ofcards.
The former protocol is so simple that lay-people can easily execute it; see thepseudocode presented in Section 3.2 again to recall that the protocol is quite simple. Thus, we believe that our three-input majority protocol is no less practicaland beautiful than the five-card trick. We even think that our majority protocol is better than the five-card trick in a sense: lay-people will be able to learn
the concept of logical AND and OR operations and their relationship throughour majority protocol (because our protocol is based on the nice property thatmaj(a, b, c) can be expressed simply using b ∧ c and b ∨ c, i.e., maj(a, b, c) is equal
to one of the four variants of the five-card trick according to the value of c)while the five-card trick is just based on the fact that the three red cards areconsecutive only when x = y = 1.

Card-Minimal Secure Three-Input Majority Function Evaluationὓ‗ὓ‗ὓ‗ὓ‗ὓ‗‗ὓὓ‗‗ὓὓ‗ὓ‗‗ὓ‗ὓ‗ὓὓ‗ὓ‗‗ὓὓ‗‗ὓ‗ὓ‗ὓὓ‗‗ὓ‗ὓ‗ὓ

13

ͳͳͳ
ͳͳͲ
ͳͲͳ
ͳͲͲ
Ͳͳͳ
ͲͳͲ
ͲͲͳ
ͲͲͲ

ሺǡሺͷ͸ሻሻὓ‗ὓ‗‗ὓὓ‗ὓ‗ὓ‗ὓ‗‗ὓ‗ὓὓ‗‗ὓὓ‗‗ὓὓ‗‗ὓ‗ὓὓ‗ὓ‗‗ὓ‗ὓ‗ὓ‗ὓ‗ὓὓ‗

ͳͳͳ
ͳͳͲ
ͳͲͳ
ͳͲͲ
Ͳͳͳ
ͲͳͲ
ͲͲͳ
ͲͲͲ

ሺǡሼǡሺͳʹሻሺ͵͸ሻሽሻὓ‗ὓ‗‗ὓ‗ὓὓ‗‗ὓὓ‗ὓ‗ὓ‗‗ὓ‗‗ὓὓὓ‗‗ὓ‗ὓ‗ὓὓὓ‗‗ὓ‗‗ὓὓ‗‗ὓ‗ὓὓ‗

ଵ

ଶ ͳͳͳ
ଵ

ଶ ͳͳͳ
ଵ

ଶ ͳͳͲ
ଵ

ଶ ͳͳͲ
ଵ

ଶ ͳͲͳ
ଵ

ଶ ͳͲͳ
ଵ

ଶ ͳͲͲ
ଵ

ଶ ͳͲͲ

‗ὓὓ‗‗ὓὓ‗ὓ‗‗ὓ‗ὓὓ‗ὓ‗ὓ‗‗‗ὓὓ‗ὓ‗ὓ‗ὓὓ‗ὓὓ‗‗‗ὓ‗ὓὓ‗ὓ‗‗ὓὓ‗

ଵ

ଶ Ͳͳͳ
ଵ

ଶ Ͳͳͳ
ଵ

ଶ ͲͳͲ
ଵ

ଶ ͲͳͲ
ଵ

ଶ ͲͲͳ
ଵ

ଶ ͲͲͳ
ଵ

ଶ ͲͲͲ
ଵ

ଶ ͲͲͲ

ሺǡଶǡଷǡସǡହǡ଺ ሻሺǡሼͳሽሻ
ὓǫǫǫǫǫὓ‗ὓ‗‗ὓὓὓ‗‗ὓ‗ὓ‗‗ὓ‗ὓὓ‗ὓ‗ὓ‗ଵ ὓ‗‗ὓὓ‗ହ ͳଵ ὓ‗ὓὓ‗‗ହ ͳ
ଵ ὓὓὓ‗‗‗ହ ͳ
ଵ ὓὓ‗‗‗ὓହ ͳଵ ὓ‗‗‗ὓὓହ ͳὓὓ‗ὓ‗‗֜ሺǡʹǡ͵ǡͶǡͷǡ͸ሻ‗ǫǫǫǫǫ

ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ

‗ὓὓ‗‗ὓ‗ὓ‗‗ὓὓ‗‗‗ὓὓὓ‗‗ὓὓὓ‗ଵ ‗ὓ‗ὓὓ‗ହ ͳଵ ‗‗ὓὓ‗ὓହ ͳଵ ‗ὓὓ‗ὓ‗ହ ͳଵ ‗ὓ‗ὓ‗ὓହ ͳଵ ‗‗ὓ‗ὓὓହ ͳ‗ὓὓὓ‗‗֜ሺǡʹǡ͵ǡͶǡͷǡ͸ሻ

ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ

Fig. 1. The KWH-tree of our non-committed-format majority protocol

Our committed-format three-input majority protocol shown in Appendix A
is not finite-runtime. Since there is no committed-format finite-runtime protocolother than the eight-card protocol proposed by Nishida et al. [17], it is an interesting open problem to determine whether we can have a committed-format
finite-runtime three-input majority protocol using less than eight cards. It isalso interesting to investigate relationship between card-based general majority
function protocols and Turing world computations (cf. [7]).

Acknowledgements
We thank the anonymous referees, whose comments have helped us improve
the presentation of the paper. We would like to thank Hideaki Sone for his

14

K. Toyoda, D. Miyahara, and T. Mizuki

cooperation in preparing a Japanese draft version at an earlier stage of thiswork. This work was supported in part by JSPS KAKENHI Grant Numbers
JP19J21153 and JP21K11881.

A

Transformation to Committed Format

In this section, we show how to transform our non-committed-format protocol
proposed in Section 2 to a committed-format one. Subsequently, we give thedescription of the derived committed-format majority protocol.
A.1

How to Transform

The transformation is inspired by the five-card Las Vegas AND protocol proposed by Abe et al. [3]. Briefly, their protocol realizes to output a commitment
to x ∧ y , by adding further manipulations to the five-card trick. Since the output
in our proposed protocol is derived by using (the four variants of) the five-card
trick, it is possible to obtain a commitment to maj(a, b, c) in a similar way totheir protocol.
Here is the idea behind their protocol [3].
1. Perform Steps 1 to 3 of the five-card trick shown in Section 1.1:♡? ? ? ?
|{z} |{z}
a

→

···

→

?????.

b

2. Turn over the center card; suppose that ♣ appears:????? → ??♣??.
At this time, the resulting sequence of cards is one of the following four cases:
(i)
♡♡♣♡♣
if a ∧ b = 0;
(ii)
♣♡♣♡♡
if a ∧ b = 0;
(iii)
♡♡♣♣♡
if a ∧ b = 1;
(iv)
♡♣♣♡♡
if a ∧ b = 1.
3. Turn the center card face down. For the sake of illustration, let us represent
the sequence as follows:? ? ? ? ?.
|{z} |{z}xyObserve that, in the cases (ii) and (iv), if we let the first and second cards be
a commitment to x ∈ {0, 1} and the third and fourth ones be a commitment
to y ∈ {0, 1}, we have x ⊕ y = a ∧ b. Therefore, by applying the committedformat XOR protocol [15] to them, one can obtain a commitment to x ⊕ y =a ∧ b:? ? ? ? ? → ♣ ♡ |{z}? ? ? or ♡ ♣ |{z}? ? ?.
|{z} |{z}
x

y

a∧b

a∧b

Note that, even if it is the case (i) or (iii), one can still continue to executethe protocol without leaking information, as seen below.

Card-Minimal Secure Three-Input Majority Function Evaluation

15

In the next subsection, we present the description of our committed-format protocol using this idea.
A.2

Description

The following is our committed-format three-input majority protocol.
1. Perform Steps 1 to 3 of our non-committed-format protocol presented in
Section 2.3:??????

→···→??????.

|{z} |{z} |{z}abc2. Reveal the first card. Assume that it is black, i.e., the result will be ♡-based:
revealz}|{? ? ? ? ? ? → ♣? ? ? ? ?.

(In the case where a red card is shown, it works by interchanging the blackcards and the red cards.)
3. Reveal the fourth card. If ♡ appears, turn it over and apply a random cut
to the second through sixth cards; then, return to this step. If ♣ appears,
turn it over and go to the next step.
4. Apply the XOR protocol [15] to the second through fifth cards as follows.
(a) Rearrange the order of the sequence as♣ ? ? ? ? ?
@R@♣ ? ? ? ? ? .
(b) Apply a random bisection cut to the second through fifth cards:hi♣ ? ? ? ? ? → ♣? ? ? ? ?.
(c) Rearrange the order of the sequence as♣ ? ? ? ? ?
@R@♣ ? ? ? ? ? .
5. Reveal the second and third cards.
(a) If ♣ ♡ or ♡ ♣ appears, we obtain a commitment to maj(a, b, c) as follows:♣♣♡? ? ? or ♣ ♡ ♣ |{z}? ? ?.

|{z}maj(a,b,c)maj(a,b,c)

In the latter case, by swapping the left and right cards, we obtain acommitment to maj(a, b, c).

16

K. Toyoda, D. Miyahara, and T. Mizuki(b) If ♡ ♡ appears, then turn them over:♣♡♡? ? ?

→♣? ? ? ? ?,and rearrange the order of the sequence as♣ ? ? ? ? ?

@
@
)

R
@
R@
@
R
@
♣ ? ? ? ? ? .
Then, apply a random cut to the second through sixth cards and returnto Step 3.
♣ ⟨ ? ? ? ? ? ⟩→ ♣? ? ? ? ?.
Let us find the number of required shuffles for this committed-format protocol. The AND protocol proposed by Abe et al. takes the average of seven shuffles
to terminate [3]. Since we apply a random bisection cut first in our protocol, it
terminates with the expected number of eight shuffles in total. (It should be
noted that a recent technique presented in [4] will reduce the number of shuffles
further.)
A.3

Pseudocode

A pseudocode for our committed-format majority protocol is depicted in Algorithm 2.
A.4

Correctness and Security

To verify the correctness and security of our proposed committed-format majority protocol, we describe its KWH-tree in Figure 2; it guarantees that our
protocol is correct and secure.

References
1. Abe, Y., Iwamoto, M., Ohta, K.: Efficient private PEZ protocols for symmetric functions. In: Hofheinz, D., Rosen, A. (eds.) Theory of Cryptography. Lecture Notes in Computer Science, vol. 11891, pp. 372–392. Springer, Cham (2019),
https://doi.org/10.1007/978-3-030-36030-6_15
2. Abe, Y., Iwamoto, M., Ohta, K.: How to detect malicious behaviors in a card-based
majority voting protocol with three inputs. In: 2020 International Symposium on
Information Theory and Its Applications (ISITA). pp. 377–381 (2020), https://doi.org/10.34385/proc.65.C01-9
3. Abe, Y., Hayashi, Y., Mizuki, T., Sone, H.: Five-card AND protocol in committed
format using only practical shuffles. In: 5th ACM on ASIA Public-Key Cryptography Workshop. pp. 3–8. APKC ’18, Association for Computing Machinery, New
York, NY, USA (2018), https://doi.org/10.1145/3197507.3197510

Card-Minimal Secure Three-Input Majority Function Evaluation

17

4. Abe, Y., Hayashi, Y., Mizuki, T., Sone, H.: Five-card AND computations in committed format using only uniform cyclic shuffles. New Generation Computing
39(1), 97–114 (2021), https://doi.org/10.1007/s00354-020-00110-2
5. Balogh, J., Csirik, J.A., Ishai, Y., Kushilevitz, E.: Private computation using a PEZ
dispenser. Theoretical Computer Science 306(1), 69–84 (2003), https://doi.org/
10.1016/S0304-3975(03)00210-X
6. 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), https://doi.org/10.1007/3-540-46885-4_23
7. Dvořák, P., Koucký, M.: Barrington plays cards: The complexity of card-based
protocols. In: Bläser, M., Monmege, B. (eds.) Theoretical Aspects of Computer
Science. Leibniz International Proceedings in Informatics, vol. 187, pp. 26:1–
26:17. Schloss Dagstuhl, Dagstuhl (2021), https://doi.org/10.4230/LIPIcs.
STACS.2021.26
8. Kastner, J., Koch, A., Walzer, S., Miyahara, D., Hayashi, Y., Mizuki, T., Sone,
H.: The minimum number of cards in practical card-based protocols. In: Takagi,T., Peyrin, T. (eds.) Advances in Cryptology—ASIACRYPT 2017. Lecture Notes
in Computer Science, vol. 10626, pp. 126–155. Springer, Cham (2017), https://doi.org/10.1007/978-3-319-70700-6_5
9. Koch, A.: Cryptographic Protocols from Physical Assumptions. Ph.D. thesis, Karlsruhe Institute of Technology (2019), https://doi.org/10.5445/IR/1000097756
10. Koch, A., Walzer, S., Härtel, K.: Card-based cryptographic protocols using
a minimal number of cards. In: Iwata, T., Cheon, J.H. (eds.) Advances in
Cryptology—ASIACRYPT 2015. Lecture Notes in Computer Science, vol. 9452,
pp. 783–807. Springer, Berlin, Heidelberg (2015), https://doi.org/10.1007/
978-3-662-48797-6_32
11. Manabe, Y., Ono, H.: Secure card-based cryptographic protocols using private
operations against malicious players. In: Maimut, D., Oprina, A.G., Sauveron,D. (eds.) Innovative Security Solutions for Information Technology and Communications. pp. 55–70. Springer, Cham (2021), https://doi.org/10.1007/
978-3-030-69255-1_5
12. Marcedone, A., Wen, Z., Shi, E.: Secure dating with four or fewer cards. Cryptology
ePrint Archive, Report 2015/1031 (2015), https://eprint.iacr.org/2015/1031
13. Mizuki, T., Shizuya, H.: A formalization of card-based cryptographic protocols
via abstract machine. International Journal of Information Security 13(1), 15–23(2014), https://doi.org/10.1007/s10207-013-0219-4
14. Mizuki, T., Shizuya, H.: Computational model of card-based cryptographic protocols and its applications. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100.A(1), 3–11 (2017), https://doi.org/10.1587/transfun.E100.A.3
15. 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), https://doi.
org/10.1007/978-3-642-02270-8_36
16. Nakai, T., Shirouchi, S., Iwamoto, M., Ohta, K.: Four cards are sufficient for acard-based three-input voting protocol utilizing private permutations. In: Shikata,J. (ed.) Information Theoretic Security. Lecture Notes in Computer Science,
vol. 10681, pp. 153–165. Springer, Cham (2017), https://doi.org/10.1007/
978-3-319-72089-0_9

18

K. Toyoda, D. Miyahara, and T. Mizuki

17. 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),
https://doi.org/10.1007/978-3-642-45008-2_16
18. Ono, H., Manabe, Y.: Card-based cryptographic protocols with the minimum
number of cards using private operations. In: Zincir-Heywood, N., Bonfante, G.,
Debbabi, M., Garcia-Alfaro, J. (eds.) Foundations and Practice of Security. Lecture Notes in Computer Science, vol. 11358, pp. 193–207. Springer, Cham (2019),
https://doi.org/10.1007/978-3-030-18419-3_13
19. Ono, H., Manabe, Y.: Card-based cryptographic logical computations using private
operations. New Generation Computing 39, 19–40 (2021), https://doi.org/10.
1007/s00354-020-00113-z
20. Pass, R., Shelat, A.: A course in cryptography (2010), www.cs.cornell.edu/~rafael/
21. Ruangwises, S., Itoh, T.: AND protocols using only uniform shuffles. In: van Bevern, R., Kucherov, G. (eds.) Computer Science–Theory and Applications. Lecture Notes in Computer Science, vol. 11532, pp. 349–358. Springer, Cham (2019),
https://doi.org/10.1007/978-3-030-19955-5_30
22. Salomaa, A.: Public-Key Cryptography. Texts in Theoretical Computer Science.
An EATCS Series, Springer, Berlin Heidelberg (2013)
23. Shinagawa, K.: On the Construction of Easy to Perform Card-Based Protocols.
Ph.D. thesis, Tokyo Institute of Technology (2020)
24. Ueda, I., Miyahara, D., Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: Secure
implementations of a random bisection cut. International Journal of Information
Security 19(4), 445–452 (2020), https://doi.org/10.1007/s10207-019-00463-w
25. Watanabe, Y., Kuroki, Y., Suzuki, S., Koga, Y., Iwamoto, M., Ohta, K.: Cardbased majority voting protocols with three inputs using three cards. In: 2018 International Symposium on Information Theory and Its Applications (ISITA). pp.
218–222 (2018), https://doi.org/10.23919/ISITA.2018.8664324
26. Yasunaga, K.: Practical card-based protocol for three-input majority. IEICE
Transactions on Fundamentals of Electronics, Communications and Computer
Sciences E103.A(11), 1296–1298 (2020), https://doi.org/10.1587/transfun.
2020EAL2025

Card-Minimal Secure Three-Input Majority Function Evaluation

Algorithm 2 Our committed-format majority protocol
input set:n ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?, , , ,,
, , , , ,,, , , , ,,♡ ♣ ♡ ♣ ♡ ♣♡ ♣ ♡ ♣ ♣ ♡♡ ♣ ♣ ♡ ♡ ♣? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?, , , , ,,, , , , ,,, , , , ,,♡ ♣ ♣ ♡ ♣ ♡♣ ♡ ♡ ♣ ♡ ♣♣ ♡ ♡ ♣ ♣ ♡ ? ? ? ? ? ?   ? ? ? ? ? ? o
, , , , ,,, , , , ,♣ ♡ ♣ ♡ ♡ ♣♣ ♡ ♣ ♡ ♣ ♡,1. (perm, (5 6))
2. (shuf, {id, (1 2)(3 6)})3. (shuf, RC2,3,4,5,6 )4. (turn, {1})5. if visible sequence = (♡, ?, ?, ?, ?, ?) then6.
(turn, {4})7.
if visible sequence = (♡, ?, ?, ♡, ?, ?) then8.
(turn, {4})9.
(shuf, RC2,3,4,5,6 )10.
go to 611.
else if visible sequence = (♡, ?, ?, ♣, ?, ?) then12.
(turn, {4})13.
(shuf, {id, (2 3)(4 5)})
14.
(turn, {2, 3})15.
if visible sequence = (♡, ♡, ♡, ?, ?, ?) then16.
(turn, {2, 3})17.
(perm, (3 4 5 6))
18.
(shuf, RC2,3,4,5,6 )19.
go to 620.
else if visible sequence = (♡, ♡, ♣, ?, ?, ?) then21.
(result, 4, 5)22.
else if visible sequence = (♡, ♣, ♡, ?, ?, ?) then23.
(result, 5, 4)
24. else if visible sequence = (♣, ?, ?, ?, ?, ?) then25.
(turn, {4})26.
if visible sequence = (♣, ?, ?, ♣, ?, ?) then27.
(turn, {4})28.
(shuf, RC2,3,4,5,6 )29.
go to 2530.
else if visible sequence = (♣, ?, ?, ♡, ?, ?) then31.
(turn, {4})32.
(shuf, {id, (2 3)(4 5)})33.
(turn, {2, 3})34.
if visible sequence = (♣, ♣, ♣, ?, ?, ?) then35.
(turn, {2, 3})36.
(perm, (3 4 5 6))37.
(shuf, RC2,3,4,5,6 )38.
go to 2539.
else if visible sequence = (♣, ♣, ♡, ?, ?, ?) then40.
(result, 4, 5)
41.
else if visible sequence = (♣, ♡, ♣, ?, ?, ?) then42.
(result, 5, 4)

19

20

K. Toyoda, D. Miyahara, and T. Mizukiὓ‗ὓ‗ὓ‗ὓ‗ὓ‗‗ὓὓ‗‗ὓὓ‗ὓ‗‗ὓ‗ὓ‗ὓὓ‗ὓ‗‗ὓὓ‗‗ὓ‗ὓ‗ὓὓ‗‗ὓ‗ὓ‗ὓ

ͳͳͳ
ͳͳͲ
ͳͲͳ
ͳͲͲ
Ͳͳͳ
ͲͳͲ
ͲͲͳ
ͲͲͲ
ሺǡሺͷ͸ሻሻὓ‗ὓ‗‗ὓὓ‗ὓ‗ὓ‗ὓ‗‗ὓ‗ὓὓ‗‗ὓὓ‗‗ὓὓ‗‗ὓ‗ὓὓ‗ὓ‗‗ὓ‗ὓ‗ὓ‗ὓ‗ὓὓ‗

ͳͳͳ
ͳͳͲ
ͳͲͳ
ͳͲͲ
Ͳͳͳ
ͲͳͲ
ͲͲͳ
ͲͲͲ

ሺǡሼǡሺͳʹሻሺ͵͸ሻሽሻὓ‗ὓ‗‗ὓ‗ὓὓ‗‗ὓὓ‗ὓ‗ὓ‗‗ὓ‗‗ὓὓὓ‗‗ὓ‗ὓ‗ὓὓὓ‗‗ὓ‗‗ὓὓ‗‗ὓ‗ὓὓ‗

ଵ

ଶ ͳͳͳ
ଵ

ଶ ͳͳͳ
ଵ

ଶ ͳͳͲ
ଵ

ଶ ͳͳͲ
ଵ

ଶ ͳͲͳ
ଵ

ଶ ͳͲͳ
ଵ

ଶ ͳͲͲ
ଵ

ଶ ͳͲͲ

‗ὓὓ‗‗ὓὓ‗ὓ‗‗ὓ‗ὓὓ‗ὓ‗ὓ‗‗‗ὓὓ‗ὓ‗ὓ‗ὓὓ‗ὓὓ‗‗‗ὓ‗ὓὓ‗ὓ‗‗ὓὓ‗

ଵ

ଶ Ͳͳͳ
ଵ

ଶ Ͳͳͳ
ଵ

ଶ ͲͳͲ
ଵ

ଶ ͲͳͲ
ଵ

ଶ ͲͲͳ
ଵ

ଶ ͲͲͳ
ଵ

ଶ ͲͲͲ
ଵ

ଶ ͲͲͲ

ሺǡଶǡଷǡସǡହǡ଺ ሻሺǡሼͳሽሻ‗ǫǫǫǫǫ

ὓǫǫǫǫǫὓ‗ὓ‗‗ὓὓὓ‗‗ὓ‗ὓ‗‗ὓ‗ὓὓ‗ὓ‗ὓ‗ὓὓ‗ὓ‗‗ଵ ὓ‗‗ὓὓ‗ହ ͳଵ ὓ‗ὓὓ‗‗ହ ͳ
ଵ ὓὓὓ‗‗‗ହ ͳ
ଵ ὓὓ‗‗‗ὓହ ͳଵ ὓ‗‗‗ὓὓହ ͳ

ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ

‗ὓὓ‗‗ὓ‗ὓ‗‗ὓὓ‗‗‗ὓὓὓ‗‗ὓὓὓ‗‗ὓὓὓ‗‗ሺǡሼͶሽሻὓǫǫὓǫǫὓ‗‗ὓ‗ὓὓὓ‗ὓ‗‗ଵ ὓ‗‗ὓὓ‗ଶ ͳଵ ὓ‗ὓὓ‗‗ଶ ͳὓ‗ὓ‗‗ὓὓὓ‗‗ὓ‗ὓ‗ὓ‗ὓ‗ὓὓὓ‗‗‗ὓὓ‗‗‗ὓ

ሺǡሼǡሺʹ͵ሻሺͶͷሻሽሻὓ‗‗ὓ‗ὓὓ‗‗‗ὓὓὓὓ‗ὓ‗‗ὓ‗ὓ‗ὓ‗ଵ ὓ‗‗ὓὓ‗ସ ͳଵ ὓ‗ὓὓ‗‗ସ ͳ
ଵ ὓὓ‗‗ὓ‗
ସ ͳ
ଵ

ସ ͳ

ὓ‗‗‗ὓὓ

ଵ

ଶ Ͳ
ଵ

ସ Ͳ
ଵ

ସ Ͳ

ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ
ଵ

ହ Ͳ

ሺǡሼͶሽሻὓǫǫ‗ǫǫ

ଵ

ଶ Ͳ
ଵ

ଶ Ͳ

ଵ
 ‗ὓ‗ὓὓ‗ହ ͳଵ ‗‗ὓὓ‗ὓହ ͳଵ ‗ὓὓ‗ὓ‗ହ ͳଵ ‗ὓ‗ὓ‗ὓହ ͳଵ ‗‗ὓ‗ὓὓହ ͳଵଷ ͳ
ଵ

ଷ ͳ
ଵ

ଷ ͳ
ଵ

ଷ Ͳ
ଵ

ଷ Ͳ
ଵ

ଷ Ͳ

‗ǫǫὓǫǫ‗‗‗ὓὓὓ‗‗ὓὓὓ‗‗ὓὓὓ‗‗‗ὓ‗ὓὓ‗‗‗ὓὓ‗ὓ‗ὓ‗ὓ‗ὓ‗ǫǫ‗ǫǫ

ଵ

ଷ ͳ
ଵ

ଷ ͳ
ଵ

ଷ ͳ
ଵ

ଷ Ͳ
ଵ

ଷ Ͳ
ଵ

ଷ Ͳ

‗ὓὓ‗‗ὓ‗ὓ‗‗ὓὓ

ሺǡʹǡ͵ǡͶǡͷǡ͸ሻ‗ὓ‗‗ὓὓ‗‗ὓὓ‗ὓ

ଵ

ଶ ͳ
ଵ

ସ ͳ
ଵ

ସ ͳ

ὓ‗ὓǫǫǫὓὓ‗ὓ‗‗ ͳὓὓ‗‗ὓ‗ Ͳ֜ሺǡͶǡͷሻὓ‗ὓ‗ὓ‗ ͳὓ‗ὓὓ‗‗ Ͳ֜ሺǡͷǡͶሻ

ଵ

ସ Ͳ
ଵ

ସ Ͳ
ଵ

ସ Ͳ
ଵ
Ͳ
ସ

‗ὓὓ‗ὓ‗‗ὓὓὓ‗‗‗‗ὓ‗ὓὓ‗ὓ‗ὓ‗ὓ

ሺǡሼʹǡ͵ሽሻὓὓ‗ǫǫǫ

ଵ

ଶ Ͳ
ଵ

ଶ Ͳ

ሺǡሼǡሺʹ͵ሻሺͶͷሻሽሻ‗ὓὓ‗‗ὓ
ሺǡʹǡ͵ǡͶǡͷǡ͸ሻଵ ‗ὓὓ‗ὓ‗ଶ ͳଵ ‗‗ὓ‗ὓὓଶ ͳሺǡሼʹǡ͵ሽሻὓ‗‗ǫǫǫὓ‗‗ὓ‗ὓὓ‗‗‗ὓὓὓ‗‗ὓὓ‗‗‗ὓǫǫǫଵଶ ͳ
ଵ

ଶ ͳ

Ͳ

‗‗ὓὓ‗ὓ ͳ‗‗ὓ‗ὓὓ Ͳ֜ሺǡͶǡͷሻ‗ὓὓǫǫǫ‗ὓ‗ǫǫǫ‗ὓ‗‗ὓὓ ͳ‗ὓ‗ὓ‗ὓ Ͳ֜ሺǡͷǡͶሻ‗ὓὓ‗‗ὓ‗ὓὓ‗ὓ‗‗ὓὓὓ‗‗ሺǡሺ͵Ͷͷ͸ሻሻሺǡሺ͵Ͷͷ͸ሻሻሺǡʹǡ͵ǡͶǡͷǡ͸ሻሺǡʹǡ͵ǡͶǡͷǡ͸ሻ

Fig. 2. The KWH-tree of our committed-format majority protocol.

ͳ
ଵ

ଶ Ͳ
ଵ

ଶ Ͳ