Few-helping-card Protocols for Some Wider Class of Symmetric
Boolean Functions with Arbitrary Ranges
Hayato Shikata

Daiki Miyahara

Takaaki Mizuki

Graduate School of Information
Sciences, Tohoku University
Sendai, JapanThe University ofElectro-Communications
National Institute of Advanced
Industrial Science and Technology
Tokyo, Japan

Cyberscience Center, Tohoku
University
National Institute of Advanced
Industrial Science and Technology
Sendai, Japan

ABSTRACTIn card-based cryptography, which uses a physical deck of cards torealize secure multiparty computations, a one-bit value is usually
encoded by a pair of cards. Thus, when performing a secure computation of an 𝑛-input Boolean function, a sequence of 2𝑛 cards
representing 𝑛 bits is needed for input, and some helping cards are
typically added to form a protocol. In 2020, Ruangwises and Itohconstructed a card-based protocol for a symmetric Boolean function with an arbitrary range using two helping cards. (Note that asymmetric Boolean function depends only on the number of 1s in
its input). At the same time, they showed that the helping cards canbe eliminated if the target function is limited to “doubly symmetric”
Boolean functions (also known as symmetric self-anti-dual functions). A doubly symmetric Boolean function satisfies the following
for all 𝑘: when inputting exactly a number 𝑘 of 1s, the output isthe same as the output when inputting exactly a number 𝑛 − 𝑘 of
1s. In this paper, we loosen the restriction on doubly symmetric
Boolean functions by fixing 𝑘 = 0, and construct new protocols
which require less than two helping cards for that wider class of
symmetric Boolean functions. Specifically, we design a one-helpingcard protocol for any 𝑛 > 4, and helping-card-free protocols for𝑛 = 3 and 𝑛 = 4.

CCS CONCEPTS• Security and privacy → Cryptography.

KEYWORDS
Card-based cryptography, Secure computation, Real-life hands-on
cryptography, Card-based protocols
ACM Reference Format:
Hayato Shikata, Daiki Miyahara, and Takaaki Mizuki. 2023. Few-helpingcard Protocols for Some Wider Class of Symmetric Boolean Functions with
Arbitrary Ranges. In Proceedings of the10th ACM Asia Public-Key Cryptography Workshop (APKC ’23), July 10, 2023, Melbourne, VIC, Australia. ACM,
New York, NY, USA, 9 pages. https://doi.org/10.1145/3591866.3593073

1

INTRODUCTION

Secure multiparty computations enable us to obtain the output valueof a predetermined function while keeping information on input
APKC ’23, July 10, 2023, Melbourne, VIC, Australia© 2023 Copyright held by the owner/author(s).
This is the author’s version of the work. It is posted here for your personal use. Not forredistribution. The definitive Version of Record was published in Proceedings of the10th
ACM Asia Public-Key Cryptography Workshop (APKC ’23), July 10, 2023, Melbourne,
VIC, Australia, https://doi.org/10.1145/3591866.3593073.

values secret. Card-based cryptography achieves secure multiparty
computations using a deck of physical cards, and the research area
has been significantly growing in recent years (c.f. [18, 19]); refer
to [9, 10, 22, 35] for surveys.
In card-based cryptography, a one-bit value is typically represented with the order of a black card ♣ and a red card ♥ according
to the two-card-per-bit encoding:♣ ♥ = 0,♥ ♣ = 1.

(1)

When two face-down cards represent a bit 𝑥 ∈ {0, 1} according to
Eq. (1), we call these two cards a commitment to 𝑥 and denote it by
? ? ,
|{z}
𝑥

where we assume that all black ♣ and red cards ♥ have the identicalbacks ? .
Given a number of commitments as input, a card-based cryptographic protocol (simply referred to as a protocol often hereinafter)
should perform a secure multiparty computation via a series ofactions, such as turning over and shuffling cards.

1.1

Protocol for Symmetric Functions

This paper deals with card-based cryptographic protocols for “symmetric” Boolean functions. An 𝑛-input Boolean function 𝑓 : {0, 1}𝑛 →𝑅 with some set 𝑅 (as its range) is said to be symmetric if 𝑓 satisfies
the following for every 𝑖 and 𝑗, 1 ≤ 𝑖, 𝑗 ≤ 𝑛:𝑓 (𝑥 1, . . . , 𝑥𝑖 , . . . , 𝑥 𝑗 , . . . , 𝑥𝑛 ) = 𝑓 (𝑥 1, . . . , 𝑥 𝑗 , . . . , 𝑥𝑖 , . . . , 𝑥𝑛 ).
Because one bit is encoded with two cards as per the encoding
rule (1) above, any protocol for an 𝑛-input Boolean function requires
at least 2𝑛 cards. That is, it takes 𝑛 commitments corresponding to
𝑛 inputs 𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ∈ {0, 1}? ? ? ? ··· ? ? .
|{z} |{z}
|{z}
𝑥1

𝑥2

𝑥𝑛

In addition to the 𝑛 input commitments, some helping cards (like♣ ♥ ♣ ♥ ) are often required as input. Thus, a protocol for an
𝑛-input Boolean function 𝑓 takes 𝑛 commitments to 𝑥 1, 𝑥 2, . . . , 𝑥𝑛
along with some helping cards as input, applies a series of actions,such as revealing and shuffling cards, and outputs only the value

APKC ’23, July 10, 2023, Melbourne, VIC, Australiaof 𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ):? ? ? ? ··· ? ? ♣ ♥ ♣ ♥ ···|{z} |{z}
|{z}
𝑥1

𝑥2

𝑥𝑛

→ · · · → 𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ).
When devising new protocols, a smaller number of helping cards is
considered to be preferable.
In 2020, Ruangwises and Itoh [30, 32] proposed a generic way forconstructing a protocol with two helping cards for any symmetric
Boolean function 𝑓 : {0, 1}𝑛 → 𝑅 with an arbitrary range 𝑅:i? ? ? ? · · · ? ? ♣ ♥ → . . . → 𝑓 (𝑥 1, 𝑥 2, · · · , 𝑥𝑛 ).
|{z} |{z}
|{z}
𝑥1

𝑥2

𝑥𝑛

This is a non-trivial upper bound on the number of required helping
cards for any symmetric Boolean function having an arbitrary range
𝑅 (which is not necessarily two-valued but can be multi-valued,
say 𝑅 = {0, 1, 2, . . . , 𝑛}). It is open to determine whether the upperbound, i.e., two helping cards, are necessary or could be lowered.
Ruangwises and Itoh [30, 32] also considered the class of “doubly
symmetric” Boolean functions as a subclass of symmetric Booleanfunctions to construct a helping-card-free protocol, as follows. If asymmetric Boolean function 𝑓 satisfies
𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ) = 𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 )for all 𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ∈ {0, 1}, then 𝑓 is called a doubly symmetric
Boolean function (also known as a symmetric anti-self-dual function). For any doubly symmetric Boolean function 𝑓 : {0, 1}𝑛 → 𝑅
with an arbitrary range 𝑅, they constructed a protocol without any
helping card:? ? ? ? · · · ? ? → . . . → 𝑓 (𝑥 1, 𝑥 2, · · · , 𝑥𝑛 ).
|{z} |{z}
|{z}
𝑥1

𝑥2

𝑥𝑛

Thus, we have a helping-card-free protocol for any function in thisnarrow class.
To summarize, the existing research [30, 32] gives the following
theorem.
Theorem 1.1 ([30, 32]). Let 𝑛 ≥ 2, let 𝑅 be an arbitrary set, andlet 𝑓 : {0, 1}𝑛 → 𝑅 be a symmetric Boolean function.
• There is a two-helping-card protocol for 𝑓 .
• If 𝑓 is doubly symmetric, there is a helping-card-free protocol
for 𝑓 .
To provide better bounds on the number of required helping
cards (than Theorem 1.1) is an important open problem.

1.2

Contribution

This paper tackles the aforementioned open problem and presents
a partial answer to it. For this purpose, we define “partially doubly
symmetric” Boolean functions as a wider subclass of symmetric
Boolean functions than the class of doubly symmetric Booleanfunctions, and construct a protocol requiring less than two helping
cards for any function in that wider class.
i It should be noted that, as will be seen in Sect. 3, the output value is not given as asimple encoding.

