A Card-Minimal Three-Input AND Protocol
Using Two Shuffles⋆
Raimu Isuzugawa1 , Kodai Toyoda1 , Yu Sasaki1 , Daiki Miyahara1,2 , andTakaaki Mizuki1,2
1

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

Abstract. Card-based cryptography typically uses a physical deck comprising black and red cards to perform secure computations, where a
one-bit value is encoded using a pair of cards with different colors suchthat the order of black to red represents 0 and red to black represents 1.
One of the most fundamental classes of card-based protocols is the classof “card-minimal” n-input AND protocols, which require 2n face-downcards as input to securely evaluate the AND value after applying a number of shuffles; here, the 2n cards are minimally required to describe an
n-bit input. The best n-input AND protocols currently known use two
shuffles for n = 2, five shuffles for n = 3, and n + 1 shuffles for n > 3.
These upper bounds on the numbers of shuffles have not been improvedfor several years. In this work, we present a better upper bound for then = 3 case by designing a new card-minimal three-input AND protocol using only two shuffles. Therefore, our proposed protocol reduces thenumber of required shuffles from five to two; we believe that this is asignificant improvement.

1 Introduction
Many card-based protocols have been designed in the history of card-based cryptography to perform secure computations using a deck of physical cards. Typically, card-based protocols work on two-colored decks comprising black ♣ andred ♡ cards whose backs are denoted by ? and indistinguishable. These cards
are used to represent Boolean values as follows:♣ ♡ = 0,♡ ♣ = 1.

(1)

When two face-down cards represent a bit x ∈ {0, 1} according to the above
encoding rule (1), we call them a commitment to x, denoted as? ? .
| {z }x⋆

This paper appears in Proceedings of COCOON 2021. The final authenticated version is available online at https://doi.org/10.1007/978-3-030-89543-3_55.

2

R. Isuzugawa et al.

1.1 Card-Minimal AND Protocols
In 1989, Den Boer [2] designed the first card-based protocol, called the “fivecard trick,” which takes two commitments to x1 , x2 ∈ {0, 1} and a helping card
♡ as input to securely evaluate the AND value x1 ∧ x2 (without revealing any
information about x1 , x2 more than necessary) through a series of actions, suchas shuffling and turning over cards:? ? ? ? ♡ → · · · → x1 ∧ x2 .
| {z } | {z }x1x2

Thus, this is a two-input AND protocol using one helping card.
Since then, a challenging open problem had been to construct a two-input
AND protocol without any helping card. More generally, could we construct ann-input AND protocol using only 2n cards?
? ? ? ? · · · ? ? → · · · → x1 ∧ x2 ∧ · · · ∧ xn .
| {z } | {z }| {z }
x1

x2

xn

Because 2n cards are necessary for arranging the n input commitments to thevalues x1 , x2 , . . . , xn ∈ {0, 1} (as long as we obey the encoding rule (1)), thistype of AND protocol (using exactly 2n cards) is said to be card-minimal. This
study addresses the class of card-minimal AND protocols.
1.2 Known Results
The first card-minimal AND protocol was proposed by Kumamoto et al. in2012 [12]: x1 ∧ x2 = 0x ∧ x = 0
2 RBCs1
2? ? ? ? → ··· → x1 ∧ x2 = 1| {z } | {z }



x1
x2
x1 ∧ x2 = 1

if
if
if
if

? ♣ ? ♡♣♡ ? ?
? ♣ ? ♣♡♡ ? ?.

That is, using only four cards, a two-input AND protocol was constructed. This
protocol uses two shuffles; more precisely, it applies a “random bisection cut(RBC)” twice, which is a kind of shuffling operation (explained later in Sect. 2.3).
See the first protocol listed in Table 1.
How about n-input AND protocols for n ≥ 3? This open problem was solvedin 2016 [11]. Specifically, for the case of n = 3, a card-minimal three-input AND
protocol was proposed by Mizuki [11]:x1 ∧ x2 ∧ x3 = 1 if ♣ ♣ ♣ · · ·3 RBCs & 2 RCs→ ··· →
x1 ∧ x2 ∧ x3 = 1 if ♡ ♡ ♡ · · ·? ? ? ? ? ?
| {z } | {z } | {z }
x1 ∧ x2 ∧ x3 = 0 otherwise.
x1
x2
x3

