Card-minimal Protocols for Symmetric Boolean
Functions of More Than Seven Inputs⋆
Hayato Shikata1 , Kodai Toyoda1 , Daiki Miyahara2,3 , and Takaaki
Mizuki1,3
1

Tohoku University, Sendai, JapanThe University of Electro-Communications, Tokyo, Japan
3
National Institute of Advanced Industrial Science and Technology, Tokyo, Japan
2

Abstract. Secure computations enable us to obtain the output valueof a predetermined function while keeping its input values secret. Cardbased cryptography realizes secure computations using a deck of physicalcards. Because each input bit is typically encoded with two cards, an obvious lower bound on the number of required cards is 2n when securely
computing an n-input Boolean function. Although card-based protocols
often require helping cards (aside from 2n cards needed for input), there
exist several protocols that require no helping card, namely, helpingcard-free protocols. For example, there are helping-card-free protocols forseveral fundamental functions, such as the AND, XOR, and three-input
majority functions. However, in general, it remains an open problem
whether all Boolean functions have their helping-card-free protocols. In
this study, we focus our attention on symmetric functions: Whereas thebest known result is that any n-input symmetric function can be securely
computed using two helping cards, we present a helping-card-free protocol for an arbitrary n-input symmetric function such that n > 7. Becausemuch attention has been drawn to constructing card-based protocols using the minimum number of cards, our protocol, which is card-minimal,
would be of interest to the research area of card-based cryptography.
Keywords: Card-based Cryptography · Secure computation · Real-life
hands-on cryptography · Symmetric function

1

Introduction

A secure computation, whose concept was first brought by Yao’s seminal paper [38], enables us to obtain the output value of a predetermined function while⋆

This paper appears in Proceedings of ICTAC 2022. This version of the contribution has been accepted for publication, after peer review but is not the
Version of Record and does not reflect post-acceptance improvements, or any
corrections. The Version of Record is available online at: https://doi.org/10.
1007/978-3-031-17715-6 25. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use: https://www.springernature.com/gp/
open-research/policies/accepted-manuscript-terms.

2

H. Shikata et al.

keeping the input values secret. Various techniques for secure computations havebeen proposed so far (cf. [5]). While “computer-based (digital)” secure computations have been mainly studied and developed, “physical-tool-based” securecomputations, such as using seals [27], balls [18], PEZ dispensers [1, 3, 28], flash
lights [13], coins [12], and a deck of cards [20,21], have also been studied. Physicalmethods have a couple of advantages over computer-based methods; lay-people
do not need to trust black boxes contained in computers and/or software, andthe correctness and security of physical-tool based protocols tend to be easily
understood without specialized knowledge. In this study, we focus on card-based
cryptography, which uses a deck of physical cards to perform secure computations; refer to [9, 10, 25, 34] for surveys.
1.1

What is Card-based Cryptography?

Since Den Boer [4] invented the five-card trick in 1989, many card-based cryptographic protocols have been proposed. In these protocols, a one-bit value isusually encoded by a pair of cards ♣ and ♡ , as follows:♣ ♡ = 0,♡ ♣ = 1.

(1)

According to Eq. (1), when two face-down cards ? ? (whose face side is either♣ ♡ or ♡ ♣ ) encode a bit x ∈ {0, 1}, we call them a commitment to x, whichis expressed as:
??.
|{z}
x

A card-based cryptographic protocol, or simply a protocol, takes commitments as input to perform a secure computation. For example, the aforementioned five-card trick [4], which is a five-card protocol as the name suggests,
takes commitments to a, b ∈ {0, 1} and one helping card ♡ as input:? ? ? ? ♡.
|{z} |{z}abBy applying some actions on the sequence of these five cards, such as rearranging,
shuffling, and turning over cards, this protocol reveals only the value a ∧ b of the
AND function.
Another example is the secure NOT computation, which must be the simplest
among all the existing protocols: Given a commitment to x ∈ {0, 1}, switching
the left and right cards of the commitment brings a commitment to its negation
x:
1 2

2 1

? ? → |{z}
? ?,
|{z}
x

x

where we attach the numbers above to the cards for the sake of convenience, so
as to display how the cards are rearranged.

Card-minimal Protocols for Symmetric Boolean Functions

1.2

3

Helping-card-free Protocols

One of the most attractive topics in card-based cryptography is to design cardminimal protocols that use the minimum number of cards. As most of the existing protocols follow the encoding rule (1) above (which is a “two-card-per-bit”
encoding), this paper also focuses only on protocols whose inputs are given according to Eq. (1). Therefore, since a one-bit value is encoded by two cards, any
protocol for an n-input Boolean function f : {0, 1}n → {0, 1} uses at least 2n
cards. That is, such a protocol takes n commitments to x1 , x2 , . . . , xn ∈ {0, 1},? ? ? ? · · · |{z}? ?,|{z} |{z}
x1

x2

(2)

xn

as input. If an n-input protocol does not use any (helping) card aside from the 2n
cards for the input commitments as in Eq. (2), we call it a helping-card-free protocol. For example, the five-card trick [4] mentioned in Sect. 1.1 is not a helpingcard-free protocol because it requires one helping card ♡ to securely compute the
AND function. Thus, a helping-card-free protocol for an n-input Boolean function f takes only 2n commitments (as in Eq. (2)) as input, and outputs only thevalue of f (x1 , x2 , . . . , xn ) after applying a series of actions such as shuffling andturning over cards. Note that any helping-card-free protocol is automatically a
card-minimal protocol. This paper mainly deals with helping-card-free protocols(within the standard4 computation model of card-based cryptography [24, 25]).
To the best of our knowledge, the first helping-card-free protocol in history(other than the obvious NOT computation seen above) is the XOR protocol [26],invented in 2009, which securely computes the XOR function using only two
commitments to a, b ∈ {0, 1}:? ? ? ? → · · · → |{z}??.

