Upper Bounds on the Number of Shuﬄes for
Two-Helping-Card Multi-Input AND Protocols★
Takuto Yoshida1 , Kodai Tanaka2 , Keisuke Nakabayashi2 , Eikoh Chida1 , andTakaaki Mizuki2
1 National Institute of Technology, Ichinoseki College, Ichinoseki, Iwate, Japan

chida+lncs[atmark]g.ichinoseki.ac.jp
2 Tohoku University, Sendai, Japanmizuki+lncs[atmark]tohoku.ac.jp

Abstract. Card-based cryptography uses a physical deck of cards to achieve
secure computations. To evaluate the performance of card-based protocols, thenumbers of helping cards and shuﬄes required to execute are often used as
evaluation metrics. In this paper, we focus on 𝑛-input AND protocols that use at
most two helping cards, and investigate how many shuﬄes suﬃce to construct
such a two-helping-card AND protocol. Since the Mizuki–Sone two-input AND
protocol uses two helping cards and it can be repeatedly applied 𝑛 − 1 times
to perform a secure 𝑛-input AND computation, an obvious upper bound on thenumber of required shuﬄes is 𝑛 − 1. In this paper, to obtain better bounds (than𝑛 − 1), we consider making use of the “batching” technique, which was developed
by Shinagawa and Nuida in 2020 to reduce the number of shuﬄes. Speciﬁcally,
we ﬁrst formulate the class of two-helping-card 𝑛-input AND protocols obtainedby applying the batching technique to the Mizuki–Sone AND protocol, and thenshow 𝑛-input AND protocols requiring the minimum number of shuﬄes (among
the class) for the case of 2 ≤ 𝑛 ≤ 500.
Keywords: Card-based cryptography · Secure computation · Real-life hands-on
cryptography · AND protocols

1 Introduction
Secure computations [36] enable players holding individual private inputs to evaluate
a predetermined function without revealing the input values more than necessary. The
method of secure computation using a physical deck of cards is called card-based
cryptography [7, 19]. Typically, two types of cards are used, where the reverse side isindistinguishable as ? and the front side is either ♣ or ♡ . These cards are arrangedin the following way to represent Boolean values:♣ ♡ = 0, ♡ ♣ = 1.
★ This paper appears in Proceedings of CANS 2023. This version of the contribution has been

accepted for publication, after peer review but is not the Version of Record and does not
reﬂect post-acceptance improvements, or any corrections. The Version of Record is available
online at: http://dx.doi.org/10.1007/978-981-99-7563-1_10. 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

T. Yoshida et al.

When two cards placed face down according to this encoding rule represent a bit
𝑥 ∈ {0, 1}, these two cards are called a commitment to 𝑥 and are represented as follows:
? ? .
|{z}
𝑥

A two-input AND protocol takes as input two commitments to bits 𝑥, 𝑦 ∈ {0, 1}
along with some helping cards like ♣ ♡ , and performs a secure computation of the
AND value 𝑥 ∧ 𝑦 via a series of actions such as shuﬄing, rearranging, and turning overcards. When the output is obtained as a commitment to 𝑥 ∧ 𝑦, such a protocol is called
a committed-format protocol:? ? ? ? ♣ ♡ ··· → ··· → ? ? .
|{z} |{z}
|{z}
𝑥

𝑦

𝑥∧𝑦

This paper deals with committed-format AND protocols, especially multi-input AND
protocols, as seen later.
1.1 The Mizuki–Sone AND Protocol
The most practical committed-format two-input AND protocol currently known would
be the protocol proposed by Mizuki and Sone in 2009 [20]. Hereinafter, we refer to thisas the MS-AND protocol, and the procedure is described below.
1. Place two input commitments to 𝑥, 𝑦 ∈ {0, 1} along with two helping cards, turning
the middle two cards face down, as follows:? ? ♣ ♡ ? ? → ? ? ? ? ? ? .
|{z}
|{z}
|{z} |{z} |{z}
𝑥

𝑦

𝑥

0

𝑦

2. Rearrange the sequence as follows:? ? ? ? ? ?
QQQs? ? ? ? ? ? .
3. A random bisection cut (hereafter sometimes called an RBC for short), denoted by[· · · | · · · ], is applied to the sequence of six cards, meaning that we split the cardsequence in half and randomly swap the left and right sides (until anyone loses trackof the move):hi? ? ? ? ? ? → ? ? ? ? ? ? .
It is known that a random bisection cut can be securely implemented using familiar
tools such as envelopes [35].

Two-Helping-Card Multi-Input AND Protocols

3

4. Rearrange the sequence as follows:? ? ? ? ? ?

@

@
R@
R
@
+

? ? ? ? ? ? .
5. The two cards are turned over from the left. Depending on the order of the two
revealed cards, we obtain a commitment to 𝑥 ∧ 𝑦 as follows:♣ ♡ ? ? ? ? or ♡ ♣ ? ? ? ? .
|{z}
|{z}
𝑥∧𝑦

𝑥∧𝑦

The above is the MS-AND protocol, which, given commitments to 𝑥 and 𝑦, uses two
helping cards and one random bisection cut to output a commitment to 𝑥 ∧ 𝑦.
After the protocol terminates, the two cards that were turned over in Step 5 can beused as helping cards in another protocol run; we call such face-up cards free cards.
We will also call the two face-down cards that are not a commitment to 𝑥 ∧ 𝑦 agarbage commitmentiii. A garbage commitment can be transformed into two free cards
by applying a (normal) shuﬄe to the two cards (composing the garbage commitment)
and turning them over.

1.2 Committed-Format Multi-Input AND Protocol
As mentioned above, the subject of this paper is to construct committed-format multiinput AND protocols. That is, given 𝑛 input commitments? ? ? ? ··· ? ? ,|{z} |{z}
|{z}
𝑥1

𝑥2

𝑥𝑛

we want to produce a commitment to 𝑥1 ∧ 𝑥 2 ∧ · · · ∧ 𝑥 𝑛 .
Applying the MS-AND protocol described in Sect. 1.1 to commitments to 𝑥1 and 𝑥2
yields a commitment to 𝑥 1 ∧ 𝑥2 together with two free cards. Thus, we can continue toapply the MS-AND protocol to commitments to 𝑥 1 ∧ 𝑥2 and 𝑥3 . By repeating this a totalof 𝑛 − 1 times, a committed-format 𝑛-input AND protocol can be constructed [15]:? ? ? ? ··· ? ? ♣ ♡ → ··· →|{z} |{z}
|{z}
𝑥1

𝑥2

𝑥𝑛

? ?
|{z}

.

𝑥1 ∧𝑥2 ∧···∧𝑥𝑛