Hayato Shikata, Daiki Miyahara, and Takaaki Mizuki

To define “partially doubly symmetric” Boolean functions, first,
let us review the basic properties of symmetric Boolean functions.
Let 𝑓 : {0, 1}𝑛 → 𝑅 be a symmetric Boolean function. The value of
its output 𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ) depends only on the number of 1s in theÍinput, i.e., the sum 𝑛𝑖=1 𝑥𝑖 . In other words, there exists a function
𝑔 : {0, 1, . . . , 𝑛} → 𝑅 such that!
𝑛∑︁𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ) = 𝑔
𝑥𝑖
(2)
𝑖=1

for every 𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ∈ {0, 1}. Bearing this in mind, observe thatfor a doubly symmetric Boolean function, the output value when
the sum is 𝑘 is equal to the one when the sum is 𝑛 − 𝑘. Thus, for a
doubly symmetric Boolean function 𝑓 , the corresponding function
𝑔 in Eq. (2) satisfies the following:𝑔(0) = 𝑔(𝑛),𝑔(1) = 𝑔(𝑛 − 1),
..
.

(3)

𝑔(⌊(𝑛 − 1)/2⌋) = 𝑔(𝑛 − ⌊(𝑛 − 1)/2⌋) .
As known from the list of equations (3) above, doubly symmetric
Boolean functions represent a quite restricted subclass within theclass of symmetric Boolean functions. In this paper, we relax the restriction and consider a class that imposes only the topmost restriction 𝑔(0) = 𝑔(𝑛) in the list (3), which we call “{0}-partially doubly
symmetric” Boolean functions; we will construct few-helping-card
protocols for this wider class.
More generally, for a set 𝐼 ⊆ {0, 1, . . . , ⌊(𝑛 − 1)/2⌋}, we define
an 𝐼 -partially doubly symmetric Boolean function, as follows.
Definition 1.2. Let 𝑓 : {0, 1}𝑛 → 𝑅 be a symmetric Booleanfunction, let 𝑔 : {0, 1, . . . , 𝑛} → 𝑅 be the function satisfying Eq. (2),and let 𝐼 ⊆ {0, 1, . . . , ⌊(𝑛 − 1)/2⌋}. If 𝑔(𝑘) = 𝑔(𝑛 −𝑘) for every 𝑘 ∈ 𝐼 ,then 𝑓 is called an I-partially doubly symmetric Boolean function.
Under this definition, a doubly symmetric Boolean function
is redefined as a {0, 1, . . . , ⌊(𝑛 − 1)/2⌋}-partially doubly symmetric Boolean function, and a symmetric Boolean function is an ∅partially doubly symmetric Boolean function (where ∅ denotes theempty set).
As mentioned above, the main target of this paper is {0}-partiallydoubly symmetric Boolean functions. That is, we will design aprotocol for any symmetric Boolean function that outputs the samevalue when the number of 1s in the input is 0 and when it is 𝑛;more simply, our target is any 𝑛-input symmetric Boolean function
𝑓 such that 𝑓 (0, 0, . . . , 0) = 𝑓 (1, 1, . . . , 1).
Specifically, we will construct few-helping-card protocols, divided into three cases, 𝑛 = 3, 𝑛 = 4, and 𝑛 ≥ 5. First, for the caseof 𝑛 = 3, we will show that one can obtain a protocol without any
helping card (Sect. 4):? ? ? ? ? ? → · · · → 𝑓 (𝑥 1, 𝑥 2, 𝑥 3 ) .
|{z} |{z} |{z}
𝑥1

𝑥2

𝑥3

Next, for the case of 𝑛 = 4, we will also show that we need no
helping card (Sect. 5):? ? ? ? ? ? ? ? → · · · → 𝑓 (𝑥 1, 𝑥 2, 𝑥 3, 𝑥 4 ) .
|{z} |{z} |{z} |{z}
𝑥1

𝑥2

𝑥3

𝑥4

Few-helping-card Protocols for Some Wider Class of Symmetric Boolean Functions with Arbitrary Ranges

Next, we will design a protocol with one helping card for the caseof 𝑛 ≥ 5 (Sect. 6):? ? ? ? · · · ? ? ♥ → · · · → 𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ) .
|{z} |{z}
|{z}
𝑥1

𝑥2

𝑥𝑛

Finally, when 𝑛 = 2, we will state that for any 2-input symmetric
Boolean function, without limiting ourselves to partially doubly
symmetric Boolean functions, a helping-card-free protocol can beconstructed by simply making use of the existing method (Sect. 7):? ? ? ? → · · · → 𝑓 (𝑥 1, 𝑥 2 ) .
|{z} |{z}𝑥1𝑥2

The following theorem summarizes our contribution in this paper.
Theorem 1.3. Let 𝑛 ≥ 2, let 𝑅 be an arbitrary set, and let 𝑓 :{0, 1}𝑛 → 𝑅 be a symmetric Boolean function.
• If 3 ≤ 𝑛 ≤ 4 and 𝑓 is {0}-partially doubly symmetric, there isa helping-card-free protocol for 𝑓 .
• If 𝑛 ≥ 5 and 𝑓 is {0}-partially doubly symmetric, there is a
one-helping-card protocol for 𝑓 .
• If 𝑛 = 2, there is a helping-card-free protocol for 𝑓 .
The above results and the existing studies are summarized inTable 1.
Before going to the next subsection, we display an example
of a {0}-partially doubly symmetric Boolean function. Define asymmetric Boolean function ℎ : {0, 1}9 → {0, 1, 2} asÍ9
1 if 𝑖=1
𝑥𝑖 = 4,Í9ℎ(𝑥 1, 𝑥 2, . . . , 𝑥 9 ) = 2 if 𝑖=1(4)
𝑥𝑖 = 8,
 0 otherwise.
Then, ℎ is a {0}-partially doubly symmetric Boolean function (because ℎ(0, 0, . . . , 0) = ℎ(1, 1, . . . , 1) = 0). A secure computation ofthis function ℎ allows nine players to know only if four or eight people among them want to play a four-player game, such as mahjong,
without awkwardness.

1.3

Related Work

The purpose of this paper is to construct protocols with a small
number of helping cards for symmetric Boolean functions with
arbitrary ranges.
Although protocols for arbitrary functions (having arbitrary
domains and ranges) can be constructed if a sufficient numberof helping cards are available [2], most of the existing research
has focused on Boolean functions with range {0, 1}, i.e., functions
𝑓 : {0, 1}𝑛 → 𝑅 with 𝑅 = {0, 1}. It is known that any Boolean function with range {0, 1} can be securely computed using six helping
cards [25]; this is a general upper boundii . It was also shown that
two helping cards are sufficient when limited to symmetric Booleanfunctions [25]. A recent study [34] has shown that no helping card isneeded for symmetric Boolean functions 𝑓 : {0, 1}𝑛 → {0, 1} when𝑛 ≥ 8. There are also several specific functions for which there exist
helping-card-free protocols: the two-input AND function [12, 20],
the three-input AND function [7, 17], the XOR function [23], the

APKC ’23, July 10, 2023, Melbourne, VIC, Australia

three-input majority function [41], and the three-input equality
function [6, 36].
Remember that our target functions 𝑓 : {0, 1}𝑛 → 𝑅 in thispaper have arbitrary ranges 𝑅.
As mentioned at the beginning of this paper, the research areaof card-based cryptography is very active recently, especially, inthe following topics: private-model secure computations [1, 13,24], zero-knowledge proof protocols [3, 28, 29, 33], novel shuffling
operations [16], secure sorting [5], multi-valued protocols with adirection encoding [39], the half-open action [15], standard-deck
protocols [4, 11], and applications to private simultaneous messages
protocols [38].

2

PRELIMINARIESIn this section, we describe the existing encoding and methods aswell as the shuffling operation our protocols use.
Card-based cryptographic protocols are formally defined via abstract machines [8, 21, 22]. Roughly speaking, a protocol consists ofthree actions, (turn,𝑇 ), (perm, 𝜋), and (shuf, Π), which represent
turning over, permuting, and shuffling cards, respectively (where
𝑇 is a set of positions, 𝜋 is a permutation, and Π is a set of permutations). In the sequel, for simplicity, instead of giving an abstract
machine, we use a natural language to describe a protocol.