|{z} |{z}
a

b

a⊕b

Since the output of this protocol is a commitment to a ⊕ b, the protocol canbe repeated n − 1 times to obtain a commitment to x1 ⊕ x2 ⊕ · · · ⊕ xn fromn commitments to x1 , x2 , . . . , xn (where we set (a, b) = (x1 , x2 ), (a, b) = (x1 ⊕x2 , x3 ), and so on). Therefore, we immediately have a helping-card-free n-input
XOR protocol.
Next came the AND protocol [23] proposed in 2012. This protocol does notproduce a commitment to a ∧ b, but later in 2015, Koch et al. [11] constructeda helping-card-free AND protocol that outputs a commitment:? ? ? ? → · · · → |{z}??.

|{z} |{z}
a

b

a∧b

Since the output is a commitment, a helping-card-free n-input AND protocol canbe constructed in a similar manner. Independently of this protocol, a helpingcard-free n-input AND protocol was developed in 2016 [19]. Recently, a simpler
helping-card-free 3-input AND protocol has also been devised [7].
4There is another computation model where private actions are allowed, e.g. [2, 14–
17, 29, 32].

4

H. Shikata et al.

As for functions other than AND and XOR, a helping-card-free protocol forthe 3-input majority function has been constructed very recently [37]. Also, there
are helping-card-free protocols for the 3-input equality Boolean function (that
outputs 1 when x1 = x2 = x3 and 0 otherwise) [6, 35].
Ruangwises and Itoh [33] designed a helping-card-free protocol for any function in the class of the so-called “doubly symmetric” Boolean functions. Notethat an n-input Boolean function f : {0, 1}n → R with some set R as its range
is said to be symmetric if for any i, j, 1 ≤ i, j ≤ n, the following holds:
f (x1 , . . . , xi , . . . , xj , . . . , xn ) = f (x1 , . . . , xj , . . . , xi , . . . , xn ),and that an n-input Boolean function f : {0, 1}n → R is said to be doubly
symmetric if f is symmetric and the following holds:
f (x1 , x2 , . . . , xn ) = f (x1 , x2 , . . . , xn ).
For example, the equality Boolean functions are doubly symmetric.
We have reviewed the existing helping-card-free protocols.
1.3

Contribution

As seen in Sect. 1.2, in the literature, we already have helping-card-free protocols
for the limited classes of functions, such as the n-input AND and XOR functions
and the doubly symmetric Boolean functions. Because the class of symmetric
Boolean functions contains all these functions as well as many other important
Boolean functions (such as threshold functions), a natural question is: Can one
construct a helping-card-free protocol for any symmetric Boolean function?
As an upper bound on the number of required helping cards, in 2015, Nishida
et al. [30] proved that two helping cards are sufficient for any n-input symmetric
Boolean function f : {0, 1}n → {0, 1} to be securely computed. Ruangwises andItoh [33] extended the result to any range R, i.e., they constructed a two-helpingcard protocol for any n-input symmetric Boolean function f : {0, 1}n → R,
where R is any set. Anyway, it is still open to determine whether one can obtaina protocol for any n-input symmetric Boolean function using fewer than two
helping cards.
In this paper, we tackle this open problem. Namely, we aim to design a
helping-card-free protocol for symmetric Boolean functions. Specifically, we will
provide a generic construction of a helping-card-free protocol for an arbitrary
n-input symmetric Boolean function f : {0, 1}n → {0, 1} such that n ≥ 8.
Therefore, we give a partial answer to the open problem.
Our generic construction relies on the two novel sub-protocols, which will
be presented in Sect. 3. The first sub-protocol transforms two commitments(to a, b ∈ {0, 1}) into the result of their addition (namely, a + b) without any
helping card; in addition, it produces one “free” card, which is very useful becausesuch “free” cards can be used as helping cards in another protocol. Because theresult of addition is obtained as an integer in a different encoding, the second
sub-protocol transforms such an integer into commitments; in other words, itCard-minimal Protocols for Symmetric Boolean Functions

5“binarizes” an integer. Making use of these two sub-protocols along with otherexisting protocols, we will design a generic protocol in Sect. 4. Before Sects. 3
and 4, we give some preliminaries in Sect. 2, and we conclude this paper in
Sect. 5.

2

Preliminaries

In this section, we introduce a property of the symmetric functions and some ofthe existing protocols. Hereinafter, a symmetric Boolean function f : {0, 1}n →{0, 1} is simply called a symmetric function.
2.1

Property of Symmetric Functions

Let f : {0, 1}n → {0, 1} be a symmetric function, and let xi ∈ {0, 1} for every
i, 1 ≤ i ≤ n. It is well-known that P
the value of f (x1 , . . . , xn ) depends onlyn
on the summation of the inputs, i.e., i=1 xi . That is, there exists a function
g : {0, 1, . . . , n} → {0, 1} such that!
nX
f (x1 , . . . , xn ) = g
xi .
(3)
i=1

This implies that computing the summation
the symmetric function f .
2.2

Pni=1 xi is one way for computing

Half Adder Protocol and Full Adder Protocol