A Card-Minimal Three-Input AND Protocol Using Two Shuffles

3

Table 1. Existing card-minimal AND protocols and our proposed protocol (using
random cuts and/or random bisection cuts)#Inputs #Cards #Shuffles
Kumamoto et al. [12]242
Mizuki [11]365
Mizuki [11]n (≥ 4)2nn+1This paper
3
62

Thus, this six-card protocol uses three random bisection cuts along with two“random cuts (RCs),” for a total of five shuffles; the random cut is anothercommon type of shuffling operation, which will be explained in Sect. 2.2. See thesecond protocol listed in Table 1.
For the case of n ≥ 4, Mizuki [11] also proposed a card-minimal n-input AND
protocol:(x1 ∧ x2 ∧ · · · ∧ xn = 0 if ♣ · · ·n+1 RBCs? ? ? ? ? ? ? ? ··· ? ? → ··· →x1 ∧ x2 ∧ · · · ∧ xn = 1 if ♡ · · · .
| {z } | {z } | {z } | {z }| {z }
x1

x2

x3

x4

xn

This protocol takes n input commitments (such that n ≥ 4) and uses n + 1 random bisection cuts to securely evaluate their AND value. See the third protocol
shown in Table 1.
1.3 Contribution
In this work, we focus on the number of required shuffles: From Table 1, it
is observed that the number of shuffles used in the second protocol, i.e., 5 in
the three-input AND protocol [11], is somewhat large. Actually, the three-input
protocol [11] is elaborate but rather complicated, and it seems diﬀicult for laypeople to execute practically. Therefore, our goal is to improve this existing
three-input AND protocol [11].
Specifically, we will construct a new card-minimal three-input AND protocol
using only two shuffles, namely one random bisection cut and one random cut:
x1 ∧ x2 ∧ x3 = 1 if ♣ ♣ ♣ · · ·1 RBC & 1 RC
x1 ∧ x2 ∧ x3 = 1 if ♡ ♡ ♡ · · ·? ? ? ? ? ? → ··· →| {z } | {z } | {z }
x1 ∧ x2 ∧ x3 = 0 otherwise.
x1
x2
x3
The performance of this approach is shown in Table 1 in the last row.
Fig. 1 shows the numbers of required shuffles for all the protocols listed in Table 1. As seen from this figure, the previous three-input protocol [11] requires five
shuffles while our proposed three-input protocol uses only two shuffles, thereby
successfully reducing the number of required shuffles significantly from five totwo. As shown later in Sect. 3, our designed protocol is simple enough for laypeople to execute practically. Therefore, we believe that our new protocol isimportant from both theoretical and practical points of view.

R. Isuzugawa et al.

#shuffles

4

10
9
8
7
6
5
4
3
2
1
0

・
・・

Existing Protocols
Our Proposed Protocol

0

1

2

3

4
5
#inputs

6

7

8 ・・・

Fig. 1. Numbers of shuffles used in the existing card-minimal n-input AND protocols(for all n ≥ 2) and our proposed protocol

1.4 Related WorkAll the protocols mentioned thus far are not committed-format AND protocols
because their AND values are not obtained as commitments. Contrarily, there
are committed-format protocols, such as committed-format two-input AND protocols, which produce commitments to the AND values:? ? ? ? → ··· → ? ? .
| {z } | {z }| {z }x1

x2

x1 ∧x2Since this output is a (hidden) commitment, it can be used as input to anothercomputation; thus, by repeatedly executing a committed-format AND protocoln − 1 times, we can perform an n-input AND computation. Therefore, cardminimal committed-format two-input AND protocols are considered useful. Unfortunately however, such known AND protocols [4, 8, 23] require nonuniform or
nonclosed shuffles, which are diﬀicult to implement manually (cf. [17, 18, 25]);
furthermore, Kastner et al. [3] proved that there exist no card-minimal twoinput AND protocols that use only uniform closed shuffles. It should be notedthat both random cuts and random bisection cuts (which all the protocols listed
in Table 1 rely on) are uniform closed shuffles, which are easy to implement (asshown in Sects. 2.2 and 2.3).
If we allow the use of helping cards, we have a six-card committed-format
AND protocol [15] and a five-card committed-format AND protocol [1] that rely
only on random cuts and/or random bisection cuts; however, of course, they are
not card-minimal.
Apart from the AND computation, because there is a card-minimal committedformat two-input XOR protocol [15], we can construct a card-minimal n-input
XOR protocol for any n ≥ 2. Recently, Ruangwises and Itoh [24] constructeda general way of designing card-minimal protocols that securely compute any
doubly symmetric functions.

A Card-Minimal Three-Input AND Protocol Using Two Shuffles

5

In stead of using shuffling operations, there is an alternative approach that
relies on private operations (e.g., [16, 19–21, 28]); under this somewhat strong
assumption, Manabe and Ono [9,22] showed that card-minimal protocols can beconstructed for many kinds of Boolean functions, such as the AND, half-adder,full-adder, and symmetric functions.

2 Preliminaries
In this section, we first present a formal treatment of the actions used in cardbased protocols (which has been developed in [3, 5, 13, 14]). Then, we formally
introduce two shuffling operations, namely a random cut and a random bisection
cut.
2.1 Actions in Card-Based Protocols
In card-based protocols, the following three main actions are applied to a sequence of cards; below, we assume a sequence of m cards.
Permute. This is denoted by (perm, π), where π is a permutation applied tothe sequence of cards as follows:12m? ? ··· ?

(perm,π)−−−−−→

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

?

?

···

π −1 (m)?

.

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

2

t∈T

m

? ? ··· ? ··· ?

1(turn,T )−−−−−→

2t∈Tm? ? ··· ♣ ··· ? .

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

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

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

?

?

···

π −1 (m)?

.

Here, the permutation in Π that is applied remains unknown. If the distribution F is uniform, then its description can be omitted.
2.2 Random Cut
A random cut (RC) is the simplest and most easy-to-implement shuffle in cardbased cryptography, denoted by ⟨·⟩, which shifts a sequence of cards cyclicallyand randomly. If a random cut is applied to a sequence of m cards, then the6

R. Isuzugawa et al.

resulting sequence becomes one of the following n sequences, each of which occurs
with a probability of 1/m:
 1 2 3m−1 m
 ? ? ? ··· ? ? ,



2 3 4
m 1



··· ? ? ,?
?
?

1 2 3

m−1 m
..
−
→
? ? ? ··· ? ?
.

m−1 m 1m−3 m−2
 ? ? ? ··· ? ? ,m−2 m−1 m 1 2
? ? ? ··· ? ? .
This random cut is formally described as(shuf, {id, π, π 2 , . . . , π m−1 })for a cyclic permutation π = (1 2 3 · · · m), where id denotes the identity permutation.
Hereinafter, we use RC1,2,...,m to represent {id, π, π 2 , . . . , π m−1 }. For example, (shuf, RC1,2,3,4,5,6 ) is a random cut to a sequence of six face-down cards:
? ? ? ? ? ?

.

A random cut can be easily performed manually; a secure implementation
called the Hindu cut is a well-known instance [27].
2.3 Random Bisection Cut
A random bisection cut (RBC) is another major shuffle action, which was invented in 2009 [15]. This shuffle, denoted by [ · | · ], bisects a sequence of 2m cards
and randomly swaps the two halves; the resulting sequence becomes one of thefollowing two sequences, with a probability of 1/2:h 1m
? ··· ?

m+1

2m i

? ··· ?

 1
m m+1
2m

? ··· ? ? ··· ? ,
→ m+1
2m 1
m

? ··· ? ? ··· ? .

That is, the resulting sequence either remains unchanged compared with theoriginal or is obtained such that the two halves are swapped, with a probabilityof 1/2. The random bisection cut can be expressed as follows:(shuf, {id, (1 m+1)(2 m+2) · · · (m 2m)}).
Secure implementations of a random bisection cut were shown in [26].

A Card-Minimal Three-Input AND Protocol Using Two Shuffles

7

3 Our Proposed Protocol
In this section, we present the new card-minimal three-input AND protocol:x1 ∧ x2 ∧ x3 = 1 if ♣ ♣ ♣ · · ·1 RBC & 1 RC
→
·
·
·
→
x1 ∧ x2 ∧ x3 = 1 if ♡ ♡ ♡ · · ·? ? ? ? ? ?
| {z } | {z } | {z }
x1 ∧ x2 ∧ x3 = 0 otherwise.
x1
x2
x3
This protocol uses one random bisection cut and one random cut.
We present the description of our protocol in Sect. 3.1 as well as its pseudocode in Sect. 3.2. We also present an intuitive explanation in Sect. 3.3 as
to why the proposed protocol works correctly. Formal proofs of the correctness
and security of our proposed protocol (based on the so-called KWH-tree [8]) areomitted owing to length limitations.
3.1 Description
Our card-minimal three-input AND protocol proceeds, as follows.
1. Apply (shuf, {id, (1 2)(3 6)}) by performing operations (a)–(c) noted below.
(a) Swap the second and third cards as well as the fourth and sixth cards:
1

2

3

4

5

6

1

3

2

6

5

4

? ? ? ? ? ? → ? ? ? ? ? ?.
(b) Apply a random bisection cut to the four cards on the extreme left:
i

h
? ?

? ?

? ? → ? ? ? ? ? ?.

(c) Swap the second and third cards as well as the fourth and sixth cards
again:
1

2

3

4

5

1

6

3

2

6

5

4

? ? ? ? ? ? → ? ? ? ? ? ?.
2. Turn over the first card to check its color. If the card is ♣ , swap the firstand second cards as well as the third and sixth cards:
1

2

3

4

5

6

2

1

6

4

5

3

♣ ? ? ? ? ? → ? ♣ ? ? ? ?.
If the card color is ♡ , proceed to Step 3 directly.
3. After turning over the revealed card in a face-down manner, apply a random
cut to the entire sequence:ED? ? ? ? ? ? → ? ? ? ? ? ?.

8

R. Isuzugawa et al.

4. Turn over the first, third, and fifth cards. If these are ♡ ♣ ♡ or ♣ ♡ ♣(apart from cyclic rotation), then x1 ∧ x2 ∧ x3 = 0; if the cards are ♡ ♡ ♡or ♣ ♣ ♣ , then x1 ∧ x2 ∧ x3 = 1:
♡ ? ♣ ? ♡ ? ♣ ? ♡ ? ♣ ?
♡ ? ♡ ? ♣ ? ♣ ? ♣ ? ♡ ?
♣ ? ♡ ? ♡ ? ♡ ? ♣ ? ♣ ?
x1 ∧ x2 ∧ x3 = 0,
♡ ? ♡ ? ♡ ? ♣ ? ♣ ? ♣ ?
x1 ∧ x2 ∧ x3 = 1.
3.2 Pseudocode
The pseudocode for our protocol is depicted in Algorithm 1, where (result, i, j, k)
specifies the output positions.
Algorithm 1 Our proposed protocol
input set:{( ?

? ? ? ? ?) (? ? ? ? ? ?) (? ? ? ? ? ?), , , ,,
, , , , ,,, , , , ,,♣ ♡ ♣ ♡ ♣ ♡♣ ♡ ♣ ♡ ♡ ♣♣ ♡ ♡ ♣ ♣ ♡(? ? ? ? ? ?) (? ? ? ? ? ?) (? ? ? ? ? ?), , , , ,,, , , , ,,, , , , ,,♣ ♡ ♡ ♣ ♡ ♣♡ ♣ ♣ ♡ ♣ ♡♡ ♣ ♣ ♡ ♡ ♣( ? ? ? ? ? ? ) ( ? ? ? ? ? ? )}, , , , ,,, , , , ,♡ ♣ ♡ ♣ ♣ ♡♡ ♣ ♡ ♣ ♡ ♣,1. (shuf, {id, (1 2)(3 6)})
2. (turn, {1})3. if visible sequence = (♣, ?, ?, ?, ?, ?) then4.
(perm, (1 2)(3 6))
5.
(turn, {2})6. else if visible sequence = (♡, ?, ?, ?, ?, ?) then7.
(turn, {1})8. (shuf, RC1,2,3,4,5,6 )9. (result, 1, 3, 5)

3.3 Why Our Protocol Works Correctly
Herein, we intuitively explain why our proposed protocol works correctly. Notethat the input sequence has eight possibilities depending on the input values(x1 , x2 , x3 ) ∈ {0, 1}3 , as shown in the second column of Table 2. The idea behindA Card-Minimal Three-Input AND Protocol Using Two Shuffles

9

Table 2. Resulting sequences after applying (perm,(1 2)(3 6)) and Step 2
Input Input Sequence Apply (perm,(1 2)(3 6))

After Step 2(0,0,0) ♣ ♡ ♣ ♡ ♣ ♡♡ ♣ ♡ ♡ ♣ ♣♡ ♣ ♡ ♡ ♣ ♣(0,0,1) ♣ ♡ ♣ ♡ ♡ ♣♡ ♣ ♣ ♡ ♡ ♣♡ ♣ ♣ ♡ ♡ ♣(0,1,0) ♣ ♡ ♡ ♣ ♣ ♡♡ ♣ ♡ ♣ ♣ ♡♡ ♣ ♡ ♣ ♣ ♡(0,1,1) ♣ ♡ ♡ ♣ ♡ ♣♡ ♣ ♣ ♣ ♡ ♡♡ ♣ ♣ ♣ ♡ ♡(1,0,0) ♡ ♣ ♣ ♡ ♣ ♡♣ ♡ ♡ ♡ ♣ ♣♡ ♣ ♣ ♡ ♣ ♡(1,0,1) ♡ ♣ ♣ ♡ ♡ ♣♣ ♡ ♣ ♡ ♡ ♣♡ ♣ ♣ ♡ ♡ ♣(1,1,0) ♡ ♣ ♡ ♣ ♣ ♡♣ ♡ ♡ ♣ ♣ ♡♡ ♣ ♡ ♣ ♣ ♡(1,1,1) ♡ ♣ ♡ ♣ ♡ ♣♣ ♡ ♣ ♣ ♡ ♡♡ ♣ ♡ ♣ ♡ ♣our protocol is to assign each possible input to one of two sequence patterns
without leaking the input value. One of the two patterns is an alternating patternof ♣ and ♡ , i.e., either ♣ ♡ ♣ ♡ ♣ ♡ or ♡ ♣ ♡ ♣ ♡ ♣ , which is a possible
input sequence when (x1 , x2 , x3 ) = (0, 0, 0), (1, 1, 1); we call this an alternating
sequence. The other pattern corresponds to the remaining sequences, which wecall non-alternating sequences.
Suppose that we apply the permutation (1 2)(3 6) to the input sequence; thisappears in the shuffle applied in Step 1 and permutation in Step 2. The resulting
sequence is the one shown in the third column of Table 2. Note that the second
column (i.e., input sequence) and third column of Table 2 are equivalent to thetransition possibilities after applying (shuf, {id, (1 2)(3 6)}) to the input sequencein Step 1. In the third column of Table 2, among the four sequences from thetop (which are obtained when x1 = 0), the sequences corresponding to (0, 0, 1),(0, 1, 0), and (0, 1, 1) are still non-alternating, and the sequence corresponding
to (0, 0, 0) is converted to a non-alternating sequence. If we combine the four
sequences from the top in the third column with the four sequences from thebottom in the second column, we obtain the eight sequences shown in the fourthcolumn of Table 2, where only the sequence corresponding to (1, 1, 1) is alternating. To achieve this, we apply the permutation (1 2)(3 6) when the first cards
in the sequences in the second and third columns of Table 2 are ♣ . This is thereason behind performing (shuf, {id, (1 2)(3 6)}) in Step 1 and (perm,(1 2)(3 6))
in Step 2 if the first card revealed is ♣ .
By applying a random cut to the sequence of cards in Step 3, the resulting
sequence is one among the following four sequences (up to cyclic rotation):
if (0, 0, 0) or (1, 0, 0) ;(c)

♡ ♡ ♣ ♣ ♡ ♣,♣ ♣ ♡ ♡ ♣ ♡,♡ ♡ ♡ ♣ ♣ ♣,(d)♡ ♣ ♡ ♣ ♡ ♣,if (1, 1, 1).

(a)
(b)

if (0, 0, 1), (0, 1, 0), (1, 0, 1), or (1, 1, 0) ;if (0, 1, 1) ;

10

R. Isuzugawa et al.

Here, when the input is either (0, 0, 0) or (1, 0, 0), the resulting sequence is equal
to that in (a); when the input is (0, 0, 1), (0, 1, 0), (1, 0, 1), or (1, 1, 0), the sequence is equal to that in (b); when the input is (0, 1, 1), the sequence is equal tothat in (c); when the input is (1, 1, 1), the sequence is equal to that in (d). Now,
if we revealed all the cards in the sequence, then we could obtain the value ofx1 ∧ x2 ∧ x3 ; however, information about the input would be leaked because therevealed sequence depends on the input values. Therefore, we need an alternative
approach to obtain the output value.
Let us focus on the cards at the odd-numbered positions. If we reveal only
these cards, then the revealed cards in every sequence of (a), (b), and (c) will
have the same pattern, i.e., either ♡ ♣ ♡ or ♣ ♡ ♣ up to cyclic rotation. By
contrast, if (d) occurs, then the revealed cards will be either ♡ ♡ ♡ or ♣ ♣ ♣ .
Hence, the sequences of (a), (b), and (c) become indistinguishable, and we canobtain only the value of x1 ∧ x2 ∧ x3 .

4 Conclusion
In this work, we proposed a card-minimal three-input AND protocol using only
two shuffles. The minimality means that the protocol uses exactly six cards. The
shuffles used in our protocol are one random cut and one random bisection cut.
Since the existing three-input protocol [11] requires five shuffles, our proposed
protocol successfully reduces the number of required shuffles from five to two.
We believe that this is a significant improvement and that our protocol is simple
enough for easy execution by lay-people.
An interesting open problem is improving the numbers of shuffles for cardminimal n-input AND computations for n ≥ 4. It is also an intriguing problem toseek lower bounds on the numbers of shuffles using the “formal method approach”
recently developed by Koch, Schrempp, and Kirsten [6, 7].
This work considers the number of shuffles as the quality metric for evaluatinga protocol because the shuffle action is the most time-consuming step (cf. [10]).
However, considering the other actions for a more fine-grained analysis would be
an interesting line of investigation in the future.

Acknowledgements
We thank the anonymous referees, whose comments have helped us improve
the presentation of the paper. We would like to thank Hideaki Sone for hiscooperation in preparing a Japanese draft version at an earlier stage of thiswork. This work was supported in part by JSPS KAKENHI Grant Numbers
JP19J21153 and JP21K11881.

References
1. Abe, Y., Hayashi, Y., Mizuki, T., Sone, H.: Five-card AND computations in committed format using only uniform cyclic shuffles. New Gener. Comput. 39(1), 97–
114 (2021), https://doi.org/10.1007/s00354-020-00110-2

A Card-Minimal Three-Input AND Protocol Using Two Shuffles

11

2. Den Boer, B.: More eﬀicient 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
3. 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
4. Koch, A.: The landscape of optimal card-based protocols. Cryptology ePrint
Archive, Report 2018/951 (2018), https://eprint.iacr.org/2018/951
5. Koch, A.: Cryptographic Protocols from Physical Assumptions. Ph.D. thesis, Karlsruhe Institute of Technology (2019), https://doi.org/10.5445/IR/1000097756
6. Koch, A., Schrempp, M., Kirsten, M.: Card-based cryptography meets formal verification. In: Galbraith, S.D., Moriai, S. (eds.) Advances in Cryptology–ASIACRYPT
2019. LNCS, vol. 11921, pp. 488–517. Springer, Cham (2019), https://doi.org/
10.1007/978-3-030-34578-5_18
7. Koch, A., Schrempp, M., Kirsten, M.: Card-based cryptography meets formal verification. New Gener. Comput. 39(1), 115–158 (2021), https://doi.org/10.1007/
s00354-020-00120-0
8. Koch, A., Walzer, S., Hä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
9. Manabe, Y., Ono, H.: Card-based cryptographic protocols for three-input functions
using private operations. In: Combinatorial Algorithms. LNCS, Springer, Cham
(2021), to appear
10. Miyahara, D., Ueda, I., Hayashi, Y., Mizuki, T., Sone, H.: Evaluating card-based
protocols in terms of execution time. Int. J. Inf. Secur. 20(5), 729–740 (2021),
https://doi.org/10.1007/s10207-020-00525-4
11. 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
12. 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
13. 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
14. Mizuki, T., Shizuya, H.: Computational model of card-based cryptographic protocols and its applications. IEICE Trans. Fundamentals E100.A(1), 3–11 (2017),
https://doi.org/10.1587/transfun.E100.A.3
15. Mizuki, T., Sone, H.: Six-card secure AND and four-card secure XOR. In: Deng,
X., Hopcroft, J.E., Xue, J. (eds.) Frontiers in Algorithmics. LNCS, vol. 5598,
pp. 358–369. Springer, Berlin, Heidelberg (2009), https://doi.org/10.1007/
978-3-642-02270-8_36
16. Nakai, T., Misawa, Y., Tokushige, Y., Iwamoto, M., Ohta, K.: How to solve millionaires’ problem with two kinds of cards. New Gener. Comput. 39(1), 73–96 (2021),
https://doi.org/10.1007/s00354-020-00118-8

12

R. Isuzugawa et al.

17. Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: An implementation of nonuniform shuffle for secure multi-party computation. In: Proceedings of the 3rd ACM
International Workshop on ASIA Public-Key Cryptography. pp. 49–55. AsiaPKC’16, ACM, New York, NY, USA (2016). https://doi.org/10.1145/2898420.2898425,
https://doi.acm.org/10.1145/2898420.2898425
18. Nishimura, A., Nishida, T., Hayashi, Y., Mizuki, T., Sone, H.: Card-based protocols
using unequal division shuffles. Soft Comput. 22(2), 361–371 (2018), https://doi.
org/10.1007/s00500-017-2858-2
19. Ono, H., Manabe, Y.: Eﬀicient card-based cryptographic protocols for the millionaires’ problem using private input operations. In: Asia Joint Conference on
Information Security (AsiaJCIS). pp. 23–28 (2018), https://doi.org/10.1109/
AsiaJCIS.2018.00013
20. Ono, H., Manabe, Y.: Card-based cryptographic protocols with the minimum
number of cards using private operations. In: Zincir-Heywood, N., Bonfante,G., Debbabi, M., Garcia-Alfaro, J. (eds.) Foundations and Practice of Security.
LNCS, vol. 11358, pp. 193–207. Springer, Cham (2019), https://doi.org/10.
1007/978-3-030-18419-3_13
21. Ono, H., Manabe, Y.: Card-based cryptographic protocols with the minimum number of rounds using private operations. In: Pérez-Solà, C., Navarro-Arribas, G.,
Biryukov, A., Garcia-Alfaro, J. (eds.) Data Privacy Management, Cryptocurrencies and Blockchain Technology. LNCS, vol. 11737, pp. 156–173. Springer, Cham(2019), https://doi.org/10.1007/978-3-030-31500-9_10
22. 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
23. Ruangwises, S., Itoh, T.: AND protocols using only uniform shuffles. 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
24. Ruangwises, S., Itoh, T.: Securely computing the n-variable equality function with
2n cards. Theor. Comput. Sci. (2021), https://doi.org/10.1016/j.tcs.2021.
07.007, in press
25. Saito, T., Miyahara, D., Abe, Y., Mizuki, T., Shizuya, H.: How to implement a nonuniform or non-closed shuffle. In: Martín-Vide, C., Vega-Rodríguez, M.A., Yang,
M.S. (eds.) Theory and Practice of Natural Computing. LNCS, vol. 12494, pp. 107–118. Springer, Cham (2020), https://doi.org/10.1007/978-3-030-63000-3_9
26. 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
27. Ueda, I., Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: How to implementa random bisection cut. In: Martín-Vide, C., Mizuki, T., Vega-Rodríguez, M.A.
(eds.) Theory and Practice of Natural Computing. LNCS, vol. 10071, pp. 58–69.
Springer, Cham (2016), https://doi.org/10.1007/978-3-319-49001-4_5
28. Yasunaga, K.: Practical card-based protocol for three-input majority. IEICE
Trans. Fundamentals E103.A(11), 1296–1298 (2020), https://doi.org/10.1587/
transfun.2020EAL2025