Card-Minimal Protocols for Three-Input
Functions with Standard Playing Cards⋆
Rikuo Haga1 , Yuichi Hayashi1,4 , Daiki Miyahara2,4 , and Takaaki
Mizuki3,4
1

Nara Institute of Science and Technology,
8916-5 Takayama, Ikoma, Nara 630-0192, Japan
2
The University of Electro-Communications,
1-5-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan
3
Tohoku University, Aramak-Aza-Aoba, Aoba, Sendai 980-8576, Japan
4
National Institute of Advanced Industrial Science and Technology (AIST),
2-3-26 Aomi, Koto-ku, Tokyo 135-0064, Japan

Abstract. A protocol realizing a secure computation using a deck ofphysical cards is called a card-based cryptographic protocol. Since Niemi
and Renvall first proposed a few protocols using a commercially available deck of playing cards in 1999, several protocols for the two-input
AND and XOR functions have been proposed. By combining these existing protocols, one can construct a protocol for any Boolean function
using a standard deck of playing cards. However, the minimal numbersof cards needed for Boolean functions having more than two inputs havenot been revealed so much. Recently, Koyama et al. developed a cardminimal three-input AND protocol. In this study, by extending Koyama’s
AND protocol, we construct a card-minimal protocol for the three-input
majority function. Furthermore, carrying the idea behind these protocols
further, we provide a generic card-minimal three-input protocol, which
covers many important three-input Boolean functions.
Keywords: Card-based cryptography · Secure computation · Standard
deck of playing cards

1

Introduction

Card-based cryptographic protocols realize a secure computation using a deck ofphysical cards (refer to [5, 25, 37] for surveys). Many researches on card-based
cryptography typically use a two-colored deck of cards whose fronts are red ♡⋆This paper appears in Proceedings of AFRICACRYPT 2022. This version of thecontribution has been accepted for publication, after peer review but is not the
Version of Record and does not reflect post-acceptance improvements, or any
corrections. The Version of Record is available online at: https://doi.org/10.
1007/978-3-031-17433-9_19. 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

R. Haga et al.

or black ♣ and whose backs are indistinguishable ? . The Boolean values are
encoded as follows:(1)♣ ♡ = 0, ♡ ♣ = 1.
When two face-down cards ? ? represent a bit x ∈ {0, 1} according to Eq. (1),
we call them a commitment to x and denote it as follows:

??.
|{z}
x

Given commitments as input, a committed-format protocol produces a commitment to the output value of some predetermined function. For example, the(two-input) AND protocol designed in [26] produces a commitment to a ∧ b via
a series of actions, given two commitments to a, b ∈ {0, 1} and two helping cards
as input:? ? ? ? ♣ ♡ → · · · → ♣ ♡ |{z}? ? ? ? or ♡ ♣ ? ? |{z}??.

|{z} |{z}
a

1.1

b

a∧b

a∧b

Card-Based Protocols with a Standard Deck of Cards

The protocols using a two-colored deck of cards cannot be implemented with asingle standard deck of commercially available playing cards. The reason is thatsuch playing cards contain numbers (such as A, 2, 3, 4, . . . , J, Q, K) in addition tosuits (♣, ♡, ♠, ♢), i.e., all the cards are distinct. Therefore, we need to prepare
either multiple decks of playing cards or a tailor-made deck of cards to implement
the protocols.
Fortunately, Niemi and Renvall [30] solved this problem by constructing a few
protocols using a single standard deck of commercially available playing cards.
They regarded a deck of playing cards as a total order on natural numbers from
1 to 52 because there are 52 combinations of numbers and suits in playing cards(excluding the joker); we denote these cards by 1 2 3 · · · 52 . In their protocols,a bit x ∈ {0, 1} is encoded using i and j satisfying 1 ≤ i < j ≤ 52, as follows:
i j = 0,j i = 1.

(2)

That is, if the number on the left card is smaller, it represents 0, and if thenumber on the left card is larger, it represents 1. Thus, similar to the twocolored-deck case (as defined in Eq. (1)), using two cards i and j (of different
numbers), we can create a commitment to x ∈ {0, 1}, denoted by

?? ,
|{z}

[x]{i,j}where the set {i, j} is called the base of the commitment. (We sometimes omit
the description of the base.) For example,

??
|{z}

[x]{1,4}

Card-minimal Three-Input Protocols with Standard Playing Cards

3

Table 1. Existing protocols for Boolean functions using standard playing cards
Protocol# of cards# of shuffles

finite?

2-AND

5
8
4

7.5 (exp.)
4
6 (exp.)✓4
47 (exp.)1

68.5 (exp.)

2-XOR
3-AND

✓

Authors
Niemi & Renvall [30]Mizuki [22]Koch et al. [6]Niemi & Renvall [30]Mizuki [22]Koyama et al. [12]is a commitment to x of base {1, 4}; if x = 0, the order of the sequence is 1 4 ,and if x = 1, it is 4 1 .
1.2

Existing Protocols

Including the Niemi–Renvall protocols mentioned above, there are several existing protocols (working on a standard deck) in the literature, as shown in Table 1.
In this subsection, we briefly review these protocols one by one.
Throughout the paper, ‘2-AND,’ ‘2-XOR,’ and ‘3-AND’ mean the two-input
AND, two-input XOR, and three-input AND functions, respectively; we also use
similar notations for other functions. In addition, when simply writing ‘AND
protocol’ or ‘XOR protocol,’ it means a two-input protocol, i.e., a 2-AND protocol or 2-XOR protocol.
Two-Input AND and XOR. As mentioned in Sect. 1.1, Niemi and Renvall [30] proposed the first protocols working on a standard deck. Specifically,
they constructed a protocol for the two-input AND function (namely, 2-AND)using five cards:? ? ? ? 5 → ··· →?? .

|{z} |{z}|{z}[a]{1,2} [b]{3,4}[a∧b]{1,4}Therefore, aside from the two input commitments to a, b ∈ {0, 1}, this AND
protocol uses one helping card, namely 5 . The protocol (with the slight modification by Koch et al. [6]) uses 7.5 shuffles in expectation; thus, it is a Las
Vegas protocol (and it is not a finite-runtime protocol). See the first protocol
listed in Table 1. We call this the Niemi–Renvall AND protocol, whose detailed
explanation will be shown in Sect. 2.4.
Niemi and Renvall [30] also constructed a 2-XOR protocol with four cards:?? ??
|{z} |{z}[a]{1,2} [b]{3,4}→ ··· →?? .
|{z}[a⊕b]{1,2}