A half-adder protocol is useful when computing the summation described in
Sect. 2.1. The first card-based half-adder protocol was presented in 2013 [22].
After that, Nishida et al. [30] improved it by proposing a half-adder protocol
with two helping cards:? ? ? ? ♣ ♡ → · · · → |{z}? ? |{z}? ? ♣♡.

|{z} |{z}
a

b

a∧b

a⊕b

A full-adder protocol using four helping cards was presented in 2013 [22]:? ? ? ? ? ? ♣ ♡ ♣ ♡ → ··· →??

? ? ♣♡♣♡♣♡.

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

|{z}

|{z}

a

2.3

b

c

(a∧b)∨(b∧c)∨(c∧a) a⊕b⊕c

Protocol for Symmetric Functions with Two Helping Cards

In 2015, Nishida et al. [30] invented a protocol for any symmetric function using
two helping cards (as mentioned in Sect. 1.3). Given n commitments and two
helping cards,? ? ? ? · · · |{z}? ? ♣♡,|{z} |{z}
x1

x2

xn

6

H. Shikata et al.

their protocol produces a sequence of commitments that represents the binary
representation of the summation,? ? ? ?{z · · · ? ?} ,
P

|

(

n
i=1 xi )2

using thePhalf-adder protocol introduced in Sect. 2.2; then, their protocol comn
putes g( i=1 xi ) as in Eq. (3) using that sequence. Here, for a nonnegative
integer i ∈ {0, 1, . . . , ℓ}, we denote the binary representation of i by (i)2 , whichis represented as ⌈log2 (ℓ + 1)⌉ commitments written as? ? ? ?{z · · · ? ?} .

|

(i)2

The range of the protocol above is {0, 1}, whereas Ruangwises and Itoh [33]constructed a protocol for a symmetric function f : {0, 1}n → R with an arbitrary range R using two helping cards (as also mentioned in Sect. 1.3). Their
protocol used the following ♣-position and ♡-position encodings (the ♣-pos. encoding and the ♡-pos. encoding for short, respectively). In the ♣-pos. encoding,for k ≥ 2, one ♣ and k − 1 ♡ s are used to represent an integer i (0 ≤ i ≤ k − 1)by placing ♣ at the (i + 1)-st position as follows:
1 2

i+1

k

♡ ♡ ... ♣ ... ♡ .
In the following, we denote such a sequence of face-down cards by Ek♣ (i), andwrite it as follows:? ? ?{z· · · ?} .
|Ek♣ (i)The ♡-pos. encoding and Ek♡ (i) are defined in the same way with the colors (i.e.,suits) reversed.
2.4

Addition of Position Encodings

Ruangwises and Itoh [33] proposed the following method for adding two integers
represented in the pos. encodings.5
1. Assume that we have Ek♣ (a) and Ek♡ (b) for two integers a, b. For convenience,
we name each card as follows:Ek♣ (a) : ? ? · · ·
x0 x1

5

♡
? , Ek (b) : ? ? · · · ? .

xk−1

y0 y1

yk−1

This method is originated from the previous protocol [36] proposed by Shinagawa etal.

Card-minimal Protocols for Symmetric Boolean Functions

7

2. Rearrange the sequences as follows:
yk−1

yk−2

y0

? ? ··· ? ? .

? ?

x0

x1

xk−1

3. Apply a random 2-section cut (also known as a pile-shifting shuffle [31]) tothis sequence. Here, a random 2-section cut means to make each pair of cards
into a single bundle and shuffle all the bundles cyclically. Thus, for a random
number r, the sequence changes as follows: yk−1

yk−2
yk−1−ryk−2−ry0−ry0? ? ? ? ··· ? ? → ? ?
? ? ···
? ? .
x0

x1

xk−1

x0+r

x1+r

xk−1+r

4. Rearrange them back to the first place as follows:Ek♣ (a − r) :

? ···

?

x0+r x1+r♡? , Ek (b + r) : ?

xk−1+r? ···y0−r y1−r? ,yk−1−rwhere a is subtracted by the random number r and b is added by r.
5. Turn over Ek♡ (b+r) and shift Ek♣ (a−r) cyclically to the right by the revealed
number, i.e., add b + r to a − r; when revealing Ek♡ (b + r), the value of b
does not leak because a random value r was added to b:
Ek♣ (a − r) :

?

? ···

x0+r x1+r?

xk−1+r→ Ek♣ (a + b) :

?

? ···

x0−b x1−b? .

xk−1−bThis enables a secure computation of (a − r) + (b + r) = a + b without leaking
the values of a and b. That is, Ek♣ (a + b) is obtained. Here, we did an addition ofthe ♣-pos. encoding and the ♡-pos. encoding, but other combinations are also
feasible.

3

Building Blocks

Before describing our proposed protocol in the next section, we present two novel
sub-protocols, which will be used in the proposed protocol as building blocks.
3.1

Addition of Two Commitments

To construct our proposed protocol, we first compute the summation of inputs
as implied in Sect. 2.1. For this, we propose the following addition protocol tocompute a+b from commitments to a, b ∈ {0, 1} without the need of any helping
card6 . That is, somewhat surprisingly, this novel sub-protocol is helping-cardfree.
6This protocol is inspired by the Mizuki–Kumamoto–Sone AND protocol [23]; theprocedure is the same up to the middle.

8

H. Shikata et al.

1. Apply a random bisection cut [26] (denoted by [· · · | · · · ]) to the sequence ofthe commitments to a and b as follows:? ? ? ? →[ ? ?|? ? ]→ ? ? ? ?.
|{z} |{z}abHere, a random bisection cut is to halve a sequence and shuffle the two halvesrandomly.
2. Shuffle the two cards in the middle as follows:? [ ?|? ] ? → ? ? ? ?.
3. Reveal the second card from the left; then, either ♣ or ♡ appears with aprobability of 1/2:
? ? ? ?.
↑