In this case, the number of required helping cards is two, and the number of required
shuﬄes (namely, the number of random bisection cuts) is 𝑛 − 1.
iii These two cards are actually a commitment to 𝑥 ∧ 𝑦.

4

T. Yoshida et al.

1.3 Contribution of This Paper
As described in Sect. 1.2, an obvious upper bound on the number of required shuﬄes
for a committed-format 𝑛-input AND protocol is 𝑛 − 1 under the condition that two
helping cards are available. On the other hand, there is a technique called the “batching”
proposed in 2020 by Shinagawa and Nuida [31] that can reduce the number of shuﬄes.
Therefore, in this paper, we apply the batching technique to the MS-AND protocol sothat we can construct two-helping-card 𝑛-input AND protocols having a smaller numberof shuﬄes. Such an application naturally formulates the class of committed-format
two-helping-card 𝑛-input AND protocols. Within the class, we present a simple generic
protocol having a smaller number of shuﬄes. Furthermore, we reduce the problem of
constructing a protocol to the “MSbatching move-sequence” problem (which is a kind of
a computational problem), and by analyzing the latter problem, we show the minimum
number of shuﬄes among the class of protocols in the range of 2 ≤ 𝑛 ≤ 500. It turns outthat the generic proposed protocol is optimal in terms of the number of shuﬄes for manycases of 𝑛. For every 𝑛, 2 ≤ 𝑛 ≤ 500, such that the proposed protocol is not optimal, we
ﬁnd optimal protocols, as well.
1.4 Related Works
The history of committed-format two-input AND protocols dates back to 1993 [2], andsince then, a couple protocols have been invented [22, 33], followed by the MS-AND
protocol in 2009 [20] (which uses six cards and one random bisection cut as seen
above). Subsequently, four- and ﬁve-card protocols have been developed using complex
shuﬄes [8, 9, 25].
As for committed-format multi-input AND protocols, those using only one or two
shuﬄes have recently been proposed [11] (although many helping cards are required).
In addition, several specialized protocols have been known [6, 15].
The research area of card-based cryptography has been growing rapidly in recent
years [16, 17]. Examples of active topics are: physical zero-knowledge proof protocols [4, 10, 23, 24], private-model secure computations [1, 12, 21], symmetric function
evaluation [26–28], information leakage due to operative or physical errors [18, 29],
graph automorphism shuﬄes [14, 30], multi-valued protocols with a direction encoding [34], the half-open action [13], card-minimal protocols [3, 8], and applications to
private simultaneous messages protocols [32].
1.5 Organization of This Paper
The remainder of this paper is organized as follows. In Sect. 2, we introduce the batching
technique along with the “pile-scramble shuﬄe” required for it. In Sect. 3, we show
how the batching technique can be applied to multiple MS-AND protocols. In Sect. 4,
we formulate the class of protocols obtained by applying the batching technique, andreduce the problem of ﬁnding protocols having fewer shuﬄes to the “MSbatchingmove-sequence” problem and propose a simple generic protocol in Sect. 5. In Sect. 6, theMSbatching move-sequence problem is analyzed by a dynamic programming algorithm,
and we show optimal 𝑛-input AND protocols for 2 ≤ 𝑛 ≤ 500 in the sense that the numberTwo-Helping-Card Multi-Input AND Protocols

5of shuﬄes is minimum among all the protocols in the class. Finally, the conclusion is
given in Sect. 7.

2 Preliminaries
In this section, we ﬁrst introduce the pile-scramble shuﬄe [5] and then explain thebatching technique [31].
2.1 Pile-Scramble Shuﬄe
A pile-scramble shuﬄe [5] is a shuﬄing operation that divides a sequence of cards into
multiple piles of the same size and then rearranges the order of those piles uniformly at
random (while the order of cards inside each pile is kept unchanged).
As an example, applying a pile-scramble shuﬄe, denoted by [ · | · | · · · | · ], to asequence of nine cards consisting of three piles yields one of the following six sequenceswith a probability of exactly 1/6:
h 1 2 3
? ? ?
1 2 3




?
? ?





1
2 3




?
?
?





4 5 6




 ? ? ?
→
4 5 6




?
? ?





7 8 9




? ? ?




7 8 9



 ? ? ?


4

5

7

6

? ? ?
4

5

6

8

9

i

? ? ?
7

8

9

? ? ? ? ? ?
7

8

9

4

5

6

? ? ? ? ? ?
1

2

3

7

8

9

? ? ? ? ? ?
7

8

9

1

2

3

? ? ? ? ? ?
1

2

3

4

5

6

? ? ? ? ? ?
4

5

6

1

2

3

? ? ? ? ? ? .

A pile-scramble shuﬄe can be easily implemented by placing each pile in an envelope
and randomly stirring the envelopes.
A random bisection cut that appears in the MS-AND protocol can be said to be apile-scramble shuﬄe for two piles (each consisting of three cards).
2.2 Batching Technique
The batching technique [31] combines multiple pile-scramble shuﬄes that can be executed in parallel into a single pile-scramble shuﬄe, thereby reducing the number of
shuﬄes. Simply put, after adding “identiﬁers” with some helping cards to the piles ofeach pile-scramble shuﬄe, we perform a single pile-scramble shuﬄe together, and thenopen the identiﬁer to return each pile to the position of its original pile-scramble shuﬄe.

6T. Yoshida et al.

As an example, suppose that we want to apply two random bisection cuts (RBCs) inparallel, which appear in the MS-AND protocol, and that we want to use the batching
technique. In other words, we want to perform two RBCsi hih
? ? ? ? ? ? , ? ? ? ? ? ?
simultaneously using a single shuﬄe by the batching technique.
1. To identify two RBCs, we use ♣ and ♡ . That is, at the head of each pile, a helping
card for identiﬁcation is placed as follows:♣ ? ? ?

♣ ? ? ?

♡ ? ? ?

♡ ? ? ? .

In the sequel, we call such helping cards identiﬁer cards.
2. Turn over the identiﬁer cards and apply a pile-scramble shuﬄe to the four piles:hi? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
→ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? .
3. Turn the identiﬁer cards face up. For instance, suppose that the following sequenceof cards is obtained:♣ ? ? ?

♡ ? ? ?

♡ ? ? ?

♣ ? ? ? .

4. Sort the piles so that the pile with ♣ at the head is on the left and the pile with ♡at the head is on the right, as when the identiﬁer cards were inserted in Step 1. In
the example above, the fourth pile is moved in front of the second pile:♣ ? ? ?

♡ ? ? ?

♡ ? ? ?

♣ ? ? ?

→ ♣ ? ? ?

♣ ? ? ?