2.1

Encoding of Integer by Card Position

As mentioned in Sect. 1.2, the output value of a symmetric Booleanfunction depends on the sum of the input bits. Thus, to securely
compute a symmetric Boolean function, given 𝑛 commitments? ? ? ? ··· ? ?
|{z} |{z}
|{z}
𝑥1

𝑥2

𝑥𝑛

Í
and some helping cards, we want to obtain the sum 𝑛𝑖=1 𝑥𝑖 being
kept secret. For this, we need to encode integers with cards (tomaintain the sum).
The existing Ruangwises–Itoh protocols [30, 32] employ thefollowing integer encoding. Suppose that 𝑘 ≥ 2 and that we want
to represent an integer 𝑖, 0 ≤ 𝑖 ≤ 𝑘 − 1, with cards. Using 𝑘 cards
consisting of one ♣ and 𝑘 −1 ♥ s, the integer 𝑖 is encoded by placing
the ♣ at the (𝑖 + 1)-st as follows:
1 2

𝑖 𝑖+1 𝑖+2𝑘

♥ ♥ ··· ♥ ♣ ♥ ··· ♥ .
Hereinafter, such a sequence of face-down cards (representing 𝑖) is
denoted by 𝐸𝑘♣ (𝑖) and written as:? ? ··· ? .
| {z }
𝐸𝑘♣ (𝑖 )Exchanging the colors (♣ and ♥), 𝐸𝑘♥ (𝑖) is defined in a similar way.
As will be seen later, the existing Ruangwises–Itoh protocol [30,32] and our proposed protocols perform the addition of input commitments based on the integer encoding above in order to compute
symmetric Boolean functions.iii

ii If we allow protocols to fail with a high probability, there is a helping-card-freeiii This integer encoding is also used in card-based zero-knowledge protocols [27, 31],

protocol for any Boolean function [12].

secure ranking protocols [40], and card-based Yao’s millionaire protocols [14].

APKC ’23, July 10, 2023, Melbourne, VIC, Australia

Hayato Shikata, Daiki Miyahara, and Takaaki Mizuki.
Table 1: Numbers of helping cards required by the existing and our proposed protocols for 𝐼 -partially doubly symmetric Booleanfunctions with 𝑛 inputs𝐼𝑛# of helping cards

Ruangwises and Itoh [30, 32]

∅

≥2

2

Ruangwises and Itoh [30, 32]{0, . . . , ⌊ 𝑛−1
2 ⌋}

≥2

0

This paper, §4

{0}

3

0

This paper, §5

{0}

4

0

This paper, §6

{0}

≥5

1

This paper, §7

∅

2

0

Note that a commitment to 𝑎 ∈ {0, 1} together with a free card
♥ can be converted to 𝐸 3♣ (𝑎), i.e., place the ♥ to the right of thecommitment and turn it over:? ? ♥ → ? ? ?,|{z}
| {z }
𝐸 3♣ (𝑎)𝑎because the commitment satisfies the encoding:♣ ♥ = 0,2.3

Addition of Encoded Integers

Ruangwises and Itoh [30, 32] proposed the following method foradding two encoded integers. Our proposed protocol also employs
this integer addition method.
(1) We have sequences of 𝐸𝑘♣ (𝑎) and 𝐸𝑘♥ (𝑏) representing two
integers 𝑎 and 𝑏, respectively. For convenience, each card isnamed as follows:♥ ♣ = 1.

Similarly, a commitment to 𝑎 ∈ {0, 1} together with a ♣ can beconverted to 𝐸 3♥ (𝑎) by swapping the two cards of the commitment:

𝐸𝑘♣ (𝑎) : ? ? · · · ? ,𝐸𝑘♥ (𝑏) : ? ? · · · ? .

𝑥0 𝑥1

𝑦0 𝑦1

𝑦𝑘 −1 𝑦𝑘 −2

𝑦0? ? ? ? ··· ? ? .
𝑥0? ? ♣ → ? ? ♣ → ? ? ? .
|{z}
|{z}
| {z }

2.2

𝑦𝑘 −1(2) Rearrange the sequences as follows:

←→

𝑎

𝑥𝑘 −1

𝑦𝑘 −1

?

Pile-Shifting Shuffle𝑥0

We describe one of the most commonly used shuffling operations
in card-based protocols: the pile-shifting shuffle [26, 37]. As an
example, let us assume that there are nine cards divided into threepiles.
(1) Divide a sequence of nine cards into piles of the same numberof cards:
1 2 3

4 5 6

7 8 9

? ? ?

? ? ?

? ? ? .

𝑥𝑘 −1

(3) Apply a pile-shifting shuffle as follows:"#

𝐸 3♥ (𝑎)𝑎𝑥1(2) Cyclically shuffle the three piles without changing the orderof the three cards within each pile. The resulting order ofthe piles will be one of the following three patterns, eachwith equal probability:

?

𝑦𝑘 −2

?

?

𝑦0

𝑥1

𝑦𝑘−1−𝑟 𝑦𝑘−2−𝑟

? ?

···

𝑦0−𝑟

→ ? ? ? ? ··· ? ? ,

𝑥𝑘 −1

𝑥 0+𝑟

𝑥 1+𝑟

𝑥𝑘−1+𝑟where 𝑟 is a random value.
(4) Rearrange these as they were before, as follows:𝐸𝑘♣ (𝑎 − 𝑟 ) : ?

? ···𝑥 0+𝑟 𝑥 1+𝑟

𝐸𝑘♥ (𝑏 + 𝑟 ) : ?

? ,𝑥𝑘 −1+𝑟? ···𝑦0−𝑟 𝑦1−𝑟? ,𝑦𝑘 −1−𝑟where 𝑎 is subtracted by 𝑟 and 𝑏 is added by 𝑟 .
(5) Reveal the sequence of 𝐸𝑘♥ (𝑏 + 𝑟 ), and let 𝑠 = 𝑏 + 𝑟 . Then,
cyclically shift the sequence of 𝐸𝑘♣ (𝑎 − 𝑟 ) to the right by 𝑠,i.e., 𝑠 is added to 𝑎 − 𝑟 :𝐸𝑘♣ (𝑎 − 𝑟 ) : ?

? ···𝑥 0+𝑟 𝑥 1+𝑟?
𝑥𝑘 −1+𝑟↓h 1 2 3
? ? ?

4 5 6

7 8 9

? ? ?

? ? ?

i

𝐸𝑘♣ (𝑎 + 𝑏) :?

?

𝑥 0+𝑟 −𝑠 𝑥 1+𝑟 −𝑠
1 2 3




? ? ?


7 8 9

→ ? ? ?


4 5 6

? ? ?

4 5 6

7 8 9

? ? ? ? ? ?,
1 2 3

4 5 6

? ? ? ? ? ?,
7 8 9

1 2 3

? ? ? ? ? ? .

We denote the application of a pile-shifting shuffle by [ · | · · · | · ].

···

?

.

𝑥𝑘 −1+𝑟 −𝑠

Note that when the sequence of 𝐸𝑘♥ (𝑏 + 𝑟 ) is revealed, thevalue of 𝑏 does not leak because the random value 𝑟 wasadded to 𝑏.
This is a secure computation of (𝑎 − 𝑟 ) + (𝑏 + 𝑟 ) = 𝑎 + 𝑏 without
leaking the values of 𝑎 and 𝑏. That is, a sequence of 𝐸𝑘♣ (𝑎 + 𝑏) is
obtained.

Few-helping-card Protocols for Some Wider Class of Symmetric Boolean Functions with Arbitrary Ranges

In the current explanation, 𝐸𝑘♣ (𝑎) and 𝐸𝑘♥ (𝑏) are added; othertypes of pairs, such as a pair of 𝐸𝑘♥ (𝑎) and 𝐸𝑘♣ (𝑏) and a pair of 𝐸𝑘♣ (𝑎)and 𝐸𝑘♣ (𝑏), can be also added, of course.

2.4

Addition of Two Commitments