Reveal(a) If ♣ appears, rearrange the sequence to obtain a + b in the ♣-pos. encoding, i.e., E3♣ (a + b), as follows:
1 3 4

1 2 3 42

? ♣ ? ? → |? {z? ?} ♣ .
E3♣ (a+b)(b) If ♡ appears, rearrange the sequence to obtain a + b in the ♡-pos. encoding, i.e., E3♡ (a + b), as follows:
1 2 3 44 3 1

2

? ♡ ? ? → |? {z? ?} ♡ .
E3♡ (a+b)

We call this protocol the helping-card-free two-commitment addition. The
correctness and security of this addition protocol can be proved by drawing theso-called KWH-tree [8, 11]. We depict its KWH-tree in Fig. 1.
As seen above, we obtain either E3♣ (a + b) or E3♡ (a + b) (with a probabilityof 1/2) as well as one free card from the commitments to a and b.
3.2

Binarization of Position Encoding

Our second novel sub-protocol is to “binarize” an integer in the position encoding. Let 0 ≤ i ≤ 3; given E4♣ (i) and four helping cards, this sub-protocol
produces commitments to (i)2 . (A protocol for E4♡ (i) can be constructed in asimilar way.)
1. Turn the four helping cards face down (resulting in two commitments to 0
because of the encoding rule (1)):? ?{z? ?}|E4♣ (i)♣♡ ♣♡ →

? ?{z? ?} |{z}? ? |{z}??.

|E4♣ (2u+v)

00Here, we introduce u, v ∈ {0, 1} such that i = 2u + v, i.e., u and v are themost and least significant bits of (i)2 , respectively.

Card-minimal Protocols for Symmetric Boolean Functions
♡♣♡♣
♡♣♣♡
♣♡♡♣
♣♡♣♡

9

𝑋11
𝑋10
𝑋01
𝑋00

(shuf, {id,(1 3)(2 4)})

♡♣♡♣
♡♣♣♡
♣♡♡♣
♣♡♣♡

𝑋2
1/2𝑋1
1/2𝑋1
𝑋0
(shuf, {id,(2 3)})

♡♣♡♣
♡♡♣♣
♡♣♣♡
♣♡♡♣
♣♡♣♡
♣♣♡♡

1/2𝑋2
1/2𝑋2
1/2𝑋1
1/2𝑋1
1/2𝑋0
1/2𝑋0

(turn, {2})(perm, (2 4 1 3))

?♡??

?♣??
(perm, (2 4 3))♡♡♣ 𝑋2♡♣♡ 𝑋1♣♡♡ 𝑋0♣♣♡ 𝑋2♣♡♣ 𝑋1♡♣♣ 𝑋0Fig. 1. KWH-tree of the helping-card-free two-commitment addition. Here, X0 = X00 ,X1 = X01 + X10 , and X2 = X11 .

2. Shuffle E4♣ (2u + v) and the middle commitment to 0 “synchronously” asfollows.
(a) Rearrange the sequence as follows:
1 2 3 4

5 6

7 8

1 2 5

???? ?? ?? → ???
| {z } |{z} |{z}E4♣ (2u+v)

0

0

3 4 6

7 8

? ? ? |{z}??.
0(b) Apply a random bisection cut to the first six cards:[ ? ? ? | ? ? ? ]?? → ??????

? ?.

(c) Rearrange the sequence as follows:
1 2 3 4 5 6

7 8

1 2 4 53 6??????

?? →????
| {z }? ? ? ?.
|{z} |{z}E4♣ (2(u⊕r1 )+v)

r1

7 8

0

Here, a random bit r1 ∈ {0, 1} is added to u and the middle commitment
to 0 because of the random bisection cut in Step 2b.
3. Shuffle E4♣ ((2u ⊕ r1 ) + v) and the right commitment to 0 “synchronously”
as follows.
(a) Rearrange the sequence as follows:
1 2 3 45 6????
| {z }?? ?? → ???
|{z} |{z}E4♣ (2(u⊕r1 )+v)

r1

7 8

0

1 3 7

2 4 8

5 6

? ? ? |{z}
??.
r1

10

H. Shikata et al.
Table 1. How to swap commitments in Step 5 of the binarization protocol
Revealed Seq. Binary

Swapping♣♡♡♡| {z }(0, 0)?? ??

♡♣♡♡| {z }(0, 1)?? ??

♡♡♣♡| {z }(1, 0)♡♡♡♣| {z }(1, 1)

♣
E4
(0)

Swap

♣
E4
(1)

?? ??

Swap

♣
E4
(2)

?? ??

Swap Swap

♣
E4
(3)

(b) Apply a random bisection cut to the first six cards:[ ? ? ? | ? ? ? ]?? → ???

???

? ?.

(c) Rearrange the sequence as follows:
1 2 3 45 6

7 8

1 4 2 5

7 8????

? ? |{z}?? →????
| {z }?? ??.
|{z} |{z}r1E4♣ (2(u⊕r1 )+(v⊕r2 ))

r1

3 6

r2

Here, a random bit r2 ∈ {0, 1} is added to v and the right commitment
to 0 because of applying the random bisection cut in Step 3b.
4. Reveal E4♣ (2(u ⊕ r1 ) + (v ⊕ r2 )):? ?{z? ?}|? ? ? ?.

Reveal