Because the two input commitments need four cards as long as we follow theencoding rule in Eq. (2), this XOR protocol, which does not use any helping

4

R. Haga et al.

card, is card-minimal 5 . As shown in Table 1, the protocol uses seven shuffles in
expectation.
In 2016, Mizuki [22] proposed AND and XOR protocols with eight and four
cards, respectively:? ? ? ? 5 6 7 8 → ··· →??

|{z} |{z}|{z}[a]{1,2} [b]{3,4}or[a∧b]{5,6}

??
|{z}

[a∧b]{7,8}

and

?? ??

→ ··· →|{z} |{z}

?? .
|{z}

[a]{1,2} [b]{3,4}[a⊕b]{3,4}

The AND and XOR protocols use four and one shuffles, respectively, and boththe protocols are finite-runtime; see Table 1. While the XOR protocol is cardminimal, the AND protocol needs four helping cards.
As seen thus far, there had been card-minimal XOR protocols, whereas nocard-minimal AND protocol had been found until 2019: Koch et al. [6] constructed a card-minimal AND protocol in 2019:?? ??

→ ··· →|{z} |{z}

??.
|{z}

[a]{1,2} [b]{3,4}a∧bAs seen in Table 1, this is a Las Vegas protocol, which uses six shuffles in expectation.
Three-Input AND. If we execute the above-mentioned card-minimal 2-AND
protocol designed by Koch et al. [6] twice, we can securely compute 3-AND
without any helping card, although it needs 12 shuffles in expectation.
In 2021, Koyama et al. [12] improved upon this by nicely making use of theNiemi–Renvall AND protocol. That is, they proposed a card-minimal 3-AND
protocol with 8.5 shuffles (in expectation):?? ?? ??
|{z} |{z} |{z}[a]{1,2} [b]{3,4} [c]{5,6}→ ··· →

??

.

|{z}

[a∧b∧c]{1,4}Hereinafter, we call this protocol Koyama’s AND protocol.
Thus, there have already been card-minimal protocols for 3-AND. In addition, one can easily construct a card-minimal 3-XOR protocol by executing oneof the existing 2-XOR protocols twice. However, aside from 2-AND and 2-XOR,
there are many other three-input Boolean functions, and it is open to determine
whether all the three-input Boolean functions can be securely computed without
any helping card.
5This paper (and the literature) assume the encoding (2), i.e., a two-card-per-bit encoding, when discussing the card-minimality of protocols; thus, an n-input (Booleanfunction) protocol always needs 2n cards for input commitments, and such a protocol
using only 2n cards is card-minimal.

Card-minimal Three-Input Protocols with Standard Playing Cards

5