Shikata et al. [34] proposed the following helping-card-free twocommitment addition that produces 𝐸 3♣ (𝑎 + 𝑏) or 𝐸 3♥ (𝑎 + 𝑏) fromtwo given commitments to 𝑎, 𝑏 ∈ {0, 1} (without any helping card).
(1) Apply a pile-shifting shuffle to the commitments to 𝑎 and 𝑏
as follows:? ? ? ? → ? ? ? ? → ? ? ? ? .
|{z} |{z}𝑎𝑏(Such a shuffle is also called a random bisection cut [23].)(2) Apply a pile-shifting shuffle to the middle two cards (in thiscase, it is a normal shuffle):


? ? ?
? → ? ? ? ? .
(3) Reveal the second card from the left.
(a) If it is ♣ , we obtain a sequence of 𝐸 3♣ (𝑎 +𝑏) by rearranging
as follows:
1 2 3 41 3 4

2

? ♣ ? ? → ? ? ? ♣.
| {z }(b) If it is ♥ , we obtain a sequence of 𝐸 3♥ (𝑎 +𝑏) by rearranging
as follows:
1 2 3 44 3 1

♣ ( Í𝑛 𝑥 ) is ♣,Notice that if the (𝑖 + 1)-st face-down card in 𝐸𝑛+1𝑖=1 𝑖then 𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ) = 𝑔(𝑖). Therefore, for each 𝑗 ∈ 𝑅, we collectall (𝑖 + 1)-st cards such that 𝑔(𝑖) = 𝑗, shuffle all the collected cards,
and reveal them; if a ♣ appears, then it implies 𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ) = 𝑗.
As an example, let 𝑓 be the parity function, i.e., if 𝑖 is even, 𝑔(𝑖) =0; otherwise, 𝑔(𝑖) = 1. Then, after collecting all cards whose posi♣ ( Í𝑛 𝑥 ), we shuffle all the collectedtions are odd numbers in 𝐸𝑛+1𝑖=1 𝑖
cards and reveal them. If a ♣ appears, then 𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ) = 0;otherwise, 𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ) = 1.
For another example, let 𝑓 be the function ℎ defined in Eq. (4)in Sect. 1.2. Then, we reveal the fifth and ninth cards to see if a
♣ appears, i.e., if ℎ(𝑥 1, 𝑥 2, . . . , 𝑥 9 ) = 1 and ℎ(𝑥 1, 𝑥 2, . . . , 𝑥 9 ) = 2,
respectively (here, we do not have to shuffle a single card).
♣ ( Í𝑛 𝑥 ), we can know only the value ofIn this way, from 𝐸𝑛+1𝑖=1 𝑖𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ), i.e., we can securely compute 𝑓 (𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ).
For the case of doubly symmetric Boolean functions, Ruangwises
and Itoh [30, 32] pointed out that two cards can be revealed byadding a common random bit to all input commitments, so thatthey become two free cards. The obtained two free cards can beused in the integer addition. Based on these ideas, they proposeda helping-card-free protocol for any doubly symmetric Booleanfunction.

3.2

𝐸 3♣ (𝑎 + 𝑏 )2? ♥ ? ? → ? ? ? ♥.
| {z }
𝐸 3♥ (𝑎 + 𝑏 )APKC ’23, July 10, 2023, Melbourne, VIC, Australia

Our Approach

As mentioned before, this paper focuses on {0}-partially doubly
symmetric Boolean functions 𝑓 : {0, 1}𝑛 → 𝑅. In this case, thefunction 𝑔 satisfying Eq. (2) has the property that 𝑔(0) = 𝑔(𝑛).
Therefore, the function 𝑔 also satisfies
!
!
𝑛
𝑛
∑︁
∑︁
𝑔
𝑥𝑖 = 𝑔𝑥𝑖 mod 𝑛 .
𝑖=1

In this way, from commitments to 𝑎 and 𝑏, we obtain a sequenceof either 𝐸 3♣ (𝑎 + 𝑏) or 𝐸 3♥ (𝑎 + 𝑏) (with a probability of 1/2) as wellas one free card. This subprotocol will be also employed in our
proposed protocols.

3

Because 0 ≤ ( 𝑖=1 𝑥𝑖 mod 𝑛) ≤ 𝑛 − 1, this value is represented♣ ( Í𝑛 𝑥 ), it suffices toby 𝑛 cards. This implies that instead of 𝐸𝑛+1
𝑖=1 𝑖
Í𝑛
♣
obtain 𝐸𝑛 ( 𝑖=1 𝑥𝑖 mod 𝑛):? ? ··· ? ,| {z }IDEA BEHIND OUR PROPOSED PROTOCOLSIn this section, we describe the idea behind our proposed protocols
for {0}-partially doubly symmetric Boolean functions. We first
give an overview of the two existing protocols of Ruangwises andItoh [30, 32]: one is for symmetric Boolean functions and the otheris for doubly symmetric Boolean functions. We then present theproperties of {0}-partially doubly symmetric Boolean functions,and based on them, we show the strategy for reducing the numberof helping cards.

3.1

𝑖=1

Í𝑛

Existing Protocols

Let 𝑓 : {0, 1}𝑛 → 𝑅 be a symmetric Boolean function, and let
𝑔 : {0, 1, . . . , 𝑛} → 𝑅 be the function satisfying Eq. (2). The existing
protocol [30, 32] takes commitments to 𝑥 1, 𝑥 2, . . . , 𝑥𝑛 ∈ {0, 1} andtwo helping cards as input and uses the integer addition describedÍin Sect. 2.3 repeatedly to obtain a sequence encoding 𝑛𝑖=1 𝑥𝑖 , i.e.,Í♣ ( 𝑛 𝑥 ):
𝐸𝑛+1
𝑖=1 𝑖
? ? ? ? ··· ? ? ♣ ♥ → ··· → ? ? ? ··· ? .
|{z} |{z}
|{z}
|
{z
}
𝑥1

𝑥2

𝑥𝑛

♣ (
𝐸𝑛+1

Í𝑛

𝑖=1 𝑥𝑖 )

𝐸𝑛♣ (

Í𝑛

𝑖=1 𝑥𝑖 mod 𝑛)That is, one less card can be used for encoding, which contributes
to reducing the number of required helping cards, as will be seenin the next sections.

4

PROPOSED PROTOCOL FOR 𝑛 = 3

In this section, we construct a helping-card-free protocol for an
arbitrary {0}-partially doubly symmetric Boolean function for thecase of 𝑛 = 3.
Let 𝑓 : {0, 1}3 → 𝑅 be a {0}-partially doubly symmetric Booleanfunction to be securely computed. Since the proposed protocol
requires no helping card, the input to the protocol is? ? ? ? ? ? .
|{z} |{z} |{z}
𝑥1

𝑥2

𝑥3

Our protocol proceeds as follows.
(1) For the commitments to 𝑥 1 and 𝑥 2 , apply the helping-cardfree two-commitment addition described in Sect. 2.4. Assume

APKC ’23, July 10, 2023, Melbourne, VIC, Australia

Hayato Shikata, Daiki Miyahara, and Takaaki Mizuki.
Table 2: Value of 𝑥 1 + 𝑥 2 + 𝑥 3 and the sequence of cards

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

𝑋2
𝑋1
𝑋0
(shuf, id, 1 3 2 4 )𝑥1 + 𝑥2 + 𝑥3

Sequence of cards

0

♣ ♥ ♥

1

♥ ♣ ♥

2

♥ ♥ ♣

3

♣ ♥ ♥

(shuf, id, 1 2 3 4 )𝑥3

𝐸 3♣ (𝑥 1 + 𝑥 2 )♣? ? ?

𝑥3(2) Convert the commitment to 𝑥 3 together with the free card
♣ to 𝐸 3♥ (𝑥 3 ) by the method mentioned in Sect. 2.1:
? ? ? ? ? ♣ → ? ? ? ? ? ? .
| {z } |{z}| {z } | {z }𝐸 3♣ (𝑥 1 +𝑥 2 )𝐸 3♣ (𝑥 1 +𝑥 2 ) 𝐸 3♥ (𝑥 3 )𝑥3(3) Apply the integer addition described in Sect. 2.3 to 𝐸 3♣ (𝑥 1 +𝑥 2 )and 𝐸 3♥ (𝑥 3 ):

.