5. From the revealed integer value in the previous step, obtain commitments
to (i)2 by swapping (or not swapping) the commitments to r1 and r2 as
shown in Table 1: Consider commitments to the binary representation of therevealed integer value (i.e., the second column of the table); if we have 1
among the two-bit sequence, we swap the corresponding commitment; if wehave 0, we do not swap the commitment. By rearranging the sequence inthis way, we obtain? ? ? ? , i.e., |? ?{z? ?} .

|{z} |{z}
u

v

(i)2

For example, if E4♣ (2) appears by revealing the sequence in Step 4 as♡♡♣♡
| {z }
E4♣ (2)? ? ? ?,|{z} |{z}r1r2Card-minimal Protocols for Symmetric Boolean Functions

11

Fig. 2. KWH-tree of our binarization protocol. Note that the probability of the input
sequence being E4♣ (i) is Xi .

we swap the middle commitment to r1 , but do not swap the right commitment
as follows:♡♡♣♡| {z }
E4♣ (2)? ? ? ? → ♡♡♣♡Swap

? ?{z? ?} .

|

(i)2

The correctness and security of this protocol can be confirmed by drawing its
KWH-tree depicted in Fig. 2. We believe that this sub-protocol is of independentinterest.

4

Our Proposed Protocol

We are ready to describe our proposed protocol for securely computing any
symmetric function f : {0, 1}n → {0, 1} such that n ≥ 8. Let us assume thatn = 8 for simplicity (the protocol can be easily extended to the case of n ≥ 9).

12

H. Shikata et al.

Thus, the input to the protocol is a sequence of 16 cards:?? ?? ?? ?? ?? ?? ?? ??.
|{z} |{z} |{z} |{z} |{z} |{z} |{z} |{z}
x1

x2

x3

x4

x5

x6

x7

x8

An overview of our protocol is as follows.
1. Add the inputs to obtain sequences of x1 + x2 + x7 , x3 + x4 , and x5 + x6 + x8
using our helping-card-free two-commitment addition proposed in Sect. 3.1
and the existing addition protocol introduced in Sect. 2.4 (Sect. 4.1).
2. Binarize the sequences obtained above using our binarization protocol proposed in Sect. 3.2 (Sect. 4.2).
3. Add the binarized sequences using the existing full-adder protocol introducedin Sect. 2.2 (Sect. 4.3).

4.1

Adding the Inputs

Computing x1 +x2 . First, we obtain a sequence of x1 +x2 from the commitments
to x1 and x2 using our helping-card-free two-commitment addition described in
Sect. 3.1. For the sake of explanation, let us assume that the addition result
is obtained in the ♣-pos. encoding, i.e., we obtain E3♣ (x1 + x2 ) without lossof generality. In this case, one free card ♣ is also obtained. In summary, theresulting sequence is as follows:??? ♣| {z }

E3♣ (x1 +x2 )? ? ? ? · · · |{z}??.

|{z} |{z}
x3

x4

x8

Computing x3 +x4 . We apply the helping-card-free two-commitment addition to
obtain a sequence of x3 + x4 . Here, we have two possible cases with a probabilityof 1/2 as follows.
1. If the revealed card is ♡, the resulting sequence is as follows:? ? ? ♣ |? {z? ?} ♡| {z }

E3♣ (x1 +x2 )E3♡ (x3 +x4 )? ? · · · |{z}
??.

|{z}
x5

x8

2. If it is ♣, the resulting sequence is as follows:? ? ? ♣ |? {z? ?} ♣| {z }

E3♣ (x1 +x2 )E3♣ (x3 +x4 )? ? · · · |{z}
??.

|{z}
x5

x8

In the former case, we have ♣ ♡ as free cards. In the latter case, we have♣ ♣ as free cards.

Card-minimal Protocols for Symmetric Boolean Functions

13

Computing x5 + x6 . For each of the two cases described in the previous paragraph, an addition is done as follows.
Case 1: We have free cards ♣ ♡ .
We use the helping-card-free two-commitment addition for computing x5 + x6 .
Without loss of generality, let us assume that ♣ appears in this computation.
Thus, the resulting sequence is as follows:

???

???

???

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

E3♣ (x1 +x2 ) E3♡ (x3 +x4 ) E3♣ (x5 +x6 )♣♣♡ ? ? ? ? .
|{z} |{z}
x7

(4)

x8

Case 2: We have free cards ♣ ♣ .
We want to acquire a free card ♡ (which is a different color from the current
free cards) via the computation of x5 + x6 . To achieve this, we use the existing
addition protocol introduced in Sect. 2.4 to compute x5 + x6 while generating a♡ . Remember that the current sequence is:???
| {z }

E3♣ (x1 +x2 )

♣

♣

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

|{z}
x5

E3♣ (x3 +x4 )x8

Recall that the commitments to x5 and x6 are encoded by:♣ ♡ = 0,♡ ♣ = 1.

This can be viewed as representing an integer value at the position of ♣ , i.e.,E2♣ (x5 ) or E2♣ (x6 ). If we swap the two cards comprising each commitment,
they are commitments to x5 and x6 and can be viewed as E2♡ (x5 ) and E2♡ (x6 ),respectively, because they represent values at the position of ♡ . In this case,adding a ♣ to the rightmost does not change the value represented, resulting in
E3♡ (x5 ) and E3♡ (x6 ). Based on this, we compute x5 + x6 as follows7 .
1. Place each of the two ♣ s on the right of the commitments to x5 and x6 asfollows:? ? ♣ |{z}? ? ♣.
|{z}x5

x6