For example, the three-input majority function maj : {0, 1}3 → {0, 1} definedas(
0 if a + b + c ≤ 1,
maj(a, b, c) =1 if a + b + c ≥ 2
can be securely computed by combining the existing protocols (including the“copy” protocols, which will be mentioned in Sect. 1.4), because it suffices toapply AND, OR, and copy protocols by following a circuit such as
maj(a, b, c) = (a ∧ b) ∨ (b ∧ c) ∨ (c ∧ a).
Note that a 2-OR protocol is obtained immediately by a 2-AND protocol withDe Morgan’s laws, or we will directly display a 2-OR protocol in Sect. 3.1.
When following the circuit for 3-majority above, we need to duplicate some
input commitments, and hence, we need some helping cards, implying that sucha construction is not card-minimal. Thus, designing card-minimal protocols forthree-input Boolean functions (including 3-majority) is considered to be nontrivial.
1.3

Contribution

In this study, we focus on designing card-minimal protocols for three-input
Boolean functions by extending the idea behind Koyama’s AND protocol [12]further. Specifically, the contribution of this paper is twofold:– For the three-input majority function, we construct a protocol using six
cards, i.e., we design a card-minimal 3-majority protocol:?? ?? ??
|{z} |{z} |{z}[a]{1,2} [b]{3,4} [c]{5,6}

→

···

→

??

.

|{z}

[maj(a,b,c)]{1,4}

As will be explained, our protocol is based on Koyama’s AND protocol [12],and uses the same number of shuffles, namely 8.5 shuffles (in expectation).
Note that the 3-majority is one of the most important three-input Booleanfunctions in terms of practical use.
– We generalize the idea behind Koyama’s AND protocol so that we obtain ageneric card-minimal three-input protocol, which accommodates many threeinput Boolean functions (namely, 140 functions), including important functions such as 3-OR, 3-XOR, 3-NAND, 3-NOR, 3-XNOR, and the 3-minority.
1.4

Related Work

Aside from the existing AND and XOR protocols introduced in Sect. 1.2, there
are “copy” protocols working on a standard deck [13, 22, 30]. A copy protocol
duplicates a commitment without revealing any information about the valueof the commitment. Using such a copy protocol as well as 2-AND, 2-XOR, and6

R. Haga et al.

NOT protocols6 , we can construct a protocol for any Boolean function. However,determining whether there exist card-minimal protocols for multi-input functions
remains an open problem (except the n-AND and n-XOR functions).
There are also attractive applications using a standard deck of cards: zeroknowledge proof protocols for Sudoku [34] and millionaire protocols [18]. Moreover, under another computation model which accepts “private operations” suchas revealing a card behind player’s back, card-minimal AND, XOR, and copy
protocols were constructed [16].
As mentioned at the beginning of this section, many card-based protocols
work on a two-color deck of cards; under several kinds of settings of decks(including the standard-deck and two-color-deck settings), the research area
on card-based cryptography has grown rapidly recently from both theoreticaland practical aspects. Examples are: constructing zero-knowledge proof protocols [15, 32, 33, 35], investigating computation models [3, 9, 23, 39] and shuffles [8,21,36], designing private-operation-model protocols [1,17,28,29,31], seeking practical and/or efficient protocols [2, 7, 14, 20, 40], and making use of otherphysical objects [4, 11, 19, 27, 38].

1.5

OutlineIn Sect. 2, we introduce operations used in card-based cryptography and describe
the existing protocol [30] and technique [12]. In Sect. 3, we show how to constructa three-input majority protocol by extending the ideas behind the Niemi–Renvall
AND protocol and Koyama’s AND protocol. In Sect. 4, we construct a generic
protocol which covers many three-input Boolean functions by generalizing theideas further. Section 5 summarizes our study.

2

Preliminaries

In this section, we introduce the description of operations formalized in thecomputational model of card-based cryptography [24]. We also introduce the twopractical shuffles called the “random cut” and “random bisection cut.” Finally,
we describe the Niemi–Renvall AND protocol [30] and the useful technique [12]called the “swap operation by commitment value.”

2.1

Operations

We here introduce three operations, namely rearrangement, turn, and shuffle. We
assume that we have a sequence of n face-down cards for some natural numbern (≥ 2).
6

A NOT protocol can be simply constructed: swapping two cards comprising a commitment produces a commitment to the negation.

Card-minimal Three-Input Protocols with Standard Playing Cards

7

Rearrangement. This applies some permutation π ∈ Sn to the sequence, where
Sn denotes the symmetric group of degree n. This is written as (perm, π), andthe sequence changes as follows:1 2n? ? ··· ?

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

π −1 (n)

? ···

?

.

?

Turn. This reveals the t-th card from the left in the sequence to check its number.
This is written as (turn, {t}), and the sequence changes as follows (for example):
1 2

t

n

? ? ··· ? ··· ?

1 2(turn,{t})−−−−−−→tn? ? ··· 7 ··· ? .

Shuffle. This applies a permutation π drawn from a permutation set Π ⊆ Sn
according to a probability distribution F on Π. This is written as (shuf, Π, F),
and the sequence changes as follows:1 2n? ? ··· ?

π −1 (1) π −1 (2)(shuf,Π, F )−−−−−−−→?

?

π −1 (n)···?

for π ← F.

Note that no one learns which permutation in Π was applied. If F is uniform,
then we simply write it as (shuf, Π).
2.2

Random Cut

A random cut, denoted by ⟨ · ⟩, is an operation that shuffles a sequence by cyclically shifting it. Applying a random cut to a sequence of n cards results in oneof n possibilities, each occurring with a probability of 1/n:

D 1 2

n−1 n E? ? ··· ? ?

→

 1 2
n−1 n


 ? ? ··· ? ?



 2 3
n 1



··· ? ?

 ??
..
.



n−3 n−2
n−1 n



·
·
·
?
?
? ?




n 1
n−2 n−1
? ? ··· ? ?

(1/n),(1/n),(1/n),(1/n).

Thus, this operation can be written as (shuf, ⟨(1 2 · · · n)⟩), where ⟨(i1 i2 · · · iℓ )⟩denotes the cyclic group generated by a (cyclic) permutation (i1 i2 · · · iℓ ).
2.3

Random Bisection Cut (RBC)

A random bisection cut (RBC) [26], denoted by [ · | · ], is a shuffling operation,
which bisects a sequence of cards and then randomly swaps the two halves. Thus,
when an RBC is applied to a sequence of 2n cards, the sequence becomes either

8

R. Haga et al.

the original one, or the one in which the first n cards are swapped with the lastn cards, as follows:h 1n? ··· ?

n+1

2n i

? ··· ?

→

1n

 ? ··· ?
n+1
2n


···

?

?

n+1

2n

? · · · ? (1/2),
1n? ··· ?

(1/2).

This operation can be written as (shuf, {id, (1 n+1)(2 n+2) · · · (n 2n)}), where
id denotes the identity permutation.

2.4

The Niemi–Renvall AND Protocol

The Niemi–Renvall AND protocol [30] takes as input two commitments to a, b ∈{0, 1} as well as an additional card and outputs a commitment to a ∧ b. This
protocol proceeds as follows.
1. Place the two input commitments and the additional card 5 as follows, andturn over the face-up card:
5

→

?? ??
|{z} |{z}[a]{1,2} [b]{3,4}? |{z}? ? |{z}?? .
[a]{1,2} [b]{3,4}

2. Swap the third and fourth cards:
1 2 3 4 5

1 2 4 3 5

→

?????

?????.

The initial and swapped sequences for each input are described in the thirdand fourth columns of Table 2. Observe that the order of 1 , 4 , and 5 inthe swapped sequence is 5 → 4 → 1 if and only if a ∧ b = 1. Therefore, we
try to remove the two cards 2 and 3 in the next steps.
3. Apply a random cut to the sequence:
D

?????

E

→

? ? ? ? ?.

4. Turn over the first card. Remove the revealed card if it is either 2 or 3 ;otherwise, turn the card face down. Return to Step 3 unless both 2 and 3
are already removed.
5. Now, the sequence is one of the three possibilities as described in the fifth
column of Table 2. Apply a random cut to the sequence again and then turnover the first card. We can obtain a commitment to a ∧ b (as output), asCard-minimal Three-Input Protocols with Standard Playing Cards

9

Table 2. The sequence of five cards for each input during the Niemi–Renvall protocol
Input (a, b)

a∧b

InitialAfter swap

2 and 3 removed(0, 0)

0

5 1 2 3 4

5 1 3 2 4

1 4 5 or 4 5 1 or 5 1 4(0, 1)

0

5 1 2 4 3

5 1 4 2 3

1 4 5 or 4 5 1 or 5 1 4(1, 0)

0

5 2 1 3 4

5 2 3 1 4

1 4 5 or 4 5 1 or 5 1 4(1, 1)

1

5 2 1 4 3

5 2 4 1 3

1 5 4 or 4 1 5 or 5 4 1

follows:7

D

???

E

→



1 ??


|{z}



 [a∧b]{4,5} 4(turn,{1})??
|{z}? ? ? −−−−−−→ [a∧b]{1,5}




5 ??


|{z}



(1/3),(1/3),(1/3).

[a∧b]{1,4}

If the first card is 4 , then we obtain a commitment to the negation of a ∧ b;
we can obtain a commitment to a ∧ b by swapping the two cards comprising
the commitment.
The correctness of this protocol is clear from Table 2. In addition, no information
about the input and output is leaked when a card is turned over because wealways apply a random cut before turning over a card.
2.5

Swapping by Commitment Value

Koyama et al. [12] proposed a sub-protocol called the swapping by commitment
value based on the idea of behind the two-input XOR protocol [22] proposedby Mizuki. This led to the construction of the 3-AND protocol [12]. Given twotarget cards ? ? and a commitment to c ∈ {0, 1} of base {i, j}, the swappingby commitment value is to swap the two cards ? ? if and only if c = 1, without
leaking any information about the value of c as follows:

1 2


1 2
? ? if c = 0,
? ? |{z}? ? → 2 1

? ? if c = 1.
[c]{i,j}The procedure is shown below.
1. Place the two target cards and the commitment to c as follows:? ? |{z}?? .
[c]{i,j}7

This step was proposed by Koch et al. [6], reducing the number of shuffles.

10

R. Haga et al.

2. Swap the second and third cards, i.e., apply (perm, (2 3)).
3. Apply (shuf, {id, (1 3)(2 4)}) , i.e., apply an RBC as follows:ih? ? ? ? → ? ? ? ?.
4. Apply (perm, (2 3)) again. Then, the sequence becomes one of the following
two possibilities depending on the value of c:

1 2


? ? i j (1/2),
c=0→ 2 1? ? j i (1/2).

1 2


? ? j i (1/2),
c=1→ 2 1? ? i j (1/2).
Observe that the order of the first and second cards are desirable if the orderof i and j is i j .
5. Turn over the third and fourth cards to reveal the order of i and j .
(a) If i j appears, then output the first and second cards.
(b) If j i appears, then swap the first and second cards and output them.
Thus, the above sub-protocol achieves the desired functionality without leaking
any information about c.

3

Three-input Majority Protocol

In this section, we construct a card-minimal protocol for the three-input majority
function maj(a, b, c) working on a standard deck. The idea behind our proposed
protocol is based on the Niemi–Renvall AND protocol [30] and Koyama’s AND
protocol [12].
To construct a 3-majority protocol, we utilize the following equation:(a ∧ b if c = 0,maj(a, b, c) =(3)a ∨ b if c = 1.
To compute maj(a, b, c), observe that, if c = 0, it suffices to compute a ∧ b using
the Niemi–Renvall AND protocol introduced in Sect. 2.4; otherwise, we want tocompute a ∨ b. Therefore, we first construct an OR protocol by modifying theNiemi–Renvall protocol and then construct a 3-majority protocol.
3.1

Two-Input OR Protocol

We construct a two-input OR protocol by changing the rearrangement positionsin the Niemi–Renvall AND protocol. The protocol takes as input two commitments to a, b as well as an additional card and outputs a commitment to a ∨ b,
as follows.

Card-minimal Three-Input Protocols with Standard Playing Cards

11

Table 3. The sequence of five cards for each input during the 2-OR protocol
Input(a, b) a ∨ b

InitialRearranged (Step 2)

Removing 2 and 3(0, 0)

0

5 1 2 3 4

5 3 1 4 2

1 4 5 or 4 5 1 or 5 1 4(0, 1)

1

5 1 2 4 3

5 4 1 3 2

1 5 4 or 4 1 5 or 5 4 1(1, 0)

1

5 2 1 3 4

5 3 2 4 1

1 5 4 or 4 1 5 or 5 4 1(1, 1)

1

5 2 1 4 3

5 4 2 3 1

1 5 4 or 4 1 5 or 5 4 1

1. Place the two input commitments and the additional card 5 and turn it overas follows:→ ? ?? ??.
5 ?? ??
|{z} |{z}|{z} |{z}a[a]{1,2} [b]{3,4}b

2. Rearrange the sequence as follows, i.e., apply (perm, (2 3 5 4)):1 2 3 4 5?????

1 4 2 5 3→?????.

The input and rearranged sequences for each input are described in the thirdand fourth columns of Table 3. Observe that the order of 1 , 4 , and 5 in
the rearranged sequence is 5 → 4 → 1 if and only if a ∨ b = 1.
3. Apply Steps 3, 4, and 5 of the Niemi–Renvall AND protocol shown in
Sect. 2.4 to obtain a commitment to a ∨ b.
3.2

Idea

Remember that in Step 2 of the Niemi–Renvall AND protocol and our OR protocol, we rearrange the sequence of cards, i.e., the AND protocol uses (perm, (3 4))
and the OR protocol uses (perm, (2 3 5 4)).
Observe that if we apply (perm, (3 4)), namely
1 2 3 4 5?????

1 2 4 3 5→

? ? ? ? ?,→? ? ? ? ?,and apply (perm, (2 3)(4 5)), namely
1 2 3 4 5?????

1 3 2 5 4

the resulting sequence becomes the same as the one after executing Step 2 of
our OR protocol. In other words, ((2 3)(4 5))(3 4) = (2 3 5 4).
Therefore, after applying (perm, (3 4)), if we do nothing, it results in the AND
protocol. If we apply (perm, (2 3)(4 5)) after applying (perm, (3 4)), it resultsin the OR protocol. Therefore, it suffices to perform the swap operation bycommitment value [12] introduced in Sect. 2.5 to apply (perm, (2 3)(4 5)) if andonly if c = 1 (see Eq. (3) again).

12

3.3

R. Haga et al.

Description of Protocol

We are ready to describe the procedure for our 3-majority protocol. The protocol takes three commitments to a, b, c as input and outputs a commitment tomaj(a, b, c).
1. Place three input commitments as follows:?? ?? ?? .
|{z} |{z} |{z}[a]{1,2} [b]{3,4} [c]{5,6}

2. Swap the second and the third cards:
1 2 3 4 5 6??????

1 3 2 4 5 6→??????.

3. Apply the swap operation by the commitment to c [12] to apply (perm, (1 2)(3 4))
if and only if c = 1 as follows:(a) Rearrange the sequence as follows:
1 2 3 4 5 6??????

1 3 5 2 4 6→??????.

(b) Apply (shuf, {id, (1 4)(2 5)(3 6)}) , i.e., apply an RBC as follows:hi? ? ? ? ? ? → ? ? ? ? ? ?.
(c) Rearrange the sequence as follows:
1 2 3 4 5 6??????

1 4 2 5 3 6→??????.

(d) Turn over the fifth and sixth cards. If their order is 5 6 , do nothing;if it is 6 5 , swap the first and second cards as well as the third andfourth cards. The sequence for each input is described in Table 4 where
the order of the revealed two cards 5 6 does not matter.
4. Execute Steps 3, 4, and 5 of the Niemi–Renvall AND protocol to obtain acommitment to maj(a, b, c), where we use the first through fourth cards as
input, and the 5 turned over in Step 3d as an additional card (i.e., place the
5 in the first from the left).

3.4

Correctness and Security

The correctness of this protocol is clear from Table 4 because when the input(a, b, c) satisfies maj(a, b, c) = 0, the resulting sequence after Step 3 is 1 4 5(where 2 , 3 , and 6 are removed); otherwise, the sequence is 4 1 5 . As forthe security, we execute the swap operation by commitment value [12] in Step 3
and then the part of the Niemi–Renvall AND protocol (and Steps 1 and 2 just

Card-minimal Three-Input Protocols with Standard Playing Cards

13

Table 4. The sequence of six cards for each input in our 3-majority protocol, where
the sequences in the fourth column are in a case when the order of the revealed fifthand sixth cards are 5 6 in Step 3d.
Input(a, b, c) maj(a, b, c)

InitialAfter Swap (Step 3d) Removing 2 3 6(0, 0, 0)0

1 2 3 4 5 6

1 3 2 4 5 61 4 5(0, 0, 1)0

1 2 3 4 6 5

3 1 4 2 5 6

1 4 5(0, 1, 0)0

1 2 4 3 5 6

1 4 2 3 5 61 4 5(0, 1, 1)1

1 2 4 3 6 5

4 1 3 2 5 6

4 1 5(1, 0, 0)0

2 1 3 4 5 6

2 3 1 4 5 6

1 4 5(1, 0, 1)1

2 1 3 4 6 5

3 2 4 1 5 6

4 1 5(1, 1, 0)1

2 1 4 3 5 6

2 4 1 3 5 6

4 1 5(1, 1, 1)1

2 1 4 3 6 5

4 2 3 1 5 6

4 1 5

place and swap the sequence, respectively), no information about the input andoutput is leaked.
More formally, we use the KWH-tree [10] to prove the security (and correctness) of this protocol; we depict the KWH-tree of our three-input majority
protocol in Fig. 1. In the diagram, states of a sequence of cards are expressed as
nodes, and operations on the sequence of cards are expressed as edges. Because
the sum of the probability distributions of the nodes is equal to the probability
distribution of the input, the protocol is guaranteed to be secure.

4

Generic Protocol for Three-Input Functions

In this section, we generalize our 3-majority protocol described in Sect. 3 so as
to obtain a generic card-minimal protocol for three-input Boolean functions.
After we describe the idea behind the generalization in Sect. 4.1, we generalize the Niemi–Renvall AND protocol and the swap operation by commitment
value [12] in Sects 4.2 and 4.3, respectively.
Before going into the subsections, we define a notation; hereinafter, πijkℓdenotes a permutation in S4 such that1234
πijkl =
ijkℓ
for four distinct integers i, j, k, ℓ ∈ {1, 2, 3, 4}. For example, π1234 = id and
π1324 = (2 3).
4.1

Idea

Our idea is that, as maj(a, b, c) is represented with the two elementary functionsof a and b depending on the value of c (as in Eq. (3)), every three-input Boolean

14

R. Haga et al.

Fig. 1. The KWH-tree of three-input majority protocol

Card-minimal Three-Input Protocols with Standard Playing Cards

function f : {0, 1}3 → {0, 1} can be also written as follows:(g(a, b) if c = 1,
f (a, b, c) =h(a, b) if c = 0,

15

(4)

where there exist two functions g, h : {0, 1}2 → {0, 1}.
Remember that in our 3-majority protocol proposed in Sect. 3, we first apply
the permutation π1324 (to compute 2-AND) and then, if c = 1, apply the permutation π2143 by the swap operation (to compute 2-OR); π1324 leads to 2-AND,and π2143 π1324 leads to 2-OR. If we replace these two permutations with otherones, then we will obtain (possibly) another three-input protocol.
Bearing this in mind, we first investigate what two-input function (as a candidate for g or h in Eq. (4)) will be computed for every permutation πijkℓ ∈ S4
(in Sect. 4.2). Then, we enumerate all possible swap operations (in Sect. 4.3).
4.2

Generalizing the Niemi–Renvall AND Protocol

In this subsection, we generalize the Niemi–Renvall AND protocol by considering
all permutations for Step 2 of the protocol.
Assume that we apply a permutation π ∈ S4 (instead of the original permutation) in Step 2 of the Niemi–Renvall AND protocol. Then, at the end of the
protocol, we should obtain a commitment to a certain two-input function; wedenote this function by NRπ : {0, 1}2 → {0, 1}.
We examined all 4! possibilities for π and write NRπ (a, b) in Table 5. This
table tells us that aside from 2-XOR and 2-XNOR, all two-input functions canbe obtained.
4.3

Generalizing Swap Operation by Commitment ValueIn this subsection, consider all possible swapping operations.
Assume that we have four cards along with a commitment to c ∈ {0, 1} ofbase {5, 6}:? ? ? ? |{z}?? .
[c]{5,6}

We want to apply a permutation in S4 to the first four cards if and only if
c = 1. What are the possible permutations? We can consider two kind of swap
operations.
(i j)-swap. Remember that the swap operation introduced in Sect. 2.5 swaps
two cards (or does not) depending on the value of c. As a natural extension,
let us consider a swap operation such that the i-th and j-th cards (among theleftmost four cards) for 1 ≤ i < j ≤ 4 are swapped or not; we call this the(i j)-swap, which can be achieved as follows.
1. Apply the permutation corresponding to (i j) according to Table 6.

16

R. Haga et al.
Table 5. Output NRπ of the generalized Niemi–Renvall protocol with π
Permutation ππ1234 , π1243 , π2134 , π2143
π1324
π1423
π1342 , π1432
π2314
π3124 , π3214
N/A
π3142
π2413
N/A
π4123 , π4213
π4132
π2341 , π2431
π3241
π4231
π3412 , π3421 , π4312 , π4321

NRπ (a, b)
0a∧ba ∧ b̄
aā ∧ b
b
a⊕b
a∨b
a∨b
a⊕b
b̄
a ∨ b̄āā ∨ ba∧b
1

2. Apply (shuf, {id, (3 5)(4 6)}) , i.e., apply an RBC as follows:hi? ? ? ? ? ? → ? ? ? ? ? ?.
3. Apply the inverse of the permutation applied in Step 1.
4. Turn over the fifth and sixth cards (namely, apply (turn, {5, 6})). If the order of the revealed cards are 6 5 , swap the i-th and j-th cards (namely,(perm, (i j))); otherwise, do nothing.
(i j)(k ℓ)-swap. Remember that our 3-majority protocol uses (perm, (2 3)(4 5))in the swap operation, and note that the permutations (2 3) and (4 5) aredisjoint. Therefore, we can consider a swap operation such that the i-th and j-thcards as well as the k-th and ℓ-th cards are swapped or not for 1 ≤ i < j ≤ 4and {k, ℓ} = {1, 2, 3, 4} − {i, j}; we call this the (i j)(k ℓ)-swap, which can beachieved as follows.
1. Apply the permutation corresponding to (i j)(k ℓ) according to Table 7.
2. Apply (shuf, {id, (1 4)(2 5)(3 6)}), i.e., apply an RBC as follows:hi? ? ? ? ? ? → ? ? ? ? ? ?.
3. Apply the inverse of the permutation applied in Step 1.
4. Turn over the fifth and sixth cards (namely, apply (turn, {5, 6})). If the orderof the revealed cards are 6 5 , swap the i-th and j-th cards as well as k-th
and ℓ-th cards (namely, (perm, (i j)(k ℓ))); otherwise, do nothing.

Card-minimal Three-Input Protocols with Standard Playing Cards

17

Table 6. Actions for Steps 1 and 3 of the (i j)-swap(i j)Action for Step 1

Action for Step 3 (Inverse of Step 1)

(1 2)
(1 3)
(1 4)
(2 3)
(2 4)
(3 4)

(perm, (1 3)(2 5 4))(perm, (1 3 5 4 2))(perm, (1 3 2)(4 5))(perm, (2 3 5 4))(perm, (2 3)(4 5))(perm, (4 5))(perm, (1 3)(2 4 5))(perm, (1 2 4 5 3))(perm, (1 2 3)(4 5))(perm, (2 4 5 3))(perm, (2 3)(4 5))(perm, (4 5))

Table 7. Actions for Steps 1 and 3 of the (i j)(k ℓ)-swap

4.4(i j)(k ℓ)Action for Step 1

Action for Step 3 (Inverse of Step 1)(1 2)(3 4)(1 3)(2 4)(1 4)(2 3)(perm, (2 4 5 3))(perm, (3 4 5))(perm, (3 5))(perm, (2 3 5 4))(perm, (3 5 4))(perm, (3 5))

Description of Protocol

We are now ready to describe our generic protocol for three-input Boolean function.
Our protocol owns two permutations π, σ ∈ S4 as parameter, where either
σ = (i j) for 1 ≤ i < j ≤ 4, or σ = (i j)(k ℓ) for 1 ≤ i < j ≤ 4 and{k, ℓ} = {1, 2, 3, 4} − {i, j}; it proceeds as follows.
1. Place three input commitments as:?? ?? ?? .
|{z} |{z} |{z}[a]{1,2} [b]{3,4} [c]{5,6}

2. Apply (perm, π).
3. Apply σ-swap.
4. Apply Steps 3, 4, and 5 of the Niemi–Renvall AND protocol.
4.5

Covered Functions

In this subsection, we comprehensively reveal what three-input functions ourgeneric protocol computes.
Executing our generic protocol with parameter π, σ ∈ S4 is equivalent toexecuting a protocol for the three-input Boolean function f such that(
NRσπ (a, b) if c = 1,
f (a, b, c) =NRπ (a, b) if c = 0.
For example, if we take π, σ as in the first and second columns of Table 8,
we have NRπ and NRσπ as in the fourth and fifth columns, and hence, the18

R. Haga et al.
Table 8. Covered main functions
π

σ

σπ

NRπ

NRσπ

f (a, b, c)

π1234
π3412
π3412
π4321
π2413
π2413
π1324
π2413

(2 3)
(2 3)
(1 4)(2 3)
(2 3)
(2 3)
(1 3)(2 4)(1 2)(3 4)(1 2)(3 4)

π1324
π3142
π2143
π4231
π2143
π1324
π3142
π4231

AND
1
NAND
NAND
0
AND
OR
NOR

0
OR
OR
1
NOR
NOR
AND
NAND

3-AND [12]
3-OR
3-XOR
3-NAND
3-NOR
3-XNOR
3-majority
3-minority

corresponding three-input Boolean functions are shown in the sixth column.
This table tells us that major three-input Boolean functions are covered by ourgeneric protocol.
From the user’s perspective, given a three-input function f , we want to findtwo permutations π, σ ∈ S4 which lead to f . Table 9 helps us: We first find g, hsuch that(g(a, b) if c = 1,
f (a, b, c) =h(a, b) if c = 0;
then, using Table 9, find the corresponding parameter π, σ.
Although not all three-input Boolean functions have a corresponding parameter π, σ, our generic protocol covers 140 three-input Boolean functions amongthe 256 ones.

5

Conclusion

In this study, we showed how to construct a card-minimal 3-majority protocol
by extending the Niemi–Renvall AND protocol [30] and Koyama’s AND protocol [12]. Furthermore, we constructed a generic card-minimal protocol thatcovers many three-input Boolean functions as shown in Table 9.
Although the proposed protocol accommodates many major functions as seenin Table 8, not all the three-input Boolean functions can be computed by it. It is
open to determine whether there exists a six-card protocol for every three-input
Boolean function. While 3-XOR and 3-XNOR can be computed without any
helping card by using the existing protocols, we conjecture that some functions,say(a ∧ b if c = 1,
f (a, b, c) =a ⊕ b if c = 0,
would need helping cards.

Card-minimal Three-Input Protocols with Standard Playing Cards

19

Table 9. Parameter π, σ leading to g, h
g

0

a∧b

a∧b

a

a∧b

b

a⊕b

a∨b

a∨b

a⊕b

b

a∨b

a

a∨b

a∧b

1

0

π1234
(3 4)

π1234
(2 3)

π1243
(2 3)

π1234
(2 4)

π2134
(2 3)

π1234
(1 3)

N/A

π2143
(1 4)

π2143
(2 3)

N/A

π2143
(1 3)

π2134
(1 4)

π2143
(2 4)

π1243
(1 4)

π1234
(1 4)

π2143
(1 4)(2 3)

a∧b

π1324
(2 3)

N/A

π1324
(2 4)

π1324
(3 4)

π1324
(1 3)

π1324
(1 2)

N/A

π1324
π1324 N/A
(1 2)(3 4) (1 3)(2 4)

N/A

N/A

N/A

N/A

π1324
(1 4)(2 3)

π1324
(1 4)

a∧b

π1423
(2 3)

π1423
(2 4)

N/A

π1423
(3 4)

π1423
(1 3)(2 4)

N/A

N/A

N/A

π1423
(1 3)

N/A

π1423
(1 2)

π1423
(1 2)(3 4)

N/A

π1423
(1 4)(2 3)

N/A

π1423
(1 4)

a

π1342
(2 4)

π1342
(3 4)

π1432
(3 4)

π1432
(2 3)

N/A

π1342 N/A
(1 2)(3 4)

π1342
(1 2)

N/A

N/A

π1342
(1 3)(2 4)

π1432
(1 2)

π1432
(1 4)(2 3)

N/A

N/A

π1432
(1 3)

a∧b

π2314
(2 3)

π2314
(1 3)

π2314
(1 3)(2 4)

N/A

N/A

π2314
(1 2)

N/A

N/A

π2314
(2 4)

N/A

N/A

π2314
(1 4)(2 3)

π2314
(3 4)

π2314
(1 2)(3 4)

N/A

π2314
(1 4)

b

π3124
(1 3)

π3124
(1 2)

N/A

π3124
(1 2)(3 4)

π3214
(1 2)

π3124
(2 3)

N/A

π3124
(3 4)

N/A

N/A

π3214
(1 4)(2 3)

N/A

π3214
(1 2)(3 4)

π3214
(3 4)

N/A

π3124
(2 4)

a⊕b

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

a∨b

π3142
(1 4)

π3142
(1 2)(3 4)

N/A

π3142
(1 2)

N/A

π3142
(3 4)

N/A

N/A

π3142 N/A
(1 4)(2 3)

N/A

π3142
(1 3)

N/A

π3142
(2 4)

π3142
(1 3)(2 4)

π3142
(2 3)

a∨b

π2413
(2 3)

π2413
(1 3)(2 4)

π2413
(1 3)

N/A

π2413
(1 4)

N/A

N/A

π2413
(1 4)(2 3)

π2413
(1 2)

N/A

π2413
(3 4)

N/A

π2413
(1 2)(3 4)

π2413
(1 4)

h

N/A

N/A

a⊕b

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

N/A

b

π4123
(1 3)

N/A

π4123
(1 2)

π4213
(1 3)(2 4)

N/A

π4123
(1 4)

N/A

N/A

π4213
(1 2)

N/A

π4123
(2 3)

π4123
(3 4)

π4123
(1 3)(2 4)

N/A

π4213
(3 4)

π4123
(2 4)

a∨b

π4132
(1 4)

N/A

π4132
(1 2)(3 4)

π4132
(1 2)

π4132
(1 4)(2 3)

N/A

N/A

π4132
(1 3)

N/A

N/A

π4132
(3 4)

N/A

N/A

π4132
(1 3)(2 4)

π4132
(2 4)

π4132
(2 3)

a

π2341
(2 4)

N/A

N/A

π2341
(1 4)

π2341
(3 4)

π2341 N/A
(1 2)(3 4)

N/A

π2431
(3 4)

N/A

π2341
(1 3)(2 4)

N/A

π2341
(2 3)

π2341
(1 2)

π2431
(1 2)

π2431
(1 3)

a∨b

π3241
(1 4)

N/A

π3241
(1 4)(2 3)

N/A

π3241
(1 2)(3 4)

π3241
(2 4)

N/A

N/A

N/A

π3241
(1 3)(2 4)

π3241
(1 2)

N/A

π3241
(1 3)

π3241
(2 3)

a∧b

π4231
(1 4)

π4231
(1 4)(2 3)

N/A

N/A

N/A

N/A

N/A

π4231
π4231 N/A
(1 3)(2 4) (1 2)(3 4)

π4231
(3 4)

π4231
(2 4)

π4231
(1 2)

π4231
(1 3)

N/A

π4231
(2 3)

1

π3412
(1 4)(2 3)

π4321
(1 4)

π3421
(1 4)

π3412
(1 3)

π4312
(1 4)

π3421
(2 4)

N/A

π4312
(2 4)

π4312
(2 3)

π4321
(1 3)

π3421
(2 3)

π4321
(2 3)

π3412
(3 4)

π3241
(3 4)

N/A

π3412
(2 3)

π3412
(1 4)

N/A

Acknowledgements
We thank the anonymous referees, whose comments have helped us improve thepresentation of the paper. We also thank Hiroto Koyama for his cooperation in
preparing a Japanese draft version of Sect. 3 at an earlier stage of this work. This
work was supported in part by JSPS KAKENHI Grant Numbers JP21K11881
and JP19H01104.

References
1. Abe, Y., Nakai, T., Kuroki, Y., Suzuki, S., Koga, Y., Watanabe, Y., Iwamoto, M.,
Ohta, K.: Efficient card-based majority voting protocols. New Gener. Comput. 40,
173–198 (2022), https://doi.org/10.1007/s00354-022-00161-7
2. 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
3. Dvořák, P., Koucký, M.: Barrington plays cards: The complexity of card-based
protocols. In: Bläser, M., Monmege, B. (eds.) Theoretical Aspects of Computer
Science. LIPIcs, vol. 187, pp. 26:1–26:17. Schloss Dagstuhl, Dagstuhl (2021),
https://doi.org/10.4230/LIPIcs.STACS.2021.26

20

R. Haga et al.

4. Isuzugawa, R., Miyahara, D., Mizuki, T.: Zero-knowledge proof protocol for
Cryptarithmetic using dihedral cards. In: Kostitsyna, I., Orponen, P. (eds.) Unconventional Computation and Natural Computation. LNCS, vol. 12984, pp. 51–67.
Springer, Cham (2021), https://doi.org/10.1007/978-3-030-87993-8_4
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.: Foundations for actively secure card-based cryptography. In:
Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) Fun with Algorithms. LIPIcs,
vol. 157, pp. 17:1–17:23. Schloss Dagstuhl, Dagstuhl, Germany (2020), https://doi.org/10.4230/LIPIcs.FUN.2021.17
9. Koch, A., Walzer, S.: Private function evaluation with cards. New Gener. Comput.
pp. 1–33 (2022), https://doi.org/10.1007/s00354-021-00149-9, in press
10. Koch, A., Walzer, S., Härtel, K.: Card-based cryptographic protocols using a minimal number of cards. In: Iwata, T., Cheon, J.H. (eds.) Advances in Cryptology—
ASIACRYPT 2015. LNCS, vol. 9452, pp. 783–807. Springer, Berlin, Heidelberg(2015), https://doi.org/10.1007/978-3-662-48797-6_32
11. Komano, Y., Mizuki, T.: Coin-based secure computations. Int. J. Inf. Secur. pp.
1–14 (2022), https://doi.org/10.1007/s10207-022-00585-8, in press
12. Koyama, H., Miyahara, D., Mizuki, T., Sone, H.: A secure three-input AND protocol with a standard deck of minimal cards. In: Santhanam, R., Musatov, D.
(eds.) Computer Science – Theory and Applications. Lecture Notes in Computer
Science, vol. 12730, pp. 242–256. Springer, Cham (2021), https://doi.org/10.
1007/978-3-030-79416-3_14
13. Koyama, H., Toyoda, K., Miyahara, D., Mizuki, T.: New card-based copy protocols
using only random cuts. In: ASIA Public-Key Cryptography Workshop. pp. 13–22.
ACM, NY (2021), https://doi.org/10.1145/3457338.3458297
14. Kuzuma, T., Toyoda, K., Miyahara, D., Mizuki, T.: Card-based single-shuffle protocols for secure multiple-input AND and XOR computations. In: ASIA Public-Key
Cryptography. pp. 1–8. ACM, NY (2022), https://doi.org/10.1145/3494105.
3526236, to appear
15. Lafourcade, P., Miyahara, D., Mizuki, T., Robert, L., Sasaki, T., Sone, H.: How toconstruct physical zero-knowledge proofs for puzzles with a “single loop” condition.
Theor. Comput. Sci. 888, 41–55 (2021), https://doi.org/10.1016/j.tcs.2021.
07.01916. Manabe, Y., Ono, H.: Card-based cryptographic protocols with a standard deckof cards using private operations. In: Cerone, A., Ölveczky, P.C. (eds.) Theoretical
Aspects of Computing – ICTAC 2021. LNCS, vol. 12819, pp. 256–274. Springer,
Cham (2021), https://doi.org/10.1007/978-3-030-85315-0_15
17. Manabe, Y., Ono, H.: Card-based cryptographic protocols with malicious players
using private operations. New Gener. Comput. 40, 67–93 (2022), https://doi.
org/10.1007/s00354-021-00148-w
18. Miyahara, D., Hayashi, Y., Mizuki, T., Sone, H.: Practical card-based implementations of Yao’s millionaire protocol. Theor. Comput. Sci. 803, 207–221 (2020),
https://doi.org/10.1016/j.tcs.2019.11.005

Card-minimal Three-Input Protocols with Standard Playing Cards

21

19. Miyahara, D., Komano, Y., Mizuki, T., Sone, H.: Cooking cryptographers: Secure multiparty computation based on balls and bags. In: Computer Security
Foundations Symposium. pp. 1–16. IEEE, NY (2021), https://doi.org/10.1109/
CSF51468.2021.00034
20. Miyahara, D., Ueda, I., Hayashi, Y., Mizuki, T., Sone, H.: Evaluating card-based
protocols in terms of execution time. Int. J. Inf. Secur. 20, 729–740 (2021), https://doi.org/10.1007/s10207-020-00525-4
21. Miyamoto, K., Shinagawa, K.: Graph automorphism shuffles from pile-scramble
shuffles. New Gener. Comput. 40, 199–223 (2022), https://doi.org/10.1007/
s00354-022-00164-4
22. Mizuki, T.: Efficient and secure multiparty computations using a standard deck ofplaying cards. In: Foresti, S., Persiano, G. (eds.) Cryptology and Network Security.
LNCS, vol. 10052, pp. 484–499. Springer, Cham (2016), https://doi.org/10.
1007/978-3-319-48965-0_29
23. Mizuki, T., Komano, Y.: Information leakage due to operative errors in card-based
protocols. Inf. Comput. pp. 1–15 (2022), https://doi.org/10.1016/j.ic.2022.
104910, in press
24. Mizuki, T., Shizuya, H.: A formalization of card-based cryptographic protocols via
abstract machine. Int. J. Inf. Secur. 13(1), 15–23 (2014), https://doi.org/10.
1007/s10207-013-0219-4
25. Mizuki, T., Shizuya, H.: Computational model of card-based cryptographic protocols and its applications. IEICE Trans. Fundam. E100.A(1), 3–11 (2017),
https://doi.org/10.1587/transfun.E100.A.3
26. Mizuki, T., Sone, H.: Six-card secure AND and four-card secure XOR. In: Deng,
X., Hopcroft, J.E., Xue, J. (eds.) Frontiers in Algorithmics. LNCS, vol. 5598,
pp. 358–369. Springer, Berlin, Heidelberg (2009), https://doi.org/10.1007/
978-3-642-02270-8_36
27. Murata, S., Miyahara, D., Mizuki, T., Sone, H.: Efficient generation of a card-based
uniformly distributed random derangement. In: Uehara, R., Hong, S.H., Nandy,
S.C. (eds.) WALCOM: Algorithms and Computation. LNCS, vol. 12635, pp. 78–
89. Springer, Cham (2021), https://doi.org/10.1007/978-3-030-68211-8_7
28. Nakai, T., Misawa, Y., Tokushige, Y., Iwamoto, M., Ohta, K.: Secure computation for threshold functions with physical cards: Power of private permutations. New Gener. Comput. pp. 1–19 (2022), https://doi.org/10.1007/
s00354-022-00153-7, in press
29. Nakai, T., Shirouchi, S., 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
30. Niemi, V., Renvall, A.: Solitaire zero-knowledge. Fundam. Inf. 38(1,2), 181–188(1999), https://doi.org/10.3233/FI-1999-381214
31. 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
32. Robert, L., Miyahara, D., Lafourcade, P., Libralesso, L., Mizuki, T.: Physical zeroknowledge proof and NP-completeness proof of Suguru puzzle. Inf. Comput. pp.
1–14 (2021), https://doi.org/10.1016/j.ic.2021.104858, in press
33. Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake. New Gener. Comput. 40,
149–171 (2022), https://doi.org/10.1007/s00354-022-00155-5

22

R. Haga et al.

34. Ruangwises, S.: Two standard decks of playing cards are sufficient for a ZKP
for Sudoku. New Gener. Comput. pp. 1–17 (2022), https://doi.org/10.1007/
s00354-021-00146-y, in press
35. Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for Ripple Effect. Theor.
Comput. Sci. 895, 115–123 (2021), https://doi.org/10.1016/j.tcs.2021.09.
034
36. 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
37. Shinagawa, K.: On the Construction of Easy to Perform Card-Based Protocols.
Ph.D. thesis, Tokyo Institute of Technology (2020)
38. Shinagawa, K.: Card-based cryptography with dihedral symmetry. New Gener.
Comput. 39(1), 41–71 (2021), https://doi.org/10.1007/s00354-020-00117-9
39. Takashima, K., Miyahara, D., Mizuki, T., Sone, H.: Actively revealing card attackon card-based protocols. Nat. Comput. pp. 1–13 (2021), https://doi.org/10.
1007/s11047-020-09838-8, in press
40. Toyoda, K., Miyahara, D., Mizuki, T.: Another use of the five-card trick: Cardminimal secure three-input majority function evaluation. In: Adhikari, A., Küsters,
R., Preneel, B. (eds.) Progress in Cryptology – INDOCRYPT 2021. LNCS,
vol. 13143, pp. 536–555. Springer, Cham (2021), https://doi.org/10.1007/
978-3-030-92518-5_24