♡♣♣♡
𝑋2
♡♣♡♣
𝑋1
♡♡♣♣
𝑋0
-> (result, 2,3,4)

Figure 1: KWH-tree for the color conversion subprotocol
Here, we explain the case of converting 𝐸 3♣ (𝑥) to 𝐸 3♥ (𝑥).
(1) Place a helping card and turn it over as follows:♣ ? ? ? → ? ? ? ? .
| {z }? ? ? ? ? ? → ··· → ? ? ? ♣ ♣ ♥ .
| {z } | {z }| {z }

𝐸 3♣ (𝑥 1 +𝑥 2 ) 𝐸 3♥ (𝑥 3 )

1Τ 𝑋
2 2
1Τ 𝑋
2 2
1Τ 𝑋
2 1
1Τ 𝑋
2 1
1Τ 𝑋
2 0
1Τ 𝑋
2 0

𝐸 3♣ (𝑥 1 + 𝑥 2 + 𝑥 3 mod 3)

Here, as shown in Table 2, if 𝑥 1 + 𝑥 2 + 𝑥 3 = 3, the resulting three-card sequence becomes 𝐸 3♣ (0). Therefore, we have
𝐸 3♣ (𝑥 1 + 𝑥 2 + 𝑥 3 mod 3).
This is how 𝐸 3♣ (𝑥 1 + 𝑥 2 + 𝑥 3 mod 3) is generated for 𝑛 = 3, and as
explained in Sect. 3, it is possible to securely compute 𝑓 (𝑥 1, 𝑥 2, 𝑥 3 )from this.

(turn, 1 )♡? ? ?

? ? ? ? ? ? → ? ? ? ♣ ? ? .
|{z} |{z} |{z}| {z }
|{z}
𝑥2

𝑋1
1Τ 𝑋
2 0
1Τ 𝑋
2 0

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

without loss of generality that 𝐸 3♣ (𝑥 1 + 𝑥 2 ) and a free blackcard ♣ are obtained:

𝑥1

1Τ 𝑋
2 2
1Τ 𝑋
2 2

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

𝐸 3♣ (𝑥 )(2) Apply a random bisection cut as follows:? ? ? ?
→ ? ? ? ? .
(3) After rearranging the middle two cards, apply a random
bisection cut, and then rearrange the middle two cards again:←→? ? ? ? →

←→



? ?

? ?



→ ? ? ? ? .

(4) Reveal the left-most card:

5

PROPOSED PROTOCOL FOR 𝑛 = 4? ? ? ? .

In this section, we construct a helping-card-free protocol for an
arbitrary {0}-partially doubly symmetric Boolean function for thecase of 𝑛 = 4.
Let 𝑓 : {0, 1}4 → 𝑅 be a {0}-partially doubly symmetric Booleanfunction to be securely computed. Since the proposed protocol
requires no helping card, the input to the protocol is↑turn(a) If it is ♥ , then the remaining face-down cards represent
𝐸 3♥ (𝑥):♥ ? ? ? .
| {z }
𝐸 3♥ (𝑥 )? ? ? ? ? ? ? ? .
|{z} |{z} |{z} |{z}
𝑥1

𝑥2

𝑥3

We first present a subprotocol in Sect. 5.1 and then show themain protocol in Sect. 5.2.

5.1(b) If it is ♣ , then turn over the revealed card again, andreturn to Step 2.

𝑥4

Color Conversion Subprotocol

In our protocol presented in this section, we have a probabilistic casewhere an integer encoding based on some color must be converted
to the other color. For this, we propose a subprotocol to convert athree-card encoding of either color obtained by the helping-cardfree two-commitment addition described in Sect. 2.3 to the othercolor with one helping card.

This is the color conversion subprotocol, converting 𝐸 3♣ (𝑥) to 𝐸 3♥ (𝑥).
If we want to convert 𝐸 3♥ (𝑥) to 𝐸 3♣ (𝑥), then it suffices to just reverse♥ and ♣ and perform the same operations.
The security and correctness of this subprotocol is proved by its
KWH-tree [12] depicted in Fig. 1. Note that this subprotocol has aloop and is a Las Vegas algorithm.

5.2

Protocol Description

The proposed protocol for 𝑛 = 4 proceeds as follows.

Few-helping-card Protocols for Some Wider Class of Symmetric Boolean Functions with Arbitrary Ranges.
Table 3: Value of 𝑥 1 + 𝑥 2 + 𝑥 3 + 𝑥 4 and the sequence of cards
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4

Sequence of cards0♣ ♥ ♥ ♥

1♥ ♣ ♥ ♥

2♥ ♥ ♣ ♥

3♥ ♥ ♥ ♣

4♣ ♥ ♥ ♥

6

APKC ’23, July 10, 2023, Melbourne, VIC, Australia

PROPOSED PROTOCOL FOR 𝑛 ≥ 5

In this section, we construct a protocol for an arbitrary 𝑛-input{0}-partially doubly symmetric Boolean function such that 𝑛 ≥ 5.
The proposed protocol requires one helping card ♥ , and hence, theinput to the protocol is? ? ? ? ··· ? ? ♥ .
|{z} |{z}|{z}𝑥1(1) For the commitments to 𝑥𝑛−3 and 𝑥𝑛−2 , apply the helpingcard-free two-commitment addition described in Sect. 2.4.
Assume without loss of generality that 𝐸 3♣ (𝑥𝑛−3 + 𝑥𝑛−2 ) anda free black card ♣ are obtained:? ? ··· ? ? ? ? ? ? ? ? ♥|{z}|{z} |{z} |{z} |{z}
𝑥1

𝑥𝑛−3

𝑥3

𝑥4

𝐸 3♣ (𝑥 1 + 𝑥 2 )𝑥3? ? ? ♣ ? ? ? ? → ? ? ? ♣ ? ? ? ♥.
| {z }|{z} |{z}| {z }| {z }𝑥3

𝑥4

𝐸 3♣ (𝑥 1 +𝑥 2 )𝐸 3♥ (𝑥 3 +𝑥 4 )(3) Convert 𝐸 3♣ (𝑥 1 + 𝑥 2 ) and 𝐸 3♥ (𝑥 3 + 𝑥 4 ) together with the freecards ♥ and ♣ to 𝐸 4♣ (𝑥 1 + 𝑥 2 ) and 𝐸 4♥ (𝑥 3 + 𝑥 4 ), respectively,
in a similar way to the method mentioned in Sect. 2.1:

𝑥1

𝐸 3♥ (𝑥 3 +𝑥 4 )𝐸 3♣ (𝑥 1 +𝑥 2 )𝐸 3♥ (𝑥 3 +𝑥 4 )→ ? ? ? ? ? ? ? ? .
| {z } | {z }𝐸 4♣ (𝑥 1 +𝑥 2 )𝐸 4♥ (𝑥 3 +𝑥 4 )(4) Apply the integer addition described in Sect. 2.3 to 𝐸 4♣ (𝑥 1 +𝑥 2 )and 𝐸 4♥ (𝑥 3 + 𝑥 4 ):? ? ? ? ? ? ? ? → ··· → ? ? ? ? ♥ ♣ ♣ ♣ .
| {z } | {z }| {z }
𝐸 4♣ (𝑥 1 +𝑥 2 )𝐸 4♥ (𝑥 3 +𝑥 4 )𝑥𝑛𝐸 3♣ (𝑥𝑛−3 +𝑥𝑛−2 )

𝑥𝑛−1

𝑥𝑛

(2) To the commitments to 𝑥𝑛−1 and 𝑥𝑛 together with the freecards ♣ and ♥ , apply the integer addition described in
Sect. 2.3:
? ? ··· ? ? ? ♣ ? ? ? ? ♥|{z}| {z }|{z} |{z}𝑥1

𝐸 3♣ (𝑥𝑛−3 +𝑥𝑛−2 )

𝑥𝑛−1

𝑥𝑛

𝐸 3♣ (𝑥𝑛−3 +𝑥𝑛−2 ) 𝐸 3♥ (𝑥𝑛−1 +𝑥𝑛 )𝑥1

Note that we apply the addition so that 𝐸 3♥ (𝑥𝑛−1 + 𝑥𝑛 ) is
obtained.
(3) Convert the commitments to 𝑥 1 and 𝑥 2 together with ♥and ♣ to 𝐸 3♣ (𝑥 1 ) and 𝐸 3♥ (𝑥 2 ), and apply the integer addition
described in Sect. 2.3, obtaining 𝐸 3♣ (𝑥 1 + 𝑥 2 ):? ? ♥ ? ? ♣ → ? ? ? ♣ ♣ ♥.
|{z} |{z}| {z }
𝑥1

𝐸 3♣ (𝑥 1 + 𝑥 2 )𝑥2(4) Similar to the previous step, add the commitments to 𝑥 3 , 𝑥 4 ,♣ ( Í𝑛−4 𝑥 ):. . ., 𝑥𝑛−4 to 𝐸 3♣ (𝑥 1 +𝑥 2 ) one by one, obtaining 𝐸𝑛−3
𝑘=1 𝑘
? ? ? ? ? ··· ? ? ♣ ♣ ♥ ♥| {z } |{z}|{z}𝐸 3♣ (𝑥 1 +𝑥 2 )

𝑥3

𝑥𝑛−4

→ ? ? ? ? ··· ? ? ♣ ♣ ♣ ♥ ♥| {z }|{z}
𝐸 4♣(𝑥 1 +𝑥 2 +𝑥 3 )𝑥𝑛−4

𝐸 4♣ (𝑥 1 + 𝑥 2 + 𝑥 3 + 𝑥 4 mod 4)Here, as shown in Table 3, if 𝑥 1 + 𝑥 2 + 𝑥 3 + 𝑥 4 = 4, theresulting four-card sequence becomes 𝐸 4♣ (0). Therefore, wehave 𝐸 4♣ (𝑥 1 + 𝑥 2 + 𝑥 3 + 𝑥 4 mod 4).
This is how 𝐸 4♣ (𝑥 1 + 𝑥 2 + 𝑥 3 + 𝑥 4 mod 4) is generated for 𝑛 = 4,
and as explained in Sect. 3, it is possible to securely compute𝑓 (𝑥 1, 𝑥 2, 𝑥 3, 𝑥 4 ) from this.

? ? ? ♣ ♥ ♥.
| {z }→ ··· → ? ? ··· ? ? ?
|{z}| {z }? ? ? ♣ ? ? ? ♥ → ? ? ? ♥ ? ? ? ♣| {z }| {z }| {z }| {z }

𝐸 3♣ (𝑥 1 +𝑥 2 )

𝑥𝑛−1

𝑥4

(2) For the commitments to 𝑥 3 and 𝑥 4 , apply the helping-cardfree two-commitment addition described in Sect. 2.4. Here,we want to obtain the addition of 𝑥 3 +𝑥 4 with a different color
encoding to the addition of 𝑥 1 + 𝑥 2 obtained in the previous
step. Therefore, after the addition of 𝑥 3 and 𝑥 4 , we proceed
to the next step if 𝐸 3♥ (𝑥 3 + 𝑥 4 ) is obtained. If 𝐸 3♣ (𝑥 3 + 𝑥 4 )is obtained, then apply the color conversion subprotocol
described in Sect. 5.1 to it. In any case, the resulting sequence
after the operation is as follows:

𝐸 3♣ (𝑥 1 + 𝑥 2 )𝑥𝑛−2→ ? ? ··· ? ? ? ♣ ? ? ? ? ♥ .
|{z}| {z }|{z} |{z}? ? ? ? ? ? ? ? → ? ? ? ♣ ? ? ? ? .
|{z} |{z} |{z} |{z}| {z }|{z} |{z}𝑥2𝑥𝑛The protocol proceeds as follows.

(1) For the commitments to 𝑥 1 and 𝑥 2 , apply the helping-cardfree two-commitment addition described in Sect. 2.4. Assume
without loss of generality that we obtain 𝐸 3♣ (𝑥 1 + 𝑥 2 ) and afree black card ♣ :𝑥1𝑥2(𝑛 − 4) cardsz}|{→ ··· → ? ? ? ··· ? ♣ ♣ ♣ ··· ♣ ♥ ♥ .
|
{z
}
♣ (
𝐸𝑛−3

Í𝑛−4

𝑘=1 𝑥𝑘 )Í𝑛−4♣ ( Í𝑛−4 𝑥 ) and 𝐸 ♥ (𝑥♣(5) Convert 𝐸𝑛−3
3 𝑛−1 +𝑥𝑛 ) to 𝐸𝑛−1 ( 𝑘=1 𝑥𝑘 )
𝑘=1 𝑘
♥ (𝑥
and 𝐸𝑛−1
𝑛−1 + 𝑥𝑛 ), respectively, in a similar way to theAPKC ’23, July 10, 2023, Melbourne, VIC, Australia

Hayato Shikata, Daiki Miyahara, and Takaaki Mizuki

Table 4: Value of

method described in Sect. 2.1:

Í𝑛𝑥 and the sequence of cards
𝑘=1 𝑘(𝑛 − 4) cards

z
}|
{
♣
♣
♣
♣
♥
♥
? ? ? ··· ?
? ? ?
···
|
{z
}
| {z }♣ (𝐸𝑛−3

𝐸 3♥ (𝑥𝑛−1 + 𝑥𝑛 )Í𝑛−4

𝑘=1 𝑥𝑘 )→ ? ? ? ··· ? ? ? ? ··· ? .
|
{z
}|
{z
}
♣ (
𝐸𝑛−1

Í𝑛−4

𝑘=1 𝑥𝑘 )♥ (𝑥𝐸𝑛−1𝑛−1 +𝑥𝑛 )♣ ( Í𝑛−4 𝑥 )(6) Apply the integer addition presented in Sect. 2.3 to 𝐸𝑛−1
𝑘=1 𝑘
♥ (𝑥
and 𝐸𝑛−1
𝑛−1 + 𝑥𝑛 ) derived in the previous step:? ? ? ··· ? ? ? ? ··· ?
|
{z
} |
{z
}
♣ (
𝐸𝑛−1

Í𝑛−4

𝑘=1 𝑥𝑘 )Í𝑛Sequence of cards0♥ ♣ ♣ ··· ♣ ♣1♣ ♥ ♣ ··· ♣ ♣2..
.

♣ ♣ ♥ ··· ♣ ♣
..
.

𝑛−1

♣ ♣ ♣ ··· ♣ ♥𝑛♥ ♣ ♣ ··· ♣ ♣Value of

𝑥
𝑘=1 𝑘

♥ (𝑥
𝐸𝑛−1
𝑛−1 +𝑥𝑛 )(𝑛 − 2) cardsz}|{→ ? ? ? ··· ? ♣ ♥ ♥ ♥ ··· ♥ .
|
{z
}
♥ (
𝐸𝑛−1

Í𝑛−4

𝑘=1 𝑥𝑘 + 𝑥𝑛−1 + 𝑥𝑛 )♥ ( Í𝑛−4 𝑥 + 𝑥(7) Convert 𝐸 3♣ (𝑥𝑛−3 + 𝑥𝑛−2 ) and 𝐸𝑛−1
𝑛−1 + 𝑥𝑛 ) to𝑘=1 𝑘
Í𝐸𝑛♣ (𝑥𝑛−3 + 𝑥𝑛−2 ) and 𝐸𝑛♥ ( 𝑛−4
𝑥
+
𝑥
+
𝑥
),
respectively,
𝑛−1
𝑛
𝑘
𝑘=1

in a similar way to the method described in Sect. 2.1:
(𝑛 − 3) cardsz}|{? ? ? ♥ ♥ ♥ ··· ♥ ? ? ? ··· ? ♣ ♥| {z }|{z}

𝐸 3♣ (𝑥𝑛−3 + 𝑥𝑛−2 )

♥ (
𝐸𝑛−1

Í𝑛−4

𝑘=1 𝑥𝑘 + 𝑥𝑛−1 + 𝑥𝑛 )→ ? ? ? ··· ?
|{z}? ? ? ··· ?
|{z}𝐸𝑛♣ (𝑥𝑛−3 +𝑥𝑛−2 ) 𝐸𝑛♥ (

♥.

Í𝑛−4

𝑘=1 𝑥𝑘 +𝑥𝑛−1 +𝑥𝑛 )(8) Apply the integer addition described in Sect. 2.3 to 𝐸𝑛♣ (𝑥𝑛−3 +Í
𝑥𝑛−2 ) and 𝐸𝑛♥ ( 𝑛−4𝑥 + 𝑥𝑛−1 + 𝑥𝑛 ):𝑘=1 𝑘? ? ? ··· ?
|
{z
}

♥

? ? ? ··· ?
|{z}𝐸𝑛♣ (𝑥𝑛−3 +𝑥𝑛−2 ) 𝐸𝑛♥ (ACKNOWLEDGMENTS
We thank the anonymous referees, whose comments have helped
us to improve the presentation of the paper. The method in Sect. 5.1
was established with the help of Kodai Toyoda. This work was
supported in part by JSPS KAKENHI Grant Numbers JP21K11881
and JP23H00479.

Í𝑛−4

𝑘=1 𝑥𝑘 +𝑥𝑛−1 +𝑥𝑛 )𝑛 cardsz}|{→ ? ? ? ··· ? ♣ ♥ ♥ ♥ ··· ♥ .
|
{z
}
𝐸𝑛♥ (

Í𝑛

𝑘=1 𝑥𝑘mod 𝑛)

Í𝑛Here, as shown in Table 4, if 𝑘=1 𝑥𝑘 = 𝑛, the resulting seÍ
quence becomes 𝐸𝑛♥ (0). Therefore, we have 𝐸𝑛♥ ( 𝑛𝑘=1 𝑥𝑘 mod𝑛).
ÍThis is how 𝐸𝑛♥ ( 𝑛𝑘=1 𝑥𝑘 mod 𝑛) is obtained for 𝑛 ≥ 5, and as
explained in Sect. 3, it is possible to compute any {0}-partiallydoubly symmetric Boolean function from this sequence.

7

our results show that no helping card is required for 𝑛 = 3, 4, andonly one helping card suffices for 𝑛 ≥ 5.
As for the case of 𝑛 = 2, given commitments to 𝑥 1, 𝑥 2 , the helpingcard-free two-commitment addition described in Sect. 2.4 produces
𝐸 3♣ (𝑥 1 + 𝑥 2 ) or 𝐸 3♥ (𝑥 1 + 𝑥 2 ), from which we can securely computeany two-input symmetric Boolean function having an arbitrary
range. Therefore, for the case of 𝑛 = 2, without the restriction,
there is a helping-card-free protocol for any symmetric Booleanfunction; see Table 1 again.
For future work, we will address whether there exists a protocol
with less than two helping cards for any 𝑛-input (unrestricted)
symmetric Boolean function having an arbitrary range such that𝑛 ≥ 3.

CONCLUSION

In this paper, we aimed to construct new card-based protocols requiring fewer helping cards within the class of symmetric Booleanfunctions. To this end, we considered the class of {0}-partially doubly symmetric Boolean functions as a subclass, and designed generic
protocols for them using less than two helping cards. Specifically,

REFERENCES[1] Yoshiki Abe, Takeshi Nakai, Yoshihisa Kuroki, Shinnosuke Suzuki, Yuta Koga,
Yohei Watanabe, Mitsugu Iwamoto, and Kazuo Ohta. 2022. Efficient Card-Based
Majority Voting Protocols. New Gener. Comput. 40 (2022), 173–198. https://doi.org/10.1007/s00354-022-00161-7[2] Claude Crépeau and Joe Kilian. 1994. Discreet Solitary Games. In Advances in
Cryptology—CRYPTO’ 93 (LNCS, Vol. 773), Douglas R. Stinson (Ed.). Springer,
Berlin, Heidelberg, 319–330. https://doi.org/10.1007/3-540-48329-2_27[3] Takuro Fukasawa and Yoshifumi Manabe. 2022. Card-Based Zero-Knowledge
Proof for the Nearest Neighbor Property: Zero-Knowledge Proof of ABC End
View. In Security, Privacy, and Applied Cryptography Engineering (Lecture Notes
in Computer Science, Vol. 13783), Lejla Batina, Stjepan Picek, and Mainack Mondal(Eds.). Springer Nature Switzerland, Cham, 147–161.
[4] Rikuo Haga, Yuichi Hayashi, Daiki Miyahara, and Takaaki Mizuki. 2022. CardMinimal Protocols for Three-Input Functions with Standard Playing Cards. In
Progress in Cryptology—AFRICACRYPT 2022 (LNCS). Springer, Cham. to appear.
[5] Rikuo Haga, Kodai Toyoda, Yuto Shinoda, Daiki Miyahara, Kazumasa Shinagawa,Yuichi Hayashi, and Takaaki Mizuki. 2022. Card-Based Secure Sorting Protocol.
In Advances in Information and Computer Security (LNCS, Vol. 13504), ChenMou Cheng and Mitsuaki Akiyama (Eds.). Springer, Cham, 224–240. https://doi.org/10.1007/978-3-031-15255-9_12[6] James Heather, Steve Schneider, and Vanessa Teague. 2014. Cryptographic protocols with everyday objects. Formal Aspects of Computing 26, 1 (2014), 37–62.
https://doi.org/10.1007/s00165-013-0274-7

Few-helping-card Protocols for Some Wider Class of Symmetric Boolean Functions with Arbitrary Ranges[7] Raimu Isuzugawa, Kodai Toyoda, Yu Sasaki, Daiki Miyahara, and Takaaki
Mizuki. 2021. A Card-Minimal Three-Input AND Protocol Using Two Shuffles. In Computing and Combinatorics (LNCS, Vol. 13025), Chi-Yeh Chen, WingKai Hon, Ling-Ju Hung, and Chia-Wei Lee (Eds.). Springer, Cham, 668–679.
https://doi.org/10.1007/978-3-030-89543-3_55[8] Julia Kastner, Alexander Koch, Stefan Walzer, Daiki Miyahara, Yu-ichi Hayashi,
Takaaki Mizuki, and Hideaki Sone. 2017. The Minimum Number of Cards inPractical Card-Based Protocols. In Advances in Cryptology—ASIACRYPT 2017
(LNCS, Vol. 10626), Tsuyoshi Takagi and Thomas Peyrin (Eds.). Springer, Cham,
126–155. https://doi.org/10.1007/978-3-319-70700-6_5[9] Alexander Koch. 2019. Cryptographic Protocols from Physical Assumptions. Ph. D.
Dissertation. Karlsruhe Institute of Technology. https://doi.org/10.5445/IR/
1000097756[10] Alexander Koch. 2021. The Landscape of Security from Physical Assumptions.
In IEEE Information Theory Workshop. IEEE, NY, 1–6. https://doi.org/10.1109/
ITW48936.2021.9611501[11] Alexander Koch, Michael Schrempp, and Michael Kirsten. 2019. Card-Based
Cryptography Meets Formal Verification. In Advances in Cryptology–ASIACRYPT
2019 (LNCS, Vol. 11921), Steven D. Galbraith and Shiho Moriai (Eds.). Springer,
Cham, 488–517. https://doi.org/10.1007/978-3-030-34578-5_18[12] Alexander Koch, Stefan Walzer, and Kevin Härtel. 2015. Card-Based Cryptographic Protocols Using a Minimal Number of Cards. In Advances in Cryptology—
ASIACRYPT 2015 (LNCS, Vol. 9452), Tetsu Iwata and Jung Hee Cheon (Eds.).
Springer, Berlin, Heidelberg, 783–807. https://doi.org/10.1007/978-3-662-487976_32[13] Yoshifumi Manabe and Hibiki Ono. 2022. Card-Based Cryptographic Protocols
with Malicious Players Using Private Operations. New Gener. Comput. 40 (2022),
67–93. https://doi.org/10.1007/s00354-021-00148-w[14] Daiki Miyahara, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. 2020. Practical card-based implementations of Yao’s millionaire protocol. Theor. Comput.
Sci. 803 (2020), 207–221. https://doi.org/10.1016/j.tcs.2019.11.005[15] Daiki Miyahara and Takaaki Mizuki. 2022. Secure Computations through Checking Suits of Playing Cards. In Frontiers in Algorithmics (Lecture Notes in Computer
Science, Vol. 13461). Springer, Cham, 110–128.
[16] Kengo Miyamoto and Kazumasa Shinagawa. 2022. Graph Automorphism Shufflesfrom Pile-Scramble Shuffles. New Gener. Comput. 40 (2022), 199–223. https://doi.org/10.1007/s00354-022-00164-4[17] Takaaki Mizuki. 2016. Card-based Protocols for Securely Computing the
Conjunction of Multiple Variables. Theor. Comput. Sci. 622, C (2016), 34–44.
https://doi.org/10.1016/j.tcs.2016.01.039[18] Takaaki Mizuki. 2021. Preface: Special Issue on Card-Based Cryptography. New
Gener. Comput. 39 (2021), 1–2. https://doi.org/10.1007/s00354-021-00127-1[19] Takaaki Mizuki. 2022. Preface: Special Issue on Card-Based Cryptography 2. New
Gener. Comput. 40 (2022), 47–48. https://doi.org/10.1007/s00354-022-00170-6[20] Takaaki Mizuki, Michihito Kumamoto, and Hideaki Sone. 2012. The Five-Card
Trick Can Be Done with Four Cards. In Advances in Cryptology—ASIACRYPT
2012 (LNCS, Vol. 7658), Xiaoyun Wang and Kazue Sako (Eds.). Springer, Berlin,
Heidelberg, 598–606. https://doi.org/10.1007/978-3-642-34961-4_36[21] Takaaki Mizuki and Hiroki Shizuya. 2014. A formalization of card-based cryptographic protocols via abstract machine. Int. J. Inf. Secur. 13, 1 (2014), 15–23.
https://doi.org/10.1007/s10207-013-0219-4[22] Takaaki Mizuki and Hiroki Shizuya. 2017. Computational Model of Card-Based
Cryptographic Protocols and Its Applications. IEICE Trans. Fundam. E100.A, 1(2017), 3–11. https://doi.org/10.1587/transfun.E100.A.3[23] Takaaki Mizuki and Hideaki Sone. 2009. Six-Card Secure AND and Four-Card
Secure XOR. In Frontiers in Algorithmics (LNCS, Vol. 5598), Xiaotie Deng, John E.
Hopcroft, and Jinyun Xue (Eds.). Springer, Berlin, Heidelberg, 358–369. https://doi.org/10.1007/978-3-642-02270-8_36[24] Takeshi Nakai, Yuto Misawa, Yuuki Tokushige, Mitsugu Iwamoto, and Kazuo
Ohta. 2022. Secure Computation for Threshold Functions with Physical Cards:
Power of Private Permutations. New Gener. Comput. 40 (2022), 95–113. https://doi.org/10.1007/s00354-022-00153-7[25] Takuya Nishida, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. 2015. CardBased Protocols for Any Boolean Function. In Theory and Applications of Modelsof Computation (LNCS, Vol. 9076), Rahul Jain, Sanjay Jain, and Frank Stephan(Eds.). Springer, Cham, 110–121. https://doi.org/10.1007/978-3-319-17142-5_11[26] Akihiro Nishimura, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. 2018.
Pile-shifting scramble for card-based protocols. IEICE Trans. Fundam. 101, 9(2018), 1494–1502. https://doi.org/10.1587/transfun.E101.A.1494[27] Léo Robert, Daiki Miyahara, Pascal Lafourcade, Luc Libralesso, and Takaaki
Mizuki. 2022. Physical zero-knowledge proof and NP-completeness proof of
Suguru puzzle. Inf. Comput. 285 (2022), 1–14. https://doi.org/10.1016/j.ic.2021.
104858[28] Léo Robert, Daiki Miyahara, Pascal Lafourcade, and Takaaki Mizuki. 2022. CardBased ZKP for Connectivity: Applications to Nurikabe, Hitori, and Heyawake.
New Gener. Comput. 40 (2022), 149–171. https://doi.org/10.1007/s00354-02200155-5

APKC ’23, July 10, 2023, Melbourne, VIC, Australia[29] Léo Robert, Daiki Miyahara, Pascal Lafourcade, and Takaaki Mizuki. 2022. Hide a
Liar: Card-Based ZKP Protocol for Usowan. In Theory and Applications of Modelsof Computation (LNCS). Springer, Cham. to appear.
[30] Suthee Ruangwises and Toshiya Itoh. 2020. Securely Computing the n-Variable
Equality Function with 2n Cards. In Theory and Applications of Models of Computation (LNCS, Vol. 12337), Jianer Chen, Qilong Feng, and Jinhui Xu (Eds.). Springer,
Cham, 25–36. https://doi.org/10.1007/978-3-030-59267-7_3[31] Suthee Ruangwises and Toshiya Itoh. 2021. Physical ZKP for Connected Spanning
Subgraph: Applications to Bridges Puzzle and Other Problems. In Unconventional
Computation and Natural Computation, Irina Kostitsyna and Pekka Orponen(Eds.). Springer, Cham, 149–163.
[32] Suthee Ruangwises and Toshiya Itoh. 2021. Securely computing the n-variableequality function with 2n cards. Theor. Comput. Sci. 887 (2021), 99–110. https://doi.org/10.1016/j.tcs.2021.07.007[33] Suthee Ruangwises and Toshiya Itoh. 2022. Physical ZKP for Makaro Using aStandard Deck of Cards. In Theory and Applications of Models of Computation(LNCS). Springer, Cham. to appear.
[34] Hayato Shikata, Kodai Toyoda, Daiki Miyahara, and Takaaki Mizuki. 2022. Cardminimal Protocols for Symmetric Boolean Functions of More Than Seven Inputs.
In Theoretical Aspects of Computing – ICTAC 2022 (LNCS, Vol. 13572), Helmut
Seidl, Zhiming Liu, and Corina S. Pasareanu (Eds.). Springer, Cham, 388–406.
https://doi.org/10.1007/978-3-031-17715-6_25[35] Kazumasa Shinagawa. 2020. On the Construction of Easy to Perform Card-BasedProtocols. Ph. D. Dissertation. Tokyo Institute of Technology.
[36] Kazumasa Shinagawa and Takaaki Mizuki. 2019. The Six-Card Trick: Secure
Computation of Three-Input Equality. In Information Security and Cryptology(LNCS, Vol. 11396), Kwangsu Lee (Ed.). Springer, Cham, 123–131. https://doi.org/
10.1007/978-3-030-12146-4_8[37] Kazumasa Shinagawa, Takaaki Mizuki, Jacob Schuldt, Koji Nuida, Naoki
Kanayama, Takashi Nishide, Goichiro Hanaoka, and Eiji Okamoto. 2017. CardBased Protocols Using Regular Polygon Cards. IEICE Trans. Fundam. E100.A, 9(2017), 1900–1909. https://doi.org/10.1587/transfun.E100.A.1900[38] Kazumasa Shinagawa and Koji Nuida. 2022. Single-shuffle Full-open Card-based
Protocols Imply Private Simultaneous Messages Protocols. Cryptology ePrint
Archive, Paper 2022/1306. https://eprint.iacr.org/2022/1306 https://eprint.iacr.
org/2022/1306.
[39] Yuji Suga. 2022. A classification proof for commutative three-element semigroups
with local AND structure and its application to card-based protocols. In 2022 IEEE
International Conference on Consumer Electronics - Taiwan. IEEE, NY, 171–172.
https://doi.org/10.1109/ICCE-Taiwan55306.2022.9869063[40] Ken Takashima, Yuta Abe, Tatsuya Sasaki, Daiki Miyahara, Kazumasa Shinagawa,Takaaki Mizuki, and Hideaki Sone. 2020. Card-based protocols for secure ranking
computations. Theor. Comput. Sci. 845 (2020), 122–135. https://doi.org/10.1016/j.
tcs.2020.09.008[41] Kodai Toyoda, Daiki Miyahara, and Takaaki Mizuki. 2021. Another Use of theFive-Card Trick: Card-Minimal Secure Three-Input Majority Function Evaluation.
In Progress in Cryptology—INDOCRYPT 2021 (LNCS, Vol. 13143), Avishek Adhikari,
Ralf Küsters, and Bart Preneel (Eds.). Springer, Cham, 536–555. https://doi.org/
10.1007/978-3-030-92518-5_24