Then, turn over the face-up cards to have E3♡ (x5 ) and E3♡ (x6 ):??? ???.
| {z } | {z }E3♡ (x5 )

E3♡ (x6 )2. Apply the existing addition protocol introduced in Sect. 2.4 to the sequence
to obtain E3♡ (x5 + x6 ):??? ??? →???

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

E3♡ (x5 )

7E3♡ (x6 )♣♣♡.

E3♡ (x5 +x6 )The idea of adding two pos. encodings of the same color was suggested by Kazumasa
Shinagawa.

14

H. Shikata et al.

(Note that ♣ ♣ ♡ appear as free cards because the three cards in the ♡-pos.
encoding are revealed.) In summary, the whole sequence is as follows:

???

???

???

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

E3♣ (x1 +x2 )E3♣ (x3 +x4 )E3♡ (x5 +x6 )♣♣♡ ? ? ? ? .
|{z} |{z}
x7

(5)

x8

Thus, we have two possibilities of the current sequence (4) or (5). Hereinafter,
we assume the sequence (5); the case for the sequence (4) will be easily handledjust by exchanging “x3 + x4 ” and “x5 + x6 ” in the sequel.
Addition of x1 + x2 and x7 . As shown above, we have now three free cards♣ ♣ ♡ 8 . Next, we add E3♣ (x1 + x2 ) to the commitment to x7 to obtain E4♣ (x1 +x2 + x7 ) as follows.
1. Place the free card ♡ on the right of E3♣ (x1 + x2 ) and place the two ♣ s on
the right of the commitment to x7 as follows:??? ♡? ? ♣♣.

| {z }|{z}

E3♣ (x1 +x2 )x7

Recall that the value of x1 + x2 is represented at the position of ♣ in thesequence, and x7 is represented at the position of ♡ in the commitment.
Therefore, after turning over the face-up cards, each value is represented by
the position encoding as follows:? ?{z? ?} |? ?{z? ?} .

|E4♣ (x1 +x2 )E4♡ (x7 )2. Apply the existing addition protocol introduced in Sect. 2.4:

? ?{z? ?} |? ?{z? ?} →|E4♣ (x1 +x2 )? ?{z? ?}

♣♣♣♡.

|

E4♡ (x7 )

E4♣ (x1 +x2 +x7 )In summary, the whole sequence is as follows:? ?{z? ?}|E4♣ (x1 +x2 +x7 )

???

???

| {z }| {z }

E3♣ (x3 +x4 )E3♡ (x5 +x6 )♣♣♣♡ ? ? .
|{z}x8

Addition of x5 + x6 and x8 Now we have four free cards of three ♣ s and one ♡ .
Using them, E3♡ (x5 +x6 ), and the commitment to x8 , we obtain E4♡ (x5 +x6 +x8 )in a similar way as in the above paragraph:? ?{z? ?}|E4♣ (x1 +x2 +x7 )8???
| {z }

E3♣ (x3 +x4 )? ?{z? ?}♣♣♣♡♡.

|

E4♡ (x5 +x6 +x8 )Generally, there are two cards of the same color and one card of the other color.

Card-minimal Protocols for Symmetric Boolean Functions

4.2

15

Binarization

Up to now, we have at least four free cards of two ♣ s and two ♡ s. Using these,
we binarize E4♣ (x1 + x2 + x7 ) and E4♡ (x5 + x6 + x8 ) by our binarization protocol
proposed in Sect. 3.2.
After that, the resulting sequence is as follows:? ?{z? ?}|(x1 +x2 +x7 )2

4.3? ?{z? ?} ♣ ♣ ♣ ♡ ♡ .

???
| {z }|

E3♣ (x3 +x4 )(x5 +x6 +x8 )2

Full Adder and Binarization

Full adder of (x1 + x2 + x7 )2 and (x5 + x6 + x8 )2 . Using the existing full adder
protocol introduced in Sect. 2.2, we add (x1 + x2 + x7 )2 to (x5 + x6 + x8 )2 withthe free cards of two ♣ s and two ♡ s as follows:? ?{z? ?} |? ?{z? ?} →|(x1 +x2 +x7 )2(x5 +x6 +x8 )2? ? ?{z? ? ?} ♣ ♡ .

|(x1 +x2 +x5 +x6 +x7 +x8 )2After that, the whole sequence is as follows:? ? ?{z? ? ?}|(x1 +x2 +x5 +x6 +x7 +x8 )2???

♣♣♣♣♡♡♡.

| {z }

E3♣ (x3 +x4 )Binarization of E3♣ (x3 + x4 ) and Overall Addition. To obtain commitments to(x3 + x4 )2 , we first place a ♡ on the right of E3♣ (x3 + x4 ) to obtain E4♣ (x3 + x4 )as follows:? ? ? ♡ → |? ?{z? ?} .

| {z }

E3♣ (x3 +x4 )

E4♣ (x3 +x4 )To summarize the situation, we have

? ? ?{z? ? ?}|(x1 +x2 +x5 +x6 +x7 +x8 )2? ?{z? ?}♣♣♣♣♡♡.

|

E4♣ (x3 +x4 )Then, we binarize E4♣ (x3 + x4 ) using our binarization protocol proposed in
Sect. 3.2. Finally, we add (x3 + x4 )2 to (x1 + x2 + x5 + x6 + x7 + x8 )2 withthe free cards using the existing full-adder protocol introduced in Sect. 2.2 as

16

H. Shikata et al.