♡ ? ? ?

♡ ? ? ? .

Note that sorting the piles here is done publicly as seen just above (and hence, weneed no additional shuﬄe).
5. Remove the face-up identiﬁer cards; then, we have performed two RBCs by one
pile-scramble shuﬄe.
In this example, two sets of ♣ ♡ were used to identify the two RBCs. If we wantto identify four RBCs, two sets of♣ ♣♣ ♡ ♡ ♣

♡ ♡suﬃce. That is, we can distinguish the piles by two binary digits according to the onecard-per-bit encoding: ♣ = 0, ♡ = 1. In general, when we want to apply the batching
technique to 𝑘 RBCs, we need 2𝑘 ⌈log2 𝑘⌉ identiﬁer cards (i.e., 𝑘 ⌈log2 𝑘⌉ free cards foreach of ♣ and ♡).
The batching technique can be applied not only to RBCs, but more generally tomultiple pile-scramble shuﬄes. However, this paper only utilizes it for RBCs (of six
cards each).

Two-Helping-Card Multi-Input AND Protocols

7

3 Application of Batching to MS-AND Protocol
As seen in Sect. 1.2, executing repeatedly the MS-AND protocol provides a two-helpingcard 𝑛-input AND protocol using 𝑛 − 1 shuﬄes, namely 𝑛 − 1 RBCs. In this section, we
utilize the batching technique to reduce the number of shuﬄes.
In Sect. 3.1, we mention the idea behind our approach. In Sect. 3.2, we present how
to batch MS-AND protocols. In Sect. 3.3, we show an example of a protocol based on
our approach.
3.1 Idea
As described in Sect. 2.2, the batching technique can be used to convert multiple RBCs
into a single pile-scramble shuﬄe. This can be applied to the execution of multiple MSAND protocols to reduce the number of shuﬄes. Remember that, in order to performthe batching technique, some free cards as identiﬁer cards must be provided to identify
each pile pair. Remember furthermore that in the problem setup, only two helping cards
are available:? ? ? ? ··· ? ? ♣ ♡ .
|{z} |{z}
|{z}
𝑥1

𝑥2

𝑥𝑛

Therefore, the batching technique cannot be applied immediately (because of shortageof free cards as identiﬁer cards).
Let us recall the procedure of the MS-AND protocol described in Sect. 1.1; then, agarbage commitment arises in Step 5. That is, one execution of the MS-AND protocol
yields one garbage commitment. Several garbage commitments can be turned into freecards by shuﬄing all the cards (of the garbage commitments) and revealing them. This
leads to increasing the number of free cards to be used as identiﬁer cards even if there
are only two helping cards at the beginning.
More speciﬁcally, for the ﬁrst 𝑚 input commitments, if the MS-AND protocol isrepeated 𝑚 − 1 times, we obtain 2𝑚 − 2 free cards:? ? ··· ? ? ♣ ♡
|{z}
|{z}
𝑥1

𝑥𝑚

→

♣ ♡ ♣ ♡ ··· ♣ ♡|{z}
𝑥1 ∧𝑥2 ∧···∧𝑥𝑚2𝑚−2 cards
? ?
|{z}

Thus, some of the 2𝑚 free cards can be used as identiﬁer cards for the batching technique.
In this way, we ﬁrst apply the MS-AND protocol for the ﬁrst several input commitments
to produce free cards enough for the batching technique to execute.
3.2 MSbatching: How to Batch MS-AND Protocols
This subsection describes in detail how the batching technique is applied to the executionof multiple MS-AND protocols.
Before we begin, let us deﬁne a couple of terms. As described in Sect. 3.1, free cards
can be created by collecting garbage commitments, shuﬄing all the cards (constituting
the garbage commitments), and then turning them over. This procedure is called the8

T. Yoshida et al.

garbage collection. For convenience, we will refer to a pair of free cards (of diﬀerent
colors) ♣ ♡ placed face up as a free pair.
First, as an example, assume that there are four commitments? ? ? ?
|{z} |{z}𝑦1𝑦2? ? ? ?
|{z} |{z}𝑦3𝑦4

and we want to produce commitments to 𝑦1 ∧ 𝑦2 and 𝑦3 ∧ 𝑦4 by executing the MS-AND
protocol twice. Recalling the MS-AND protocol procedure, we need two helping cards,
i.e., one free pair ♣ ♡ , per run; therefore, we require two free pairs:? ? ♣ ♡ ? ?
? ? ♣ ♡ ? ? .
|{z}|{z} |{z}
|{z}
𝑦1

𝑦2

𝑦3

𝑦4

For each of these, an RBC is applied (after reordering). Using the batching technique,this can be achieved with a single shuﬄe. In this case, however, two more free pairs
♣ ♡

♣ ♡

are required (for identiﬁer cards). After applying the batching technique and turningover the four identiﬁer cards, we return to the two MS-AND protocols and terminate
each protocol. Then, the following commitments are obtained:♣ ♡ ♣ ♡♣ ♡ ? ? ? ?
|{z} |{z}𝑦1 ∧𝑦2 garbage♣ ♡ ? ? ? ? .
|{z} |{z}𝑦3 ∧𝑦4 garbage

In summary, given four commitments and four free pairs, one shuﬄe suﬃces to output
two commitments (to the AND values), four free pairs, and two garbage commitments.
Next, more generally, consider running 𝑘 MS-AND protocols in parallel (i.e., thenumber of input commitments is 2𝑘). As mentioned earlier, one MS-AND protocol
requires one free pair, and hence, 𝑘 free pairs are needed for this amount. In addition,
when applying the batching technique, free cards are also needed for serving identiﬁer
cards; as mentioned in Sect. 2.2, we require 2𝑘 ⌈log2 𝑘⌉ free cards, which are 𝑘 ⌈log2 𝑘⌉
free pairs. Thus, a total of 𝑘 + 𝑘 ⌈log2 𝑘⌉ free pairs are required:? ? ? ? ··· ? ? . ? ?
|{z} |{z}|{z} |{z}
𝑦1

𝑦2

𝑦2𝑘−1

𝑦2𝑘

♣ ♡ × (𝑘 + 𝑘 ⌈log2 𝑘⌉).
|{z}
free

Applying the batching technique to this sequence of cards, the 2𝑘 commitments become 𝑘commitments (to the AND values) after one shuﬄe, resulting in 𝑘 garbage commitments
and no change in the number of free pairs:? ? ··· ? ?
|{z}
|{z}
𝑦1 ∧𝑦2𝑦2𝑘−1 ∧𝑦2𝑘

♣ ♡ × (𝑘 + 𝑘 ⌈log2 𝑘⌉) ♣ ♡ × 𝑘.
|{z}
|{z}
free

garbage

This procedure will henceforth be referred to as 𝑘-MSbatching.
The number of free pairs required for 𝑘-MSbatching is given by 𝑘 + 𝑘 ⌈log2 𝑘⌉, where
the speciﬁc numbers are shown in Table 1. Note that 1-MSbatching is the MS-AND
protocol itself (i.e., one run of the protocol).

Two-Helping-Card Multi-Input AND Protocols

9Table 1: The number of free pairs required for 𝑘-MSbatching
𝑘

1

2

3

4

5

6

7

8

9

# of free pairs

1

4

9

12

20

24

28

32

45

3.3 Example of Two-Helping-Card AND Protocol by MSbatching
In this subsection, we illustrate a two-helping-card protocol by using MSbatching.
Suppose that the number of inputs is 48, i.e., 𝑛 = 48. Then, 48 commitments andone free pair are the input sequence:? ? ? ? ? ? ? ? ··· ? ? ♣ ♡ .
|{z} |{z} |{z} |{z} |{z} |{z}
𝑥1

𝑥2

𝑥3

𝑥4

𝑥48

free

Recall that the obvious upper bound on the number of shuﬄes is to repeat the MSAND protocol 47 times, which is 47 shuﬄes. The following protocol requires a smaller
number of shuﬄes to produce a commitment to the AND value of 48 inputs.
1. Perform 1-MSbatching 15 times for the commitments to 𝑥1 , . . . , 𝑥 16 to obtain acommitment to 𝑥 1 ∧ · · · ∧ 𝑥 16 (by 15 shuﬄes):? ? ? ? ? ? · · · ? ? ♣ ♡ ? ? ×15.
|{z} |{z} |{z} |{z} |{z} |{z}𝑥1 ∧···∧𝑥16

𝑥17

𝑥18

𝑥48

free

garbage

2. The garbage collection is performed to generate 15 free pairs (by one shuﬄe):? ? ? ? ? ? · · · ? ? ♣ ♡ ×16.
|{z} |{z} |{z} |{z} |{z}𝑥1 ∧···∧𝑥16

𝑥17

𝑥18

𝑥48

free

3. Perform 4-MSbatching for 𝑥 17 , . . . , 𝑥 24 and for 𝑥 25 , . . . , 𝑥 32 , followed by 4-MSbatching,
2-MSbatching, and 1-MSbatching, in this order, to obtain a commitment to 𝑥 17 ∧· · · ∧ 𝑥32 (by ﬁve shuﬄes):
? ?
|{z}

? ?
|{z}

𝑥1 ∧···∧𝑥16 𝑥17 ∧···∧𝑥32? ? · · · ? ? ♣ ♡ ×16 ? ? ×15.
|{z} |{z} |{z}
|{z}
𝑥33

𝑥48

free

garbage

4. Perform 1-MSbatching for 𝑥 1 ∧ · · · ∧ 𝑥 16 and 𝑥17 ∧ · · · ∧ 𝑥 32 to obtain a commitment
to 𝑥1 ∧ · · · ∧ 𝑥32 (by one shuﬄe):? ? ? ? · · · ? ? ♣ ♡ ×16 ? ? ×16.
|{z} |{z} |{z} |{z}|{z}𝑥1 ∧···∧𝑥32

𝑥33

𝑥48

free

garbage

5. The garbage collection is performed (by one shuﬄe):
? ?
|{z}

? ?
|{z}

𝑥1 ∧···∧𝑥16 𝑥17 ∧···∧𝑥32? ? · · · ? ? ♣ ♡ ×32.
|{z} |{z} |{z}
𝑥33

𝑥48

free

10

T. Yoshida et al.

6. Execute 8-MSbatching, 4-MSbatching, 2-MSbatching, and 1-MSbatching for 𝑥 33 , . . . , 𝑥 48
in this order to obtain a commitment to 𝑥33 ∧ · · · ∧ 𝑥48 (by four shuﬄes):
? ?
|{z}

? ?
|{z}

𝑥1 ∧···∧𝑥32 𝑥33 ∧···∧𝑥48♣ ♡ ×32 ? ? ×15.
|{z}
|{z}
free

garbage

7. Perform 1-MSbatching for 𝑥 1 ∧ · · · ∧ 𝑥 32 and 𝑥33 ∧ · · · ∧ 𝑥 48 to obtain a commitment
to 𝑥1 ∧ · · · ∧ 𝑥48 (by one shuﬄe):
? ?
|{z}

𝑥1 ∧···∧𝑥48♣ ♡ ×32 ? ? ×16.
|{z}
|{z}
free

garbage

As shown above, the total number of shuﬄes is 28, which is a signiﬁcant reduction
from the obvious upper bound of 47 shuﬄes.

4 Class of MSbatching Protocols and Corresponding Problem
As seen in Sect. 3, given 𝑛 input commitments and one free pair, we can produce acommitment to the AND value via a series of MSbatching (including 1-MSbatching)
and the garbage collection with fewer shuﬄes than the obvious upper bound. In thissection, we ﬁrst formulate the class of two-helping-card AND protocols, called the“MSbatching protocols,” naturally created by the combination of MSbatching and thegarbage collection. We then introduce the “MSbatching move-sequence” problem; asseen soon, ﬁnding a protocol in the class corresponds to solving the problem.
4.1 MSbatching Protocols
This subsection clariﬁes the class of protocols obtained by MSbatching.
First, let 𝑘 ≥ 1 and consider the conditions under which 𝑘-MSbatching can be
performed. As mentioned in Sect. 3.2, at least 𝑘 + 𝑘 ⌈log2 𝑘⌉ free pairs are required.
Also, to be able to run the MS-AND protocol 𝑘 times in parallel, there must be at least
2𝑘 input commitments.
Next, if we want to perform the garbage collection on 𝑔 garbage commitments for𝑔 ≥ 1, there must be at least 𝑔 garbage commitments. Hereafter, the garbage collection
for 𝑔 garbage commitments is sometimes referred to as 𝑔-GC.
Bearing these in mind, we naturally obtain a class of one-free-pair 𝑛-input AND
protocols, which we call the MSbatching protocols, as follows.
1. 𝑎 := 𝑛, 𝑏 := 1.
2. Now there are 𝑎 commitments and 𝑏 free pairs (and hence, there are 𝑛 − 𝑎 − 𝑏 + 1
garbage commitments). Perform one of the followings.
(a) Apply 𝑘-MSbatching such that 𝑎 ≥ 2𝑘 and 𝑏 ≥ 𝑘 + 𝑘 ⌈log2 𝑘⌉. In this case, thenumber of commitments decreases by 𝑘, the number of garbage commitments
increases by 𝑘, and the number of free pairs remains the same. Thus, we set
𝑎 := 𝑎 − 𝑘, 𝑏 := 𝑏.

Two-Helping-Card Multi-Input AND Protocols

11(b) Apply 𝑔-GC such that 1 ≤ 𝑔 ≤ 𝑛 − 𝑎 − 𝑏 + 1. Since 𝑔 free pairs arise, we set
𝑎 := 𝑎, 𝑏 := 𝑏 + 𝑔.
3. If 𝑎 ≥ 2, then return to Step 2.
As described above, determining the strategy of selection in Step 2 stipulates one
protocol. When 𝑎 ≥ 2, 1-MSbatching is always applicable, so it is never unselectable
in Step 2. Note that the number of times Step 2 is executed is directly the number of
shuﬄes the protocol uses.
4.2 MSbatching Move-Sequence Problem
Each protocol in the class of MSbatching protocols deﬁned in Sect. 4.1 changes thecurrent number of commitments 𝑎 and the current number of free pairs 𝑏 according to
the selection in Step 2. Therefore, let us represent the current state at each iteration of
Step 2 by a pair (𝑎, 𝑏) and consider it as a point (𝑎, 𝑏) on the 𝑎𝑏-plane.
When 𝑎 = 1, there is exactly one commitment and the protocol terminates; thus, wecall any point (1, 𝑏) a terminal point.
Assume a point (𝑎, 𝑏) which is not terminal; from the point (𝑎, 𝑏), we transition toanother point by either of the following operations.
1. Transition to the point (𝑎 − 𝑘, 𝑏) by 𝑘-MSbatching (provided that 𝑎 ≥ 2𝑘 and𝑏 ≥ 𝑘 + 𝑘 ⌈log2 𝑘⌉). Denote this by 𝐵 𝑘 (𝑎, 𝑏) = (𝑎 − 𝑘, 𝑏).
2. Transition to the point (𝑎, 𝑏 + 𝑔) by 𝑔-GC (provided that 1 ≤ 𝑔 ≤ 𝑛 − 𝑎 − 𝑏 + 1).
Denote this by 𝐺𝐶 𝑔 (𝑎, 𝑏) = (𝑎, 𝑏 + 𝑔).
In the 𝑎𝑏-plane, starting from point (𝑛, 1), the current state (𝑎, 𝑏) moves by Transition
1 or 2. Transition 1 moves horizontally (left) and Transition (2) moves vertically (up). The
number of transitions required to reach a terminal point from the start (𝑛, 1) corresponds
to the number of shuﬄes. That is, the length of the move-sequence connecting the startand terminal points corresponds to the number of shuﬄes used in the corresponding
protocol. Figure 1 shows the move-sequence corresponding to the protocol illustrated in
Sect. 3.3.
Figure 2 illustrates the area to which Transition 1 can be applied. From the lightest
color to the darkest, they represent the regions to which 𝑘-MSbatching can be appliedwith 𝑘 = 2, 3, . . . , 9.
The MSbatching move-sequence problem is deﬁned as easily imagined: given a startpoint (𝑛, 1), ﬁnd a move-sequence to an terminal point on the 𝑎𝑏-plane where only
Transitions 1 and 2 are applicable. Such a move-sequence uniquely corresponds an
MSbatching protocol, and the length of the move-sequence corresponds to the numberof shuﬄes. Therefore, ﬁnding a shortest move-sequence is equivalent to constructing an
optimal MSbatching protocol in terms of the number of shuﬄes.

5 Proposed Protocol
In this section, we propose a generic construction for an 𝑛-input MSbatching protocol
by giving how to choose Transitions 1 and 2.

12

T. Yoshida et al.

Fig. 1: The 48-input MSbatching protocol given in Sect. 3.3

5.1 Description of Proposed Protocol
First, we explain the idea of how to choose Transitions 1 and 2 in the proposed protocol.
Basically, 𝑘-MSbatching to be applied is limited to those where 𝑘 is a power of 2. If thegarbage collection would allow for a larger MSbatching size compared to the currently
applicable MSbatching, then perform the garbage collection.
To describe the above idea formally, the proposed protocol chooses a transition fora point (𝑎, 𝑏) such that 𝑎 ≥ 2 as follows, where let 𝑘 𝑏 be the maximum value of 𝑘 thatsatisﬁes 𝑎 ≥ 2𝑘 and 𝑏 ≥ 𝑘 + 𝑘 ⌈log2 𝑘⌉, and let 𝑘 𝑏+𝑔 be the maximum value of 𝑘 thatsatisﬁes 𝑎 ≥ 2𝑘 and 𝑏 + 𝑔 ≥ 𝑘 + 𝑘 ⌈log2 𝑘⌉.
– If 𝑘 𝑏+𝑔 > 𝑘 𝑏 and 𝑘 𝑏+𝑔 = 2𝑖 for some integer 𝑖, perform (𝑛 − 𝑎 − 𝑏 + 1)-GC andtransition to 𝐺𝐶 (𝑛−𝑎−𝑏+1) (𝑎, 𝑏) = (𝑎, 𝑛 − 𝑎 + 1).
– Otherwise, perform 𝑘 𝑏 -MSbatching and transition to 𝐵 𝑘𝑏 (𝑎, 𝑏) = (𝑎 − 𝑘 𝑏 , 𝑏).
5.2 Proposed Protocol for 𝒏 = 48
Here, we illustrate the proposed protocol for the case of 𝑛 = 48 as an example. That is,
Figure 3 shows the move-sequence of the proposed protocol in the case of 48 inputs.
For further explanation, 1-MSbatching is performed until enough garbage commitments have been accumulated for 2-MSbatching, i.e., for 𝑎 = 48, 47, 46. Next, after performing 3-GC when 𝑎 = 45 is reached, 2-MSbatching is applied. Then, 2-MSbatchingis performed until enough garbage commitments are accumulated for 4-MSbatching,Two-Helping-Card Multi-Input AND Protocols

13

Fig. 2: The area to which 𝑘-MSbatching can be appliedi.e., until 𝑎 = 39. When 𝑎 = 37 is reached, 8-GC is performed and then 4-MSbatching isapplied. In the same way, continue 4-MSbatching for a while and apply 8-MSbatching at
𝑎 = 17. Then apply 4-MSbatching, 2-MSbatching, and 1-MSbatching for 𝑎 = 9, 5, 3, 2.
Since the number of transitions above is 20, the number of shuﬄes in the proposed
protocol is 20. Since the number of shuﬄes for the protocol introduced in Sect. 3.3 is28, it is a successful improvement.
We show the number of shuﬄes in our protocol for 2 ≤ 𝑛 ≤ 50 in Figure 4.

6 Search for Optimal Protocols
In this section, we verify whether the protocol proposed in Sect. 5 is optimal in the sensethat it minimizes the number of shuﬄes among all the MSbatching protocols. Speciﬁcally, we ﬁnd shortest move-sequences in the MSbatching move-sequence problem by adynamic programming algorithm in the range up to 𝑛 = 500.
First, in Sect. 6.1, two lemmas are given to narrow the space where we have tosearch. Next, in Sect. 6.2, we present the strategy for ﬁnding shortest move-sequences.
After that, in Sect. 6.3, we compare the number of shuﬄes in the proposed protocol withthe minimum number of shuﬄes.

14

T. Yoshida et al.

Fig. 3: Proposed protocol for 𝑛 = 48

6.1 Lemmas to Narrow Search Space
When searching for shortest move-sequences in the MSbatching move-sequence problem
presented in Sect. 4, the following two lemmas imply that there are transitions that do
not need to be considered, narrowing the search space. Hereafter, 𝑛 is ﬁxed and 𝑀 (𝑎, 𝑏)
denotes the shortest move-sequence length from point (𝑎, 𝑏) to a terminal point.
The following Lemma 1 indicates that whenever the garbage collection is performed,
it should be done on all the remaining garbage commitments.
Lemma 1 For any 𝑔 and 𝑔 ′ such that 1 ≤ 𝑔 < 𝑔 ′ ≤ 𝑛 − 𝑎 − 𝑏 + 1, 𝑀 (𝑎, 𝑏 + 𝑔) ≥𝑀 (𝑎, 𝑏 + 𝑔 ′ ).
Proof. We prove that 𝑀 (𝑎, 𝑏 + 𝑔) ≥ 𝑀 (𝑎, 𝑏 + 𝑔 + 1) because it implies the lemma.
Let 𝑃 be a shortest move-sequence from point (𝑎, 𝑏 + 𝑔) to a terminal point, anduse induction on the length of 𝑃. When 𝑃 has length 1, (𝑎, 𝑏 + 𝑔) is terminated bysome 𝑘-MSbatching. Since the same 𝑘-MSbatching can be applied to (𝑎, 𝑏 + 𝑔 + 1),
𝑀 (𝑎, 𝑏 + 𝑔) = 𝑀 (𝑎, 𝑏 + 𝑔 + 1) = 1 and the claim holds. Assume inductively that when
𝑃 has length 2 or more, the claim holds for those having a smaller length. When the ﬁrst′′
move of 𝑃 transitions upward from the point (𝑎, 𝑏 + 𝑔) to 𝐺𝐶 𝑔 (𝑎, 𝑏) = (𝑎, 𝑏 + 𝑔 ′′ ), thepoint (𝑎, 𝑏 + 𝑔 + 1) can also transition to the same point (𝑎, 𝑏 + 𝑔 ′′ ) (or 𝑏 + 𝑔 + 1 = 𝑏 + 𝑔 ′′ ),and hence, 𝑀 (𝑎, 𝑏 + 𝑔) = 𝑀 (𝑎, 𝑏 + 𝑔 ′′ ) + 1 and 𝑀 (𝑎, 𝑏 + 𝑔 + 1) ≤ 𝑀 (𝑎, 𝑏 + 𝑔 ′′ ) + 1, fromwhich we have 𝑀 (𝑎, 𝑏 + 𝑔) ≥ 𝑀 (𝑎, 𝑏 + 𝑔 + 1) as desired. When the ﬁrst move of 𝑃 isleftward, some 𝑘-MSbatching transitions to 𝐵 𝑘 (𝑎, 𝑏+𝑔) = (𝑎−𝑘, 𝑏+𝑔) and 𝑀 (𝑎, 𝑏+𝑔) =Two-Helping-Card Multi-Input AND Protocols

15

Fig. 4: Number of shuﬄes in our protocol for 2 ≤ 𝑛 ≤ 50

𝑀 (𝑎 − 𝑘, 𝑏 +𝑔) +1. Since the same 𝑘-MSbatching can be applied to the point (𝑎, 𝑏 +𝑔 +1)
and 𝐵 𝑘 (𝑎, 𝑏 + 𝑔 + 1) = (𝑎 − 𝑘, 𝑏 + 𝑔 + 1), we have 𝑀 (𝑎, 𝑏 + 𝑔 + 1) ≤ 𝑀 (𝑎 − 𝑘, 𝑏 + 𝑔 + 1) + 1.
Also, from the induction assumption, 𝑀 (𝑎 − 𝑘, 𝑏 + 𝑔) ≥ 𝑀 (𝑎 − 𝑘, 𝑏 + 𝑔 + 1). Therefore,
the claim holds.
⊔⊓
The following Lemma 2 indicates that when MSbatching is perfomed, it should be
the largest size.
Lemma 2 If 𝑎 < 𝑎 ′ , then 𝑀 (𝑎, 𝑏) ≤ 𝑀 (𝑎 ′ , 𝑏).
Proof. We prove that 𝑀 (𝑎, 𝑏) ≤ 𝑀 (𝑎 + 1, 𝑏) because it implies the lemma. Let 𝑃 be ashortest move-sequence from point (𝑎 + 1, 𝑏) to a terminal point, and use induction on
the length of 𝑃. When 𝑃 has length 1, we have 𝑎 + 1 = 2, i.e., 𝑎 = 1. Therefore, since𝑀 (𝑎, 𝑏) = 0, the claim holds. Assume inductively that when 𝑃 has length 2 or more,
the claim holds for those having a smaller length. When the ﬁrst move of 𝑃 is upward,
there exists some 𝑔 such that 𝑀 (𝑎 + 1, 𝑏) = 𝑀 (𝑎 + 1, 𝑏 + 𝑔) + 1. Also, from the induction
assumption, 𝑀 (𝑎, 𝑏 + 𝑔) ≤ 𝑀 (𝑎 + 1, 𝑏 + 𝑔). Since 𝑀 (𝑎, 𝑏) ≤ 𝑀 (𝑎, 𝑏 + 𝑔) + 1, the claim
holds. When the ﬁrst move of 𝑃 is leftward, by some 𝑘-MSbatching, 𝑀 (𝑎 + 1, 𝑏) =𝑀 (𝑎 − 𝑘 + 1, 𝑏) + 1 and 𝑎 + 1 ≥ 2𝑘. Therefore, 𝑀 (𝑎, 𝑏) ≤ 𝑀 (𝑎 − (𝑘 − 1), 𝑏) + 1 =𝑀 (𝑎−𝑘 +1, 𝑏) +1 since (𝑘 −1)-MSbatching can be applied to the point (𝑎, 𝑏). Therefore,
the claim holds.
⊔
⊓

16

T. Yoshida et al.

Algorithm 1 Shortest move-sequence search.
1: function MIN_ COST(𝑛)2:𝑛 ← number of inputs
3:
SMS[𝑛] [𝑛 + 1]
4:
for 1 ≤ 𝑎 ≤ 𝑛 do
5:for 𝑛 − 𝑎 + 1 ≥ 𝑏 ≥ 1 do
6:
if 𝑏 == 𝑛 − 𝑎 + 1 then7:
SMS[𝑎] [𝑏] = SMS[𝑎 − 𝑘 𝑏 ] [𝑏] + 1
8:else if 𝑏 < 𝑛 − 𝑎 + 1 then9:
if SMS[𝑎] [𝑛 − 𝑎 + 1] ≤ SMS[𝑎 − 𝑘 𝑏 ] [𝑏] then10:
SMS[𝑎] [𝑏] = SMS[𝑎] [𝑛 − 𝑎 + 1] + 1
11:
else
12:
SMS[𝑎] [𝑏] = SMS[𝑎 − 𝑘 𝑏 ] [𝑏] + 1
13:
end if14:
end if15:
end for16:
end for17: end function

6.2 Shortest Move-Sequence SearchHere, the shortest move-sequence length for each 𝑛 ≤ 500 is obtained by running a
dynamic programming algorithm for the search space of the MSbatching move-sequence
problem, which is narrowed by Lemmas 1 and 2 in Sect. 6.1. The pseudo code for the
search is shown in Algorithm 1. The algorithm is explained below.
To search the entire move-sequence space from point (𝑛, 1) to a terminal point,
we deﬁne a 2-dimensional array named SMS (Shortest Move Sequence) in Line 3 ofAlgorithm 1.
First, the search range is explained. Since it is assumed that the move-sequence is
explored in reverse, 𝑎 is processed in ascending order over the range of 1 ≤ 𝑎 ≤ 𝑛 and 𝑏
is processed in descending order over the range of 1 ≤ 𝑏 ≤ 𝑛 − 𝑎 + 1. When 𝑏 = 𝑛 − 𝑎 + 1,
it means that there is no garbage commitment, which is the boundary. Figure 5 shows
the search area (boundary) when 𝑛 = 48, for example.
Next, the transition selection method is explained. Line 6 is the condition on theboundary 𝑏 = 𝑛 − 𝑎 + 1 shown in Figure 5. Since no further GC can be performed on
the boundary, add 1 to the value at the transition moved to the left by 𝑘 𝑏 -MSbatching,i.e., SMS[𝑎 − 𝑘 𝑏 ] [𝑏]. The conditions from Line 8 are about the inside of the searcharea. Line 9 adds 1 to SMS[𝑎] [𝑛 − 𝑎 + 1] since Transition 2 is better. Line 11 adds 1 to
SMS[𝑎 − 𝑘 𝑏 ] [𝑏] because Transition 1 is better.
This algorithm was executed on a computer for up to 𝑛 = 500.
6.3 Comparison
Here, we compare the number of shuﬄes for the protocol proposed in Sect. 5 with theshortest move-sequence length calculated in Sect. 6.2.

Two-Helping-Card Multi-Input AND Protocols

17

Fig. 5: Possible points to visit for 𝑛 = 48
As mentioned above, the search was performed within 𝑛 ≤ 500 of inputs, and theshortest move-sequence lengths were obtained by a computer. Compared to the numberof shuﬄes for the proposed protocol in Sect. 5, in many cases they are consistent and the
proposed protocol is optimal. On the other hand, in some cases, the proposed protocol is
not optimal, and speciﬁcally, there is a protocol that is better than the proposed protocol
at 𝑛 as shown in Table 2.
As shown in Table 2, the number of shuﬄes of the proposed protocol is found to beminimum or only one more than the minimum. Although only the shortest lengths areshown in Table 2 when the proposed protocol is not optimal, the shortest move-sequences
themselves were of course obtained for all the range 𝑛 ≤ 500.
No rule of thumb has been found for cases where the proposed protocol is not
optimal. Nor is the speciﬁc procedure for giving an optimal protocol known. While it
is interesting to consider these issues, since card-based cryptography is expected to be
performed by human hands, it may be suﬃcient to have optimal protocols up to 𝑛 = 500
ﬁgured out.

7 Conclusion
In this paper, we gave a natural class of committed-format two-helping-card 𝑛-input
AND protocols based on the batching technique and the MS-AND protocol, and showed
optimal protocols among them in terms of the minimum number of shuﬄes up to𝑛 = 500.

18

T. Yoshida et al.

.
Table 2: Numbers of inputs that do not minimize the number of shuﬄes in the proposed
protocolNumber of inputs 𝑛 Proposed protocol’s shuﬄes Shortest length
48 - 4956
104
112 - 115
128 - 129240 - 247
256 - 271
288 - 295
320 - 323
352

20
21
27
28
29
36
37
38
39
40

19
20
26
27
28
35
36
37
38
39

Note that the “optimality” here was discussed within the class of MSbatching protocols, and hence, it is still open to determine whether the upper bounds on the numberof shuﬄes obtained in this paper are also lower bounds on the number of shuﬄes forany committed-format two-helping-card AND protocols (that are not necessarily basedon the MS-AND protocol or the batching technique).

Acknowledgements
We thank the anonymous referees, whose comments have helped us to improve thepresentation of the paper. This work was supported in part by JSPS KAKENHI Grant
Numbers JP21K11881 and JP23H00479.

References
1. Abe, Y., Nakai, T., Kuroki, Y., Suzuki, S., Koga, Y., Watanabe, Y., Iwamoto, M., Ohta, K.:Eﬃcient card-based majority voting protocols. New Gener. Comput. 40, 173–198 (2022),
https://doi.org/10.1007/s00354-022-00161-7
2. Crépeau, C., Kilian, J.: Discreet solitary games. In: Stinson, D.R. (ed.) Advances in
Cryptology—CRYPTO’ 93. LNCS, vol. 773, pp. 319–330. Springer, Berlin, Heidelberg(1994), https://doi.org/10.1007/3-540-48329-2_27
3. Haga, R., Hayashi, Y., Miyahara, D., Mizuki, T.: Card-minimal protocols for three-input functions with standard playing cards. In: Batina, L., Daemen, J. (eds.) Progress in Cryptology—
AFRICACRYPT 2022. LNCS, vol. 13503, pp. 448–468. Springer, Cham (2022)
4. Hand, S., Koch, A., Lafourcade, P., Miyahara, D., Robert, L.: Check alternating patterns: A
physical zero-knowledge proof for Moon-or-Sun. In: Shikata, J., Kuzuno, H. (eds.) Advancesin Information and Computer Security. LNCS, vol. 14128, pp. 255–272. Springer, Cham
(2023), https://doi.org/10.1007/978-3-031-41326-1_14

Two-Helping-Card Multi-Input AND Protocols

19

5. Ishikawa, R., Chida, E., Mizuki, T.: Eﬃcient card-based protocols for generating a hidden
random permutation without ﬁxed points. In: Calude, C.S., Dinneen, M.J. (eds.) Unconventional Computation and Natural Computation. LNCS, vol. 9252, pp. 215–226. Springer,
Cham (2015), https://doi.org/10.1007/978-3-319-21819-9_16
6. Isuzugawa, R., Toyoda, K., Sasaki, Y., Miyahara, D., Mizuki, T.: A card-minimal three-input
AND protocol using two shuﬄes. 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
7. 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
8. Koch, A.: The landscape of optimal card-based protocols. Mathematical Cryptology 1(2), 115–131 (2022), https://journals.flvc.org/mathcryptology/article/
view/130529
9. Koch, A., Walzer, S., Härtel, K.: Card-based cryptographic protocols using a minimal numberof 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
10. Komano, Y., Mizuki, T.: Card-based zero-knowledge proof protocol for pancake sorting.
In: Bella, G., Doinea, M., Janicke, H. (eds.) Innovative Security Solutions for Information
Technology and Communications. LNCS, vol. 13809, pp. 222–239. Springer, Cham (2023),
https://doi.org/10.1007/978-3-031-32636-3_13
11. Kuzuma, T., Toyoda, K., Miyahara, D., Mizuki, T.: Card-based single-shuﬄe protocols forsecure multiple-input AND and XOR computations. In: ASIA Public-Key Cryptography. pp.
51–58. ACM, NY (2022), https://doi.org/10.1145/3494105.3526236
12. 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
13. Miyahara, D., Mizuki, T.: Secure computations through checking suits of playing cards. In:
Frontiers in Algorithmics. Lecture Notes in Computer Science, Springer, Cham (2022), toappear
14. Miyamoto, K., Shinagawa, K.: Graph automorphism shuﬄes from pile-scramble
shuﬄes. New Gener. Comput. 40, 199–223 (2022), https://doi.org/10.1007/
s00354-022-00164-4
15. 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
16. 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
17. 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
18. Mizuki, T., Komano, Y.: Information leakage due to operative errors in card-based protocols.
Inf. Comput. 285, 104910 (2022), https://doi.org/10.1016/j.ic.2022.104910
19. Mizuki, T., Shizuya, H.: Computational model of card-based cryptographic protocols andits applications. IEICE Trans. Fundam. E100.A(1), 3–11 (2017), https://doi.org/10.
1587/transfun.E100.A.3
20. 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

20

T. Yoshida et al.

21. 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. 40, 95–
113 (2022), https://doi.org/10.1007/s00354-022-00153-7
22. Niemi, V., Renvall, A.: Secure multiparty computations without computers. Theor. Comput.
Sci. 191(1–2), 173–183 (1998), https://doi.org/10.1016/S0304-3975(97)00107-2
23. Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Physical ZKP protocols for Nurimisaki
and Kurodoko. Theor. Comput. Sci. 972, 114071 (2023), https://doi.org/10.1016/j.
tcs.2023.114071
24. Ruangwises, S.: Physical zero-knowledge proof for ball sort puzzle. In: Della Vedova, G., Dundua, B., Lempp, S., Manea, F. (eds.) Unity of Logic and Computation. LNCS, vol. 13967, pp.
246–257. Springer, Cham (2023), https://doi.org/10.1007/978-3-031-36978-0_20
25. Ruangwises, S., Itoh, T.: AND protocols using only uniform shuﬄes. In: van Bevern, R.,
Kucherov, G. (eds.) Computer Science–Theory and Applications. LNCS, vol. 11532, pp.
349–358. Springer, Cham (2019), https://doi.org/10.1007/978-3-030-19955-5_30
26. 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
27. Shikata, H., Miyahara, D., Mizuki, T.: Few-helping-card protocols for some wider class of
symmetric Boolean functions with arbitrary ranges. In: 10th ACM Asia Public-Key Cryptography Workshop. pp. 33–41. APKC ’23, ACM, New York (2023), https://doi.org/10.
1145/3591866.3593073
28. Shikata, H., Toyoda, K., Miyahara, D., Mizuki, T.: Card-minimal protocols for symmetricboolean functions of more than seven inputs. In: Seidl, H., Liu, Z., Pasareanu, C.S. (eds.)
Theoretical Aspects of Computing – ICTAC 2022. pp. 388–406. Springer International
Publishing, Cham (2022)
29. Shimano, M., Sakiyama, K., Miyahara, D.: Towards verifying physical assumption in cardbased cryptography. In: Bella, G., Doinea, M., Janicke, H. (eds.) Innovative Security Solutions
for Information Technology and Communications. LNCS, vol. 13809, pp. 289–305. Springer,
Cham (2023), https://doi.org/10.1007/978-3-031-32636-3_17
30. Shinagawa, K., Miyamoto, K.: Automorphism shuﬄes for graphs and hypergraphs and its
applications. IEICE Trans. Fundam. E106.A(3), 306–314 (2023), https://doi.org/10.
1587/transfun.2022CIP0020
31. Shinagawa, K., Nuida, K.: A single shuﬄe is enough for secure card-based computation of
any Boolean circuit. Discrete Applied Mathematics 289, 248–261 (2021), https://doi.
org/10.1016/j.dam.2020.10.013
32. Shinagawa, K., Nuida, K.: Single-shuﬄe full-open card-based protocols imply private
simultaneous messages protocols. Cryptology ePrint Archive, Paper 2022/1306 (2022),
https://eprint.iacr.org/2022/1306, https://eprint.iacr.org/2022/1306
33. Stiglic, A.: Computations with a deck of cards. Theor. Comput. Sci. 259(1–2), 671–678(2001), https://doi.org/10.1016/S0304-3975(00)00409-6
34. Suga, Y.: A classiﬁcation 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. pp. 171–172. IEEE, NY (2022), https://doi.org/
10.1109/ICCE-Taiwan55306.2022.9869063
35. Ueda, I., Miyahara, D., Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: Secure implementations of a random bisection cut. Int. J. Inf. Secur. 19(4), 445–452 (2020), https://doi.org/10.1007/s10207-019-00463-w
36. 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