follows:? ? ?{z? ? ?}|(x1 +x2 +x5 +x6 +x7 +x8 )2? ?{z? ?} ♣ ♣ ♣ ♣ ♡ ♡|E4♣ (x3 +x4 )↓? ? ?{z? ? ?}|(x1 +x2 +x5 +x6 +x7 +x8 )2? ?{z? ?} ♣ ♣ ♣ ♡ ♡ ♡|(x3 +x4 )2↓? ? ? ?{z? ? ? ?} ♣ ♣ ♣ ♣ ♡ ♡ ♡ ♡ .
P

|

(

8
i=1 xi )2

P8
Now we have commitments to the summation of the inputs i=1 xi . From theseP8
commitments, we compute g( i=1 xi ) as in Eq. (3).
When n ≥ 9, it suffices
to add the remaining commitments to x9 , x10 , . . . , xn
P8
to the summationx
using the existing half-adder protocol because weii=1
have enough free cards.

5

Conclusion and Future WorkIn this study, we proved that any n-input symmetric function such that n ≥ 8
can be securely computed without the need of any helping cards. That is, we
provided a helping-card-free protocol for any n-input symmetric function suchthat n ≥ 8. Therefore, our protocol uses the minimum number of cards, i.e., it
is card-minimal.
For the case of n = 2, the existing protocols [11, 23, 26] immediately imply
that any 2-input symmetric function can be securely computed without any
helping card. Therefore, the remaining open problem is to determine whether
there exists a helping-card-free protocol for any n-input symmetric function suchthat 3 ≤ n ≤ 7.

Acknowledgements
We thank the anonymous referees, whose comments have helped us improve
the presentation of the paper. We thank Kazumasa Shinagawa for the idea ofcomputing x5 + x6 for Case 2 in Sect. 4.1. This work was supported in part by
JSPS KAKENHI Grant Number JP21K11881.

References
1. Abe, Y., Iwamoto, M., Ohta, K.: Efficient private PEZ protocols for symmetric functions. In: Hofheinz, D., Rosen, A. (eds.) Theory of Cryptography.
LNCS, vol. 11891, pp. 372–392. Springer, Cham (2019), https://doi.org/10.1007/
978-3-030-36030-6 15

Card-minimal Protocols for Symmetric Boolean Functions

17

2. Abe, Y., Nakai, T., Kuroki, Y., Suzuki, S., Koga, Y., Watanabe, Y., Iwamoto, M.,
Ohta, K.: Efficient card-based majority voting protocols. New Gener. Comput. 40,
173–198 (2022), https://doi.org/10.1007/s00354-022-00161-7
3. Balogh, J., Csirik, J.A., Ishai, Y., Kushilevitz, E.: Private computation using a
PEZ dispenser. Theor. Comput. Sci. 306(1), 69–84 (2003), https://doi.org/10.
1016/S0304-3975(03)00210-X
4. 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. LNCS, vol. 434, pp. 208–217. Springer, Berlin, Heidelberg (1990), https://doi.
org/10.1007/3-540-46885-4 23
5. Evans, D., Kolesnikov, V., Rosulek, M.: A pragmatic introduction to secure multiparty computation. Foundations and Trends® in Privacy and Security 2(2-3),
70–246 (2018), https://doi.org/10.1561/3300000019
6. Heather, J., Schneider, S., Teague, V.: Cryptographic protocols with everyday objects. Formal Aspects of Computing 26(1), 37–62 (2014), https://doi.org/10.1007/
s00165-013-0274-7
7. Isuzugawa, R., Toyoda, K., Sasaki, Y., Miyahara, D., Mizuki, T.: A card-minimal
three-input AND protocol using two shuffles. In: Chen, C.Y., Hon, W.K., Hung,
L.J., Lee, C.W. (eds.) Computing and Combinatorics. LNCS, vol. 13025, pp. 668–
679. Springer, Cham (2021), https://doi.org/10.1007/978-3-030-89543-3 55
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. LNCS, 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.: The landscape of security from physical assumptions. In: IEEE Information Theory Workshop. pp. 1–6. IEEE, NY (2021), https://doi.org/10.1109/
ITW48936.2021.9611501
11. 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. LNCS, vol. 9452, pp. 783–807. Springer, Berlin, Heidelberg(2015), https://doi.org/10.1007/978-3-662-48797-6 32
12. Komano, Y., Mizuki, T.: Coin-based secure computations. Int. J. Inf. Secur. pp.
1–14 (2022), https://doi.org/10.1007/s10207-022-00585-8, in press
13. Lafourcade, P., Mizuki, T., Nagao, A., Shinagawa, K.: Light cryptography. In:
Drevin, L., Theocharidou, M. (eds.) Information Security Education. Education in
Proactive Information Security. IFIPAICT, vol. 557, pp. 89–101. Springer, Cham(2019), https://doi.org/10.1007/978-3-030-23451-5 7
14. Manabe, Y., Ono, H.: Card-based cryptographic protocols for three-input functions
using private operations. In: Combinatorial Algorithms. LNCS, vol. 12757, pp. 469–
484. Springer, Cham (2021), https://doi.org/10.1007/978-3-030-79987-8 33
15. Manabe, Y., Ono, H.: Card-based cryptographic protocols with a standard deckof cards using private operations. In: Cerone, A., Ölveczky, P.C. (eds.) Theoretical
Aspects of Computing – ICTAC 2021. LNCS, vol. 12819, pp. 256–274. Springer,
Cham (2021), https://doi.org/10.1007/978-3-030-85315-0 15
16. 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. LNCS, vol. 12596, pp. 55–70. Springer, Cham (2021), https://doi.org/10.
1007/978-3-030-69255-1 5

18

H. Shikata et al.

17. Manabe, Y., Ono, H.: Card-based cryptographic protocols with malicious players
using private operations. New Gener. Comput. 40, 67–93 (2022), https://doi.org/
10.1007/s00354-021-00148-w
18. Miyahara, D., Komano, Y., Mizuki, T., Sone, H.: Cooking cryptographers: Secure
multiparty computation based on balls and bags. In: Computer Security Foundations Symposium. pp. 1–16. IEEE, NY (2021), https://doi.org/10.1109/CSF51468.
2021.00034
19. Mizuki, T.: Card-based protocols for securely computing the conjunction of multiple variables. Theor. Comput. Sci. 622(C), 34–44 (2016), https://doi.org/10.1016/
j.tcs.2016.01.039
20. Mizuki, T.: Preface: Special issue on card-based cryptography. New Gener. Comput. 39, 1–2 (2021), https://doi.org/10.1007/s00354-021-00127-1
21. Mizuki, T.: Preface: Special issue on card-based cryptography 2. New Gener. Comput. 40, 47–48 (2022), https://doi.org/10.1007/s00354-022-00170-6
22. 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. LNCS, vol. 7956, pp. 162–173. Springer,
Berlin, Heidelberg (2013), https://doi.org/10.1007/978-3-642-39074-6 16
23. 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.
LNCS, vol. 7658, pp. 598–606. Springer, Berlin, Heidelberg (2012), https://doi.
org/10.1007/978-3-642-34961-4 36
24. Mizuki, T., Shizuya, H.: A formalization of card-based cryptographic protocols via
abstract machine. Int. J. Inf. Secur. 13(1), 15–23 (2014), https://doi.org/10.1007/
s10207-013-0219-4
25. Mizuki, T., Shizuya, H.: Computational model of card-based cryptographic protocols and its applications. IEICE Trans. Fundam. E100.A(1), 3–11 (2017),
https://doi.org/10.1587/transfun.E100.A.3
26. 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. LNCS,
vol. 5598, pp. 358–369. Springer, Berlin, Heidelberg (2009), https://doi.org/10.
1007/978-3-642-02270-8 36
27. Moran, T., Naor, M.: Basing cryptographic protocols on tamper-evident seals.
Theor. Comput. Sci. 411(10), 1283 – 1310 (2010), https://doi.org/10.1016/j.tcs.
2009.10.023
28. Murata, S., Miyahara, D., Mizuki, T., Sone, H.: Public-PEZ cryptography. In:
Susilo, W., Deng, R.H., Guo, F., Li, Y., Intan, R. (eds.) Information Security.
LNCS, vol. 12472, pp. 59–74. Springer, Cham (2020), https://doi.org/10.1007/
978-3-030-62974-8 4
29. Nakai, T., Misawa, Y., Tokushige, Y., Iwamoto, M., Ohta, K.: Secure computation
for threshold functions with physical cards: Power of private permutations. New
Gener. Comput. pp. 1–19 (2022), https://doi.org/10.1007/s00354-022-00153-7, inpress
30. Nishida, T., Hayashi, Y., Mizuki, T., Sone, H.: Card-based protocols for any
Boolean function. In: Jain, R., Jain, S., Stephan, F. (eds.) Theory and Applications of Models of Computation. LNCS, vol. 9076, pp. 110–121. Springer, Cham(2015), https://doi.org/10.1007/978-3-319-17142-5 11
31. Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: Pile-shifting scramble for cardbased protocols. IEICE Trans. Fundam. 101(9), 1494–1502 (2018), https://doi.
org/10.1587/transfun.E101.A.1494

Card-minimal Protocols for Symmetric Boolean Functions

19

32. Ono, H., Manabe, Y.: Card-based cryptographic logical computations using private
operations. New Gener. Comput. 39(1), 19–40 (2021), https://doi.org/10.1007/
s00354-020-00113-z
33. Ruangwises, S., Itoh, T.: Securely computing the n-variable equality function with
2n cards. Theor. Comput. Sci. 887, 99–110 (2021), https://doi.org/10.1016/j.tcs.
2021.07.007
34. Shinagawa, K.: On the Construction of Easy to Perform Card-Based Protocols.
Ph.D. thesis, Tokyo Institute of Technology (2020)
35. Shinagawa, K., Mizuki, T.: The six-card trick: Secure computation of three-input
equality. In: Lee, K. (ed.) Information Security and Cryptology. LNCS, vol. 11396,
pp. 123–131. Springer, Cham (2019), https://doi.org/10.1007/978-3-030-12146-4 8
36. Shinagawa, K., Mizuki, T., Schuldt, J., Nuida, K., Kanayama, N., Nishide, T.,
Hanaoka, G., Okamoto, E.: Card-based protocols using regular polygon cards.
IEICE Trans. Fundam. E100.A(9), 1900–1909 (2017), https://doi.org/10.1587/
transfun.E100.A.1900
37. Toyoda, K., Miyahara, D., Mizuki, T.: Another use of the five-card trick:
Card-minimal secure three-input majority function evaluation. In: Adhikari, A.,
Küsters, R., Preneel, B. (eds.) Progress in Cryptology – INDOCRYPT 2021.
LNCS, vol. 13143, pp. 536–555. Springer, Cham (2021), https://doi.org/10.1007/
978-3-030-92518-5 24
38. Yao, A.C.: Protocols for secure computations. In: Foundations of Computer Science. pp. 160–164. IEEE Computer Society, Washington, DC, USA (1982), https://doi.org/10.1109/SFCS.1982.88