New Card-based Copy Protocols Using Only Random Cuts
Hiroto Koyama

Kodai Toyoda

Graduate School of Information Sciences, Tohoku
University
Sendai, Japan

Graduate School of Information Sciences, Tohoku
University
Sendai, Japan

Daiki Miyahara

Takaaki Mizuki

Graduate School of Information Sciences, Tohoku
University
National Institute of Advanced Industrial Science andTechnology (AIST)
Sendai, Japan

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

ABSTRACT1

In card-based cryptography, a commitment to a Boolean value isusually represented by two face-down cards of different colors or
numbers, whose order specifies the one-bit value (namely, 0 or 1).
One of the most important primitives in card-based cryptography
is a “copy protocol,” which is supposed to make two identical copies
of a given commitment. In the literature, there are several copy
protocols, which can be categorized by kinds of shuffles they use;
this paper focuses on those using only the so-called random cut,which is the simplest shuffle, and we propose two copy protocols
that are more efficient than the existing ones. Specifically, we firstwork on a standard deck of cards and design a six-card copy protocol
using three random cuts (on average). Since the previous protocol
needs 5.5 random cuts, our protocol improves upon it. Next, we
shift our attention to the case of a two-colored deck of cards, andconstruct a six-card copy protocol using three random cuts (onaverage). Because the previous protocol requires eight cards, ourprotocol uses two cards fewer than the previous one (although it
uses one more shuffle). In addition, going back to the standarddeck setting, we provide a four-card XOR protocol using only one
random cut for the first time.

Card-based cryptography enables us to perform cryptographic
tasks, such as secure multiparty computations, using a deck ofphysical cards. Typically, a “two-colored deck” of cards or a “standard deck” of cards is used in a card-based protocol. This paper
begins with introducing these two types of decks in Sections 1.1
and 1.2.

1.1

INTRODUCTION

Two-Colored Deck of Cards

Many card-based protocols use a two-colored deck of cards, which
consists of black cards ♣ and red cards ♥ whose backs are allidentical ? (refer to [8, 18, 35] for a survey).
Depending on the order of two cards of different colors, a Boolean
value is represented as follows:♣ ♥ = 0,♥ ♣ = 1.

(1)

Based on the above encoding rule, a player can commit his or her
private bit 𝑥 ∈ {0, 1} by placing two cards face down, keeping its
value hidden:
? ? .
|{z}
𝑥

CCS CONCEPTS

We call such a pair of face-down cards a commitment to 𝑥.

• Security and privacy → Cryptography.

1.2
KEYWORDS
Card-based cryptography, Secure computation, Real-life hands-on
cryptography, Copy protocols
ACM Reference Format:
Hiroto Koyama, Kodai Toyoda, Daiki Miyahara, and Takaaki Mizuki. 2021.
New Card-based Copy Protocols Using Only Random Cuts. In Proceedingsof the 8th ACM ASIA Public-Key Cryptography Workshop (APKC ’21), June
7, 2021, Virtual Event, Hong Kong. ACM, New York, NY, USA, 10 pages.
https://doi.org/10.1145/3457338.3458297© 2021 Copyright held by the authors. Publication rights licensed to ACM.
This is the author’s version of the work. It is posted here for your personal use. Not
for redistribution. The definitive Version of Record was published in Proceedings of the
8th ACM ASIA Public-Key Cryptography Workshop (APKC ’21), June 7, 2021, Virtual
Event, Hong Kong, https://doi.org/10.1145/3457338.3458297.

Standard Deck of Cards

Some card-based protocols [9, 10, 16, 24] work on a standard deckof cards, which consists of 52 cards (except for jokers) and eachcard has a unique pattern (suit and number) on its face: We regard
it as a total order on {1, 2, . . . , 52} and assume a deck consisting of
52 numbered cards:
1 2 3 4 · · · 51 52 ,where the backs of all cards are identical ? .
Similar to the encoding rule (1), Niemi and Renvall [24] considered an encoding rule based on which of two cards is smaller:
Define(2)
𝑖 𝑗 = 0, 𝑗 𝑖 = 1
for any two cards 𝑖 and 𝑗 with 1 ≤ 𝑖 < 𝑗 ≤ 52. Thus, if theleft card is smaller, it represents 0, and if the left card is larger, it
represents 1. Throughout this paper, we denote a commitment to𝑥 ∈ {0, 1} consisting of two numbered cards 𝑖 𝑗 by

? ? ,
|{z}
[𝑥 ] {𝑖,𝑗 }where we call such a set {𝑖, 𝑗 } the base of the commitment. For
example,? ?
|{z}[𝑥 ] {3,4}is a commitment of base {3, 4}; when we turn over these two cards,
the order 3 4 implies 𝑥 = 0, and 4 3 implies 𝑥 = 1.

1.3

|{z}

This paper mainly deals with copy protocols; given a commitment
to 𝑎 ∈ {0, 1}, a copy protocol is supposed to make two identicalcopied commitments to the bit 𝑎:? ?

→ ··· → ? ? ? ? ;|{z} |{z}

𝑎

? ?

𝑎

→ ··· →

𝑎

? ?

? ?

|{z}

|{z}

|{z}

[𝑎] {𝑖,𝑗 }[𝑎] {𝑖 1 ,𝑗1 } [𝑎] {𝑖 2 ,𝑗2 }
1 2 3 4 5 6?
? ? ? ? ?,

3 4 5 6 12
? ? ? ? ? ?,

3 4 5 6 1 2
 1 2 3 4 5 6  ? ? ? ? ? ?,
−
? ? ? ? ? ? →4 5 6 1 2 3? ? ? ? ? ?,
 5 6 1 2 3 4? ? ? ? ? ?,

6 1 2 3 4 5
 ? ? ? ? ? ? .

The Crèpeau–Kilian copy protocol [2] takes a commitment to𝑎 ∈ {0, 1} and six additional cards as input, and outputs two commitments to the bit 𝑎 after applying the random cut twice without
leaking any information about the value of the bit 𝑎:? ? ♣ ♣ ♣ ♥ ♥ ♥ → ··· → ? ?

The History of Copy Protocols|{z}probability (i.e., 1/6) as follows:.

A copy protocol plays an important role in securely computing
an arbitrary Boolean function (as well as AND/OR/XOR/NOT protocols do), and hence, it is one of the most important primitives
studied in card-based cryptography [2, 7, 11, 16, 19, 24–26].
Here, we illustrate the necessity of a copy protocol with a concrete function example. Consider a secure computation of the fiveinput majority function, whose possible circuit is:maj(𝑎, 𝑏, 𝑐, 𝑑, 𝑒) = (𝑎 ∧ 𝑏 ∧ 𝑐) ∨ (𝑎 ∧ 𝑏 ∧ 𝑑) ∨ (𝑎 ∧ 𝑏 ∧ 𝑒)
∨ (𝑎 ∧ 𝑐 ∧ 𝑑) ∨ (𝑎 ∧ 𝑐 ∧ 𝑒) ∨ (𝑎 ∧ 𝑑 ∧ 𝑒) ∨ (𝑏 ∧ 𝑐 ∧ 𝑑)∨ (𝑏 ∧ 𝑐 ∧ 𝑒) ∨ (𝑏 ∧ 𝑑 ∧ 𝑒) ∨ (𝑐 ∧ 𝑑 ∧ 𝑒).

𝑎

𝑎

𝑎

In 2009, Mizuki and Sone [19] introduced a new shuffling method,
called the “random bisection cut (RBC)” (denoted by [ · | · ]), whichbisects a sequence of cards and shuffles these two halves at random.
Although the details will be given in Section 2.3, taking a sequenceof six cards as an example, after applying a random bisection cut,the resulting sequence becomes either of the two cases with theequal probability (i.e., 1/2) as follows:h 1 2 3? ? ?

4 5 6 i?? ?

→1 2 3 4 5 6
 ? ? ? ? ? ?,

4 5 6 1 2 3
 ? ? ? ? ? ? .

Making use of the random bisection cut, the Mizuki-Sone copy
protocol [19] uses only six cards (including an input commitment)
and only one shuffle:? ? ♣ ♣ ♥ ♥ → ··· → ? ?
|{z}

? ? .

|{z} |{z}𝑎𝑎𝑎In 2015, Nishimura et al. [25, 26] designed a five-card copy protocol that requires an average of two shuffles. Their protocol uses
an unfamiliar shuffling operation, namely the “unequal division
shuffle (UDS),” as follows:
h 1 2

? ?

Since the bit 𝑎 appears six times in the above equation, we need six
commitments to 𝑎 in total to compute the function according to thecircuit (the same is true for the other bits). Therefore, to begin with,
we need to perform a copy protocol to duplicate the commitments.
Thus, copy protocols are indispensable.
In the literature, there are several copy protocols as shown in
Tables 1 and 2, in which we show their numbers of required cards,
those of required shuffles, and types of shuffles they use.
The first copy protocol was proposed by Crèpeau and Kilian [2]working on a two-colored deck of cards. This protocol uses the“random cut (RC)” (denoted by ⟨·⟩), which is a cyclic shuffling operation. Although the details will be given in Section 2.2, we takea sequence of six cards to illustrate: after applying a random cut,the resulting sequence becomes one of the six cases with the equal? ? .

|{z} |{z}3 4 5 i1 2 3 4 5
 ? ? ? ? ?,
?? ? → 3 4 5 1 2
 ? ? ? ? ? .

It is not easy for humans to implement this shuffle (without any
special auxiliary tools).
Let us shift our attention to the case of a standard deck of cards;
there are two existing copy protocols. In 1999, Niemi and Renvall [24] proposed the first copy protocol using a standard deck ofcards, which uses six cards and needs 5.5 random cuts on average:? ?

3 4 5 6 → ··· →

? ?

? ? .

|{z}

|{z} |{z}[𝑎] {1,2}[𝑎] {1,2} [𝑎] {3,4}In 2016, making use of the random bisection cut, Mizuki [16] proposed a six-card copy protocol that requires only one random bisection cut.

Table 1: Copy protocols on a two-colored deck of cards

Crépeau–Kilian [2]Mizuki–Sone [19]Nishimura et al. [25]Ours

# of cards# of shuffles

Type of shuffles

8
6
5
6

2
1
2 (exp)3 (exp)

RC
RBC
UDS
RC

Table 2: Copy protocols on a standard deck of cards

Niemi–Renvall [24]Mizuki [16]
Ours

1.4

# of cards# of shuffles

Type of shuffles

6665.5 (exp)
1
3 (exp)RC
RBC
RC

Contribution

As mentioned above, there are several kinds of shuffles, and they
contribute to improving the efficiency of copy protocols (in termsof the numbers of cards and shuffles). Now, let us compare theseshuffling operations from the perspective of practicality when implementing them. While a random bisection cut and an unequal
division shuffle require auxiliary tools, such as special card cases,
to be performed securely [26, 40], a random cut requires no such an
auxiliary tool. Therefore, a random cut is superior to the other shuffling operations in terms of practicality. This implies that seeking
a more efficient protocol using only random cuts is a meaningful
challenge in the research area of card-based cryptography. It should
be noted that Koch and Walzer [12] proposed actively secure protocols depending only on random cuts and they implied that finding
card-minimal protocols using only random cuts is an interesting
open problem.
In this paper, focusing on using only random cuts, we propose
two new copy protocols which are more efficient than the existing
ones. Specifically, we first work on a standard deck of cards anddesign a six-card copy protocol using three random cuts on average:? ?

3 4 5 6 → ··· →

? ?

? ? .

|{z}

|{z} |{z}[𝑎] {1,2}[𝑎] {3,4} [𝑎] {5,6}

Since the previous protocol, namely the Niemi–Renvall copy protocol [24], uses 5.5 random cuts as mentioned before, our protocol
improves on it. See Table 2 again. Next, we shift our attention to
the case of a two-colored deck of cards, and construct a six-card
copy protocol using three random cuts on average:? ? ♣ ♣ ♥ ♥ → ··· → ? ?
|{z}
𝑎

? ? .

|{z} |{z}𝑎𝑎Since the Crèpeau–Kilian copy protocol [2] uses eight cards andtwo random cuts (as mentioned before), our protocol uses two cards
fewer than the previous protocol (although it requires one more
shuffle). See Table 1 again.
We will prove the correctness and security of our proposed protocols by using the KWH-tree (whose idea and notion were invented

in [13]), from which we can visually confirm state transitions of
the protocols.
In addition to the two new copy protocols, we provide a new
XOR protocol working on a standard deck without any additionalcard, such as:? ?

? ? → ··· →? ?

|{z} |{z}|{z}[𝑎] {1,2} [𝑏 ] {3,4}[𝑎 ⊕𝑏 ] {1,2}.

This is a card-minimal protocol and is the first construction of an
XOR protocol using only one random cut.

1.5

Related WorkTo the best of our knowledge, no recent literature has studied elementary card-based protocols using only random cuts except for
Toyoda et al. in 2020 [39]; they proposed a six-card XOR protocol
using only random cuts, improving the existing ones [2, 20]. Apartfrom secure computations of logical functions, card-based protocols have attractive applications such as solving Yao’s millionaires’problem [15, 22, 23, 27, 38], zero-knowledge proof protocols for
pencil puzzles [31–34], secure grouping [4] and lottery [37], generating a derangement [5, 6, 21], and efficient secure multi-valued
function evaluation using dihedral symmetry [36]. Instead of using
shuffles, card-based protocols relying on private operations havebeen studied [1, 14, 28–30, 42, 43]. Recently, the relationship between card-based protocols and the (conventional) computational
complexity was discussed [3].

1.6Outline

The remainder of this paper is organized as follows. In Section 2,
we introduce a formal description of actions and the notions of two
kinds of shuffles. In Section 3, we present our copy protocol ona standard deck. In Section 4, we present our copy protocol on a
two-colored deck. In Section 5, we present our XOR protocol on astandard deck. We conclude this paper in Section 6.

2

PRELIMINARIESIn this section, we first present a formal treatment of actions appearing in card-based protocols (which has been developed in [7, 17, 18]).

Then, we introduce two important kinds of shuffles, i.e., the random
cut and the random bisection cut.

2.1

each of which occurs with a probability of 1/𝑛:
𝑛−1 𝑛
1 2 3



·
·
·
?
?
?
? ?,



2 3 4
𝑛 1




? ? ? ··· ? ? ,1 2 3


𝑛−1 𝑛


..
−
? ? ? ··· ? ? →.

𝑛−3 𝑛−2𝑛−1 𝑛 1··· ? ? ,

?
?
?


 𝑛 1 2𝑛−2 𝑛−1
 ? ? ? ··· ? ? .

Actions

Assume that we have a sequence of 𝑛 face-down cards on a table:
1 2𝑛? ? ··· ? ,where we attach the number 𝑖, 1 ≤ 𝑖 ≤ 𝑛, to the 𝑖-th card (from theleft) for convenience sake. Let 𝑆𝑛 denote the symmetric group ofdegree 𝑛. We present four actions, as follows.
Permuting. Apply a permutation 𝜋 ∈ 𝑆𝑛 to the sequence of 𝑛cards. We denote this action by (perm, 𝜋):𝑛 (perm,𝜋 ) 𝜋 −1 (1) 𝜋 −1 (2)1 2? ? · · · ? −−−−−−−−→?

?

𝜋 −1 (𝑛)

···

?

.

Turning. Turn over all cards whose positions are in 𝑇 ⊆{1, . . . , 𝑛} to check the numbers or colors of the cards: We
denote this action by (turn,𝑇 ). For instance, if 𝑇 = {𝑡 },1 2

𝑡𝑛 (turn,{𝑡 })1 2

𝑛 (turn,{𝑡 })

1 2

𝑡

𝑡

(shuf, {id, 𝜋, 𝜋 2 , . . . , 𝜋 𝑛−1 })for a cyclic permutation 𝜋 = (1 2 3 · · · 𝑛), where id ∈ 𝑆𝑛 denotes
the identity permutation.
In the sequel, we use RC1,2,...,𝑛 to represent {id, 𝜋, 𝜋 2 , . . . , 𝜋 𝑛−1 }.
For example, (shuf, RC1,2,3,4,5,6 ) is a random cut to a sequence of
six face-down cards:
? ? ? ? ? ? .

𝑛? ? · · · ? · · · ? −−−−−−−−→ ? ? · · · 3 · · · ? ;1 2This random cut is formally described as𝑡

A random cut can be easily performed by human hands; a secure
implementation called the Hindu cut is well known [40, 41].

𝑛

? ? · · · ? · · · ? −−−−−−−−→ ? ? · · · ♥ · · · ? .
Shuffle. Apply a permutation 𝜋 ∈ Π chosen uniformly randomly from a permutation set Π ⊆ 𝑆𝑛 . We denote this actionby (shuf, Π):
1 2𝑛 (shuf,Π) 𝜋 −1 (1) 𝜋 −1 (2)? ? · · · ? −−−−−−−→?

?

𝜋 −1 (𝑛)

···

?

𝑖1

𝑖2

𝑗1

𝑗2

The random bisection cut (RBC) is another major shuffle action
invented in 2009 [19]. This shuffle, denoted by [ · | · ], bisects asequence of 2𝑛 cards and randomly swaps the two halves; theresulting sequence becomes one of the following two sequences:
h 1

𝑛+1

2𝑛 i

? ··· ?

1
𝑛 𝑛+1
2𝑛


 ? ··· ? ? ··· ? ,

→ 𝑛+1
2𝑛 1
𝑛


 ? ··· ? ? ··· ? .

That is, the resulting sequence either remains the same as theoriginal one, or becomes a sequence such that the two halves areswapped with a probability of 1/2. This random bisection can be
expressed as𝑛(shuf, {id, (1 𝑛+1)(2 𝑛+2) · · · (𝑛 2𝑛)}).
𝑖1 𝑖2

𝑗1 𝑗2

−−−−−−−−−−−−−−−−−→ ? ? ? ? .
|{z} |{z}𝑎𝑎Note that, technically, the order of 𝑖 1, 𝑖 2, 𝑗1, 𝑗2 can be arbitrary.

2.2𝑛? ··· ?

? ··· ? ··· ? ··· ? ··· ? ··· ?
(result,(𝑖 1 ,𝑖 2 ),( 𝑗1 ,𝑗2 ))Random Bisection Cut.

Note that nobody can know which permutation in Π wasapplied. In the next two subsections, we show two specifickinds of shuffles.
Result. Specify positions of output commitments. In a copy
protocol, (result, (𝑖 1, 𝑖 2 ), ( 𝑗1, 𝑗2 )) means that two copied commitments are obtained at the corresponding positions:1

2.3

Random Cut

As seen in the previous subsection, a shuffle is mathematicallydefined by giving a permutation set Π. In this sense, we can consider
any shuffles. However, when constructing practical card-based
protocols, it is crucial how easy-to-implement the shuffles to be
used are.
The simplest and most easy-to-implement shuffle is the random
cut (RC), denoted by ⟨·⟩, that shifts a sequence of cards cyclically andrandomly. If a random cut is applied to a sequence of 𝑛 cards, thenthe resulting sequence becomes one of the following 𝑛 sequences,

A few secure implementations of a random bisection cut wereshown in [40]. One is a method called the spinning throw using arubber band and a separator. In this method, a separator is put inthe middle of a sequence of cards so that the sequence is bisected,
and the separator and the two halves are fixed by using a rubberband. Then, they are thrown in a spinning manner so that the two
halves are shuffled randomly. Another method employs the verticalasymmetricity of the backs of cards and reduces applying a random
bisection cut to applying a random cut.

3

COPY PROTOCOL ON STANDARD DECKIn this section, working on a standard deck of cards, we present a
new copy protocol that uses only three random cuts (on average).
In Section 3.1, we provide a basic technique: We show that arandom bisection cut (RBC) with opening leading cards can be
conducted via a series of random cuts (RCs) if we are working on astandard deck. Applying this basic technique, we construct our copy

3. Apply a random cut to the sequence of all cards:
 1

𝑛+1
𝑛
2𝑛
·
·
·
·
·
·
? ?
? ? ?
? → ? ······ ? .
| {z }

protocol in Section 3.2, followed by its pseudocode in Section 3.3.
We prove that our protocol is correct and secure in Section 3.4.

3.1

Basic Technique: RBC and Opening
Leading Cards via RCs

2𝑛 + 2 cards

Assume that we have 2𝑛 face-down cards (of a standard deck) whose
first and (𝑛 +1)-st cards are 𝑖 𝑗 or 𝑗 𝑖 and that we want to reveal
the first card after applying a random bisection cut:
1

𝑛 𝑛+1

2𝑛

? ··· ? ? ··· ? →h? ··· ?

? ··· ?

i→? ··· ? ? ··· ? .
|{z}

(3)

reveal

We assume that everyone knows that the 2𝑛 cards consist of cards
numbered 1 through 2𝑛, and hence, 1 ≤ 𝑖 ≠ 𝑗 ≤ 2𝑛.
As mentioned in Section 2.3, secure implementations of a random bisection cut are known [40] under certain constraints. Forcommercially available standard decks of cards, however, the backof every card is often vertically symmetric, i.e., a secure implementation using the vertical asymmetricity of the backs does not work.
Moreover, it might happen that no auxiliary tool such as a rubberband is available.
Fortunately, we can consider the following (partial) implementation of a random bisection cut via the random cut.
1. Apply a random cut to the sequence of 2𝑛 cards:
1

𝑛 𝑛+1
2𝑛
? ··· ? ? ··· ? → ? ······ ? .
| {z }

4. Turn over the first card; if it is 1 or 2 , reveal the (𝑛 + 2)-ndcard (i.e., the other card constituting the commitment to 𝑎)as well. Otherwise, return to Step 3.
1 , theSince the probability of returning to Step 3 in Step 4 is 𝑛+1
expected number of required shuffles is 𝑛 + 1.
Using this technique, we can simulate the six-card copy protocol
invented by Mizuki [16], which uses a random bisection cut once,
so that we obtain a six-card copy protocol using only random cuts,
as seen in the next subsection.

3.2[𝑎] {3,4} [𝑎] {5,6}

1 3 5 2 4 6(b) Apply a random cut to the sequence of all cards:
? ? ? ? ? ? → ? ? ? ? ? ?.
(c) Turn over the first card; if it is 1 , swap the third and fifth
cards. If it is 2 , apply a permutation (2 3 6 5). Otherwise,
return to Step 1(b).
2. Then we have2𝑛

1 ? ? ? ? ? or 2 ? ? ? ? ? .
|{z} |{z}|{z} |{z}[𝑎] {3,4}[𝑎] {5,6}[𝑎] {3,4}[𝑎] {5,6}

Thus, our copy protocol uses three random cuts on average. Notethat Step 1(c) rearranges the cards so that they are in order; in thepseudocode below, we will omit this rearrangement.

? ? ? ··· ? ? ··· ? .

3.3

|{z}

In this subsection, we show a pseudocode for our copy protocol
described in Section 3.2.

[𝑎] {1,2}

Note that the sequence of 2𝑛 cards contains neither 1 nor
2.
2. Move the right card of the commitment to the middle asfollows:
𝑛 𝑛+1

2𝑛

1

𝑛

𝑛+1

2𝑛

? ? ? ··· ? ? ··· ? → ? ? ··· ? ? ? ··· ? .
|{z}[𝑎] {1,2}

1 2 3 4 5 6

1. Assume that we have a commitment to 𝑎 ∈ {0, 1} whosebase is {1, 2}. Place the commitment and the sequence of 2𝑛
cards as follows:[𝑎] {1,2}? ? .

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

Note that the expected number of random cuts for finishing theabove procedure is 𝑛.
More usefully, along with 2𝑛 cards, if we have a commitment
which we want to reveal after shuffling, the goal (3) can be achieved
using random cuts as follows.

1

? ?

|{z}

The protocol proceeds as follows.
1. Apply the technique shown in Section 3.1 to the commitment
to 𝑎 and the sequence of additional four cards, as follows.
(a) Rearrange the sequence:

2. Turn over the first card. If it is 𝑖 or 𝑗 , this means that arandom bisection cut was applied to the sequence, i.e., wehave achieved the goal (3). Otherwise, turn the first card
face down, and return to Step 1. Note that this step leaks no
information because the revealed card is chosen uniformly
from the sequence of 2𝑛 cards at random.

𝑛 𝑛+1

3 4 5 6 → ··· →

? ?

2𝑛

1

Protocol Description

Now, we are ready to present our copy protocol on a standard deck.
Given a commitment to 𝑎 ∈ {0, 1} whose base is {1, 2} along withfour additional cards 3 4 5 6 , our copy protocol outputs two
commitments to 𝑎 whose bases are {3, 4} and {5, 6}:

Pseudocode

input set:n ? ? ? ? ? ?   ? ? ? ? ? ? o
, , , , , , , , , , ,1 2 3 4 5 6
2 1 3 4 5 6(perm, (2 4 5 3))
1 (shuf, RC1,2,3,4,5,6 )(turn, {1})

if visible seq. = (1, ?, ?, ?, ?, ?) then(result, (2, 5), (3, 6))else if visible seq. = (2, ?, ?, ?, ?, ?) then(result, (5, 2), (6, 3))
else(turn, {1})go to 1

Then, turn over the four face-up cards:? ? ? ? ? ?.
|{z}𝑎2. Apply a random cut to the sequence of six cards:→ ? ? ? ? ? ?.

? ? ? ? ? ?

3. Reveal the first and the fourth cards:

3.4

Correctness and Security

In this subsection, we verify the correctness and security of the
protocol presented in Section 3.2.
A copy protocol is said to be correct if, given an input commitment to 𝑎, it always produces two commitments to 𝑎. We say
a protocol is secure if it leaks no information for any run of the
protocol (in other words, random variables 𝐼 and 𝑉 denoting the
inputs and the visible sequence trace, respectively, are stochastically independent, where the visible sequence trace means what
can be observed on the table). See [13, 17, 18] for the more formal
definitions based on abstract machine and information theory.
We describe the KWH-tree (which is a nice way of depicting a diagram developed by Koch, Walzer, and Härtel [13]) of our proposed
protocol in Figure 2. In this figure, we call each box a state. The firststate (box) in Figure 2 corresponds to an initial sequence, consistingof an input commitment and four additional cards; 𝑋 0 and 𝑋 1 represent the probabilities of 𝑎 = 0 and 𝑎 = 1, respectively. A polynomial
annotating a card sequence in a state, such as +1/6𝑋 0 , represents
the conditional probability that the current sequence is the one next
to the polynomial, given the visible sequence trace observed so far
on the table. The two states (boxes) at the bottom imply that two
commitments to 𝑎 are definitively obtained. Furthermore, in eachstate, the sum of all polynomials is equal to 𝑋 0 + 𝑋 1 , implying thatno information about 𝑎 leaks, i.e., the inputs and visible sequence
trace are stochastically independent.
Thus, the KWH-tree in Figure 1 guarantees that our proposed
protocol is correct and secure. (As stated in [7], the KWH-tree is awitness for the correctness and security.)

4

COPY PROTOCOL ON TWO-COLOREDDECK

In this section, we present a new copy protocol that uses only the
random cut (three times on average) with a two-colored deck ofcards. We show the description of our protocol in Section 4.1 and its
pseudocode in Section 4.2. We verify the correctness and securityof our protocol in Section 4.3.

4.1

Description

Here, we give the description of our copy protocol working on a
two-colored deck.
1. Place a commitment to 𝑎 ∈ {0, 1} and four additional cards
as follows:? ? ♥ ♣ ♣ ♥.
|{z}𝑎revealreveal

z}|{

z}|{

?

? ?

?

? ?.

(a) If ♥ ♥ or ♣ ♣ appears, then turn them face down and go
back to Step 2.
(b) If ♥ ♣ or ♣ ♥ appears, then we obtain two commitments
to 𝑎 as follows:♥ ? ? ♣ ? ?

J
^
J
? ?

J
^
J
? ?

|{z}
𝑎

♣ ? ? ♥ ? ?
or

J
^
J
? ?

J
^
J
? ? .

|{z}

|{z}

|{z}

𝑎

𝑎

𝑎

This is our copy protocol. As noticed, this protocol is very simple
and takes an average of three random cuts to complete. Since theprevious protocol using random cuts, i.e., the Crèpeau–Kilian copy
protocol, requires six additional cards, our protocol is more efficientin this regard, although it uses one more shuffle (on average). See
the bottom row in Table 1 again.

4.2

Pseudocode

The following is a pseudocode for our copy protocol.
input set:n ? ? ? ? ? ?   ? ? ? ? ? ? o
, , , , , , , , , , ,♥ ♣ ♥ ♣ ♣ ♥♣ ♥ ♥ ♣ ♣ ♥1 (shuf, RC1,2,3,4,5,6 )(turn, {1, 4})if visible seq. = (♥, ?, ?, ♥, ?, ?) or (♣, ?, ?, ♣, ?, ?) then(turn, {1, 4})
go to 1else if visible seq. = (♥, ?, ?, ♣, ?, ?) or (♣, ?, ?, ♥, ?, ?) then(result, (3, 2), (6, 5))
In the next subsection, we confirm that our protocol definitively
produces two commitments to 𝑎 without leaking any information
about 𝑎.

4.3

Correctness and Security

We can show the correctness and security of this protocol in thesame way as we did with a standard deck in Section 3.4. The KWHtree in Figure 2 guarantees that our proposed protocol is correctand secure.

ʹͳ͵Ͷͷ͸ ൅ܺଵͳʹ͵Ͷͷ͸ ൅ܺ଴(perm, (2 4 5 3))(shuf, ଵǡଶǡଷǡସǡହǡ଺)ͳͶ͸ʹ͵ͷ ାଵ଺ ܺଵ ͳ͵ͷʹͶ͸ ାଵ଺ ܺ଴ʹ͵ͷͳͶ͸ ାଵ଺ ܺଵ ʹͶ͸ͳ͵ͷ ାଵ଺ ܺ଴͵ͷͳͶ͸ʹ ାଵ଺ ܺଵ ͵ͷʹͶ͸ͳ ାଵ଺ ܺ଴Ͷ͸ʹ͵ͷͳ ାଵ଺ ܺଵ Ͷ͸ͳ͵ͷʹ ାଵ଺ ܺ଴ͷͳͶ͸ʹ͵ ାଵ଺ ܺଵ ͷʹͶ͸ͳ͵ ାଵ଺ ܺ଴͸ʹ͵ͷͳͶ ାଵ଺ ܺଵ ͸ͳ͵ͷʹͶ ାଵ଺ ܺ଴(turn, {1})(turn, {1})(shuf, ଵǡଶǡଷǡସǡହǡ଺)

revealed 3 4 5 6

revealed 1

revealed 2ͳͶ͸ʹ͵ͷ ൅ܺଵͳ͵ͷʹͶ͸ ൅ܺ଴ʹ͵ͷͳͶ͸ ൅ܺଵʹͶ͸ͳ͵ͷ ൅ܺ଴(result, (5, 2), (6, 3))(result, (2, 5), (3, 6))㾐㾐

Figure 1: The KWH-tree of our six-card copy protocol on a standard deckὓ‗ὓ‗‗ὓ‗ὓὓ‗‗ὓнͳнͲሺshuf, ͳǡʹǡ͵ǡͶǡͷǡ͸ሻὓ‗ὓ‗‗ὓ‗ὓ‗‗ὓὓὓ‗‗ὓὓ‗‗‗ὓὓ‗ὓ‗ὓὓ‗ὓ‗ὓὓ‗ὓ‗‗

ଵ
଺
ଵ
൅ ͳ
଺
ଵ
൅ ͳ
଺
ଵ
൅ ͳ
଺
ଵ
൅ ͳ
଺
ଵ
൅ ͳ
଺

൅ ͳ

‗ὓὓ‗‗ὓὓὓ‗‗ὓ‗ὓ‗‗ὓ‗ὓ‗‗ὓ‗ὓὓ‗ὓ‗ὓὓ‗ὓ‗ὓὓ‗‗(turn, {1,4})

нͳ
нͲ

(result, (3, 2), (6, 5))㾐(turn, {1,4})(shuf, ͳǡʹǡ͵ǡͶǡͷǡ͸)

revealed ‗ǡ‗ Žƌὓǡὓ
revealed ‗ǡὓrevealed ὓǡ‗ὓ‗ὓ‗‗ὓὓὓ‗‗ὓ‗

ଵ
଺
ଵ
൅ Ͳ
଺
ଵ
൅ Ͳ
଺
ଵ
൅ Ͳ
଺
ଵ
൅ Ͳ
଺
ଵ
൅ Ͳ
଺

൅ Ͳ

‗‗ὓὓ‗ὓ‗ὓ‗ὓὓ‗нͳнͲ(result, (3, 2), (6, 5))㾐Figure 2: The KWH-tree of our six-card copy protocol on a two-colored deck

5

XOR PROTOCOL USING ONLY RANDOM
CUT(perm, (2 4 3))(result, (3, 4))

In this section, going back to the standard-deck case, we construct
a new XOR protocol by applying the idea behind the techniquepresented in Section 3.1. This makes it possible to perform a secure
XOR computation where the number of cards and the number ofshuffles are both minimized and the used shuffle is a random cut.

5.1

Protocol Description

Given two commitments to 𝑎, 𝑏 ∈ {0, 1}, our protocol proceeds asfollows.
1. Place the input commitments:

? ?

? ? .

|{z} |{z}[𝑎] {1,2} [𝑏 ] {3,4}

2. Rearrange the sequence:
1 2 3 41 3 2 4

? ? ? ? → ? ? ? ? .
3. Apply a random cut to the sequence of four cards:
? ? ? ? → ? ? ? ?.
4. Turn over the first card. If it is 1 or 4 , swap the second
and third cards. If it is 2 or 3 , permute the cards according
to (2 4 3).
5. Then we have1 ?

? ? , 2 ?

? ? ,

|{z}

|{z}

[𝑎 ⊕𝑏 ] {3,4}[𝑎 ⊕𝑏 ] {3,4}

3 ?

? ?

or

4 ?

? ?

|{z}

|{z}

[𝑎 ⊕𝑏 ] {1,2}[𝑎 ⊕𝑏 ] {1,2}.

Thus, our protocol requires only one random cut and does not
require any additional card. Since the existing XOR protocol using
only random cuts, namely Niemi and Renvall’s XOR protocol [24],requires an average of seven shuffles, as shown in Table 3, ourprotocol is superior to it. Furthermore, under the encoding rule (2),our protocol is optimal in terms of both the number of cards and thenumber of shuffles, and is no worse than the existing XOR protocol
using a random bisection cut proposed by Mizuki [16].

5.2

Pseudocode

The following is a pseudocode for our XOR protocol on a standard
deck.
input set:n  ? ? ? ?   ? ? ? ?   ? ? ? ?   ? ? ? ? o
, , , , , , , , , , , , , , ,2 1 4 32 1 3 41 2 4 3
1 2 3 4
(perm, (2 3))(shuf, RC1,2,3,4 )(turn, {1})if visible seq. = (1, ?, ?, ?) or (4, ?, ?, ?) then(perm, (2 3))
else if visible seq. = (2, ?, ?, ?) or (3, ?, ?, ?)then

5.3

Correctness and Security

We can show the correctness and security of this protocol in thesame way as we did thus far. The KWH-tree in Figure 3 guarantees that our proposed protocol is correct and secure. Note that,
contrary to the previous XOR protocols [16, 24], the base of output
commitment is not deterministic, i.e., is either {1, 2} or {3, 4}.

6

CONCLUSION

In card-based cryptography, the random cut is believed to be themost easy-to-implement shuffle, and hence, card-based protocols
that rely only on random cuts are much preferable. In this paper,
we have constructed three new protocols using only random cuts
as shuffle actions.
Specifically, the first protocol is a six-card copy protocol working
on a standard deck, and uses three random cuts on average. The
second one is also a six-card copy protocol with three random cuts,
working on a two-colored deck. The third one is a standard-deck
XOR protocol using only one random cut without any additionalcard. Every protocol is superior to the existing ones in terms of thenumber of cards or shuffles.
Because our copy protocols produce two copied commitments,
an intriguing open problem is to extend our results to constructing
copy protocols which generate more than two copied commitments.
Note that our protocol presented in Section 3 can be generalized(based on the basic technique shown in Section 3.1) although it
would increase the expected number of shuffles. In particular, tomake 𝑘 copied commitments, we use 2𝑘 additional cards and 𝑘 + 1
shuffles (on average).

ACKNOWLEDGMENTS
We thank the anonymous referees, whose comments have helped us
to improve the presentation of the paper. This work was supported
in part by JSPS KAKENHI Grant Number JP19J21153.

REFERENCES[1] Yoshiki Abe, Mitsugu Iwamoto, and Kazuo Ohta. 2020. How to Detect Malicious
Behaviors in a Card-Based Majority Voting Protocol with Three Inputs. In 2020
International Symposium on Information Theory and Its Applications (ISITA). 377–
381. https://doi.org/10.34385/proc.65.C01-9[2] Claude Crépeau and Joe Kilian. 1994. Discreet Solitary Games. In Advances in
Cryptology—CRYPTO’ 93 (LNCS, Vol. 773), Douglas R. Stinson (Ed.). Springer,
Berlin, Heidelberg, 319–330. https://doi.org/10.1007/3-540-48329-2_27[3] Pavel Dvořák and Michal Koucký. 2021. Barrington Plays Cards: The Complexity of Card-based Protocols. In Theoretical Aspects of Computer Science(LIPIcs, Vol. 187), Markus Bläser and Benjamin Monmege (Eds.). Schloss Dagstuhl,
Dagstuhl, 26:1–26:17. https://doi.org/10.4230/LIPIcs.STACS.2021.26[4] Yuji Hashimoto, Koji Nuida, Kazumasa Shinagawa, Masaki Inamura, and Goichiro
Hanaoka. 2018. Toward Finite-Runtime Card-Based Protocol for Generatinga Hidden Random Permutation without Fixed Points. IEICE Trans. Fundam.
Electron. Commun. Comput. Sci. E101.A, 9 (2018), 1503–1511. https://doi.org/10.
1587/transfun.E101.A.1503[5] T. Ibaraki and Y. Manabe. 2016. A More Efficient Card-Based Protocol for Generating a Random Permutation without Fixed Points. In Mathematics and Computers inSciences and in Industry (MCSI). 252–257. https://doi.org/10.1109/MCSI.2016.054[6] Rie Ishikawa, Eikoh Chida, and Takaaki Mizuki. 2015. Efficient Card-Based Protocols for Generating a Hidden Random Permutation Without Fixed Points.
In Unconventional Computation and Natural Computation (LNCS, Vol. 9252),

Table 3: XOR protocols on a standard deck of cards

Niemi–Renvall [24]Mizuki [16]Ours

# of cards# of shuffles

Type of shuffles

444

7 (exp)
1
1

RC
RBC
RC

ʹͳͶ͵ ൅ܺଵଵʹͳ͵Ͷ ൅ܺଵ଴ ͳʹͶ͵ ൅ܺ଴ଵͳʹ͵Ͷ ൅ܺ଴଴(perm, (2,3))(shuf, ଵǡଶǡଷǡସ)ͳ͵ʹͶ ൅ଵସܺଵଵʹͶͳ͵ ൅ଵସܺଵଵ ͵ʹͶͳ ൅ଵସܺଵଵͶͳ͵ʹ ൅ଵସܺଵଵ
ͳͶʹ͵ ൅ଵସܺଵ଴ʹ͵ͳͶ ൅ଵସܺଵ଴ ͵ͳͶʹ ൅ଵସܺ଴଴Ͷʹ͵ͳ ൅ଵସܺଵ଴
ͳͶʹ͵ ൅ଵସܺ଴ଵʹ͵ͳͶ ൅ଵସܺ଴ଵ ͵ͳͶʹ ൅ଵସܺ଴ଵͶʹ͵ͳ ൅ଵସܺ଴ଵ
ͳ͵ʹͶ ൅ଵସܺ଴଴ʹͶͳ͵ ൅ଵସܺ଴଴ ͵ʹͶͳ ൅ଵସܺ଴଴Ͷͳ͵ʹ ൅ଵସܺ଴଴
(turn, {1})revealed 4

revealed 1
revealed 2ͳ͵ʹͶ ൅ܺଵଵͳͶʹ͵ ൅ܺଵ଴ ͳͶʹ͵ ൅ܺ଴ଵͳ͵ʹͶ ൅ܺ଴଴(result, 4, 2)㾐revealed 3ʹͶͳ͵ ൅ܺଵଵʹ͵ͳͶ ൅ܺଵ଴ ʹ͵ͳͶ ൅ܺ଴ଵʹͶͳ͵ ൅ܺ଴଴(result, 2, 4)㾐͵ʹͶͳ ൅ܺଵଵ͵ͳͶʹ ൅ܺଵ଴ ͵ͳͶʹ ൅ܺ଴ଵ͵ʹͶͳ ൅ܺ଴଴(result, 2, 4)㾐Ͷͳ͵ʹ ൅ܺଵଵͶʹ͵ͳ ൅ܺଵ଴ Ͷʹ͵ͳ ൅ܺ଴ଵͶͳ͵ʹ ൅ܺ଴଴(result, 4, 2)

㾐Figure 3: The KWH-tree of our four-card XOR protocol on standard deck
Cristian S. Calude and Michael J. Dinneen (Eds.). Springer, Cham, 215–226.
https://doi.org/10.1007/978-3-319-21819-9_16[7] Julia Kastner, Alexander Koch, Stefan Walzer, Daiki Miyahara, Yu-ichi Hayashi,
Takaaki Mizuki, and Hideaki Sone. 2017. The Minimum Number of Cards inPractical Card-Based Protocols. In Advances in Cryptology—ASIACRYPT 2017
(LNCS, Vol. 10626), Tsuyoshi Takagi and Thomas Peyrin (Eds.). Springer, Cham,
126–155. https://doi.org/10.1007/978-3-319-70700-6_5[8] Alexander Koch. 2019. Cryptographic Protocols from Physical Assumptions. Ph.D.
Dissertation. Karlsruhe Institute of Technology. https://doi.org/10.5445/IR/
1000097756[9] Alexander Koch, Michael Schrempp, and Michael Kirsten. 2019. Card-Based
Cryptography Meets Formal Verification. In Advances in Cryptology–ASIACRYPT
2019 (LNCS, Vol. 11921), Steven D. Galbraith and Shiho Moriai (Eds.). Springer,
Cham, 488–517. https://doi.org/10.1007/978-3-030-34578-5_18[10] Alexander Koch, Michael Schrempp, and Michael Kirsten. 2021. Card-based
cryptography meets formal verification. New Gener. Comput. 39, 1 (2021), 115–
158. https://doi.org/10.1007/s00354-020-00120-0[11] Alexander Koch and Stefan Walzer. 2018. Private Function Evaluation with Cards.
Cryptology ePrint Archive, Report 2018/1113. https://eprint.iacr.org/2018/1113.
[12] Alexander Koch and Stefan Walzer. 2020. Foundations for Actively Secure CardBased Cryptography. In Fun with Algorithms (Leibniz International Proceedingsin Informatics (LIPIcs), Vol. 157), Martin Farach-Colton, Giuseppe Prencipe, and
Ryuhei Uehara (Eds.). Schloss Dagstuhl, Dagstuhl, Germany, 17:1–17:23. https://doi.org/10.4230/LIPIcs.FUN.2021.17[13] Alexander Koch, Stefan Walzer, and Kevin Härtel. 2015. Card-Based Cryptographic Protocols Using a Minimal Number of Cards. In Advances in Cryptology—
ASIACRYPT 2015 (LNCS, Vol. 9452), Tetsu Iwata and Jung Hee Cheon (Eds.).

Springer, Berlin, Heidelberg, 783–807. https://doi.org/10.1007/978-3-662-487976_32[14] Yoshifumi Manabe and Hibiki Ono. 2021. Secure Card-Based Cryptographic
Protocols Using Private Operations Against Malicious Players. In Innovative Security Solutions for Information Technology and Communications (LNCS, Vol. 12596),
Diana Maimut, Andrei-George Oprina, and Damien Sauveron (Eds.). Springer,
Cham, 55–70. https://doi.org/10.1007/978-3-030-69255-1_5[15] Daiki Miyahara, Yu ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. 2020. Practical card-based implementations of Yao’s millionaire protocol. Theor. Comput.
Sci. 803 (2020), 207–221. https://doi.org/10.1016/j.tcs.2019.11.005[16] Takaaki Mizuki. 2016. Efficient and Secure Multiparty Computations Using aStandard Deck of Playing Cards. In Cryptology and Network Security (LNCS,
Vol. 10052), Sara Foresti and Giuseppe Persiano (Eds.). Springer, Cham, 484–499.
https://doi.org/10.1007/978-3-319-48965-0_29[17] Takaaki Mizuki and Hiroki Shizuya. 2014. A formalization of card-based cryptographic protocols via abstract machine. Int. J. Inf. Secur. 13, 1 (2014), 15–23.
https://doi.org/10.1007/s10207-013-0219-4[18] Takaaki Mizuki and Hiroki Shizuya. 2017. Computational Model of Card-Based
Cryptographic Protocols and Its Applications. IEICE Trans. Fundam. Electron.
Commun. Comput. Sci. E100.A, 1 (2017), 3–11. https://doi.org/10.1587/transfun.
E100.A.3[19] Takaaki Mizuki and Hideaki Sone. 2009. Six-Card Secure AND and Four-Card
Secure XOR. In Frontiers in Algorithmics (LNCS, Vol. 5598), Xiaotie Deng, John E.
Hopcroft, and Jinyun Xue (Eds.). Springer, Berlin, Heidelberg, 358–369. https://doi.org/10.1007/978-3-642-02270-8_36

[20] Takaaki Mizuki, Fumishige Uchiike, and Hideaki Sone. 2006. Securely computing
XOR with 10 cards. The Australasian Journal of Combinatorics 36 (2006), 279–293.
https://ajc.maths.uq.edu.au/?page=get_volumes&volume=36[21] Soma Murata, Daiki Miyahara, Takaaki Mizuki, and Hideaki Sone. 2021. Efficient
Generation of a Card-Based Uniformly Distributed Random Derangement. In
WALCOM: Algorithms and Computation (LNCS, Vol. 12635), Ryuhei Uehara, SeokHee Hong, and Subhas C. Nandy (Eds.). Springer, Cham, 78–89. https://doi.org/
10.1007/978-3-030-68211-8_7[22] Takeshi Nakai, Yuto Misawa, Yuuki Tokushige, Mitsugu Iwamoto, and Kazuo
Ohta. 2021. How to Solve Millionaires’ Problem with Two Kinds of Cards. New
Gener. Comput. 39, 1 (2021), 73–96. https://doi.org/10.1007/s00354-020-00118-8[23] Takeshi Nakai, Yuuki Tokushige, Yuto Misawa, Mitsugu Iwamoto, and Kazuo
Ohta. 2016. Efficient Card-Based Cryptographic Protocols for Millionaires’ Problem Utilizing Private Permutations. In Cryptology and Network Security (LNCS,
Vol. 10052), Sara Foresti and Giuseppe Persiano (Eds.). Springer, Cham, 500–517.
https://doi.org/10.1007/978-3-319-48965-0_30[24] Valtteri Niemi and Ari Renvall. 1999. Solitaire Zero-knowledge. Fundam. Inf. 38,
1,2 (1999), 181–188. https://doi.org/10.3233/FI-1999-381214[25] Akihiro Nishimura, Takuya Nishida, Yu-ichi Hayashi, Takaaki Mizuki, andHideaki Sone. 2015. Five-Card Secure Computations Using Unequal Division
Shuffle. In Theory and Practice of Natural Computing (LNCS, Vol. 9477), AdrianHoria Dediu, Luis Magdalena, and Carlos Martín-Vide (Eds.). Springer, Cham,
109–120. https://doi.org/10.1007/978-3-319-26841-5_9[26] Akihiro Nishimura, Takuya Nishida, Yu-ichi Hayashi, Takaaki Mizuki, andHideaki Sone. 2018. Card-based protocols using unequal division shuffles. Soft
Comput. 22 (2018), 361–371. https://doi.org/10.1007/s00500-017-2858-2[27] H. Ono and Y. Manabe. 2018. Efficient Card-Based Cryptographic Protocols for
the Millionaires’ Problem Using Private Input Operations. In Asia Joint Conferenceon Information Security (AsiaJCIS). 23–28. https://doi.org/10.1109/AsiaJCIS.2018.
00013[28] Hibiki Ono and Yoshifumi Manabe. 2019. Card-Based Cryptographic Protocols
with the Minimum Number of Cards Using Private Operations. In Foundations andPractice of Security (LNCS, Vol. 11358), Nur Zincir-Heywood, Guillaume Bonfante,
Mourad Debbabi, and Joaquin Garcia-Alfaro (Eds.). Springer, Cham, 193–207.
https://doi.org/10.1007/978-3-030-18419-3_13[29] Hibiki Ono and Yoshifumi Manabe. 2019. Card-Based Cryptographic Protocols
with the Minimum Number of Rounds Using Private Operations. In Data Privacy
Management, Cryptocurrencies and Blockchain Technology (LNCS, Vol. 11737),
Cristina Pérez-Solà, Guillermo Navarro-Arribas, Alex Biryukov, and Joaquin
Garcia-Alfaro (Eds.). Springer, Cham, 156–173. https://doi.org/10.1007/978-3030-31500-9_10[30] Hibiki Ono and Yoshifumi Manabe. 2021. Card-Based Cryptographic LogicalComputations Using Private Operations. New Gener. Comput. 39, 1 (2021), 19–40.
https://doi.org/10.1007/s00354-020-00113-z[31] Suthee Ruangwises and Toshiya Itoh. 2020. Physical Zero-Knowledge Proof
for Numberlink. In Fun with Algorithms (Leibniz International Proceedings inInformatics (LIPIcs), Vol. 157), Martin Farach-Colton, Giuseppe Prencipe, and
Ryuhei Uehara (Eds.). Schloss Dagstuhl, Dagstuhl, Germany, 22:1–22:11. https://doi.org/10.4230/LIPIcs.FUN.2021.22[32] Suthee Ruangwises and Toshiya" Itoh. 2021. Physical Zero-Knowledge Proof for
Numberlink Puzzle and k Vertex-Disjoint Paths Problem. New Gener. Comput. 39,
1 (2021), 3–17. https://doi.org/10.1007/s00354-020-00114-y[33] Suthee Ruangwises and Toshiya Itoh. 2021. Physical Zero-Knowledge Proof
for Ripple Effect. In WALCOM: Algorithms and Computation (LNCS, Vol. 11737),
Seokhee Hong, Subhas Nandy, and Ryuhei Uehara (Eds.). Springer, Cham, 296–
307. https://doi.org/10.1007/978-3-030-68211-8_24[34] Tatsuya Sasaki, Daiki Miyahara, Takaaki Mizuki, and Hideaki Sone. 2020. Efficient
card-based zero-knowledge proof for Sudoku. Theor. Comput. Sci. 839 (2020),
135–142. https://doi.org/10.1016/j.tcs.2020.05.036[35] Kazumasa Shinagawa. 2020. On the Construction of Easy to Perform Card-BasedProtocols. Ph.D. Dissertation. Tokyo Institute of Technology.
[36] Kazumasa Shinagawa. 2021. Card-based Cryptography with Dihedral Symmetry.
New Gener. Comput. 39, 1 (2021), 41–71. https://doi.org/10.1007/s00354-02000117-9[37] Yuto Shinoda, Daiki Miyahara, Kazumasa Shinagawa, Takaaki Mizuki, andHideaki Sone. 2021. Card-Based Covert Lottery. In Innovative Security Solutions for Information Technology and Communications (LNCS, Vol. 12596), Diana
Maimut, Andrei-George Oprina, and Damien Sauveron (Eds.). Springer, Cham,
257–270. https://doi.org/10.1007/978-3-030-69255-1_17[38] Ken Takashima, Yuta Abe, Tatsuya Sasaki, Daiki Miyahara, Kazumasa Shinagawa,Takaaki Mizuki, and Hideaki Sone. 2020. Card-based protocols for secure ranking
computations. Theor. Comput. Sci. 845 (2020), 122–135. https://doi.org/10.1016/j.
tcs.2020.09.008[39] Kodai Toyoda, Daiki Miyahara, Takaaki Mizuki, and Hideaki Sone. 2020. SixCard Finite-Runtime XOR Protocol with Only Random Cut. In ACM Workshop
on ASIA Public-Key Cryptography (APKC ’20). ACM, New York, 2–8. https://doi.org/10.1145/3384940.3388961[40] Itaru Ueda, Daiki Miyahara, Akihiro Nishimura, Yu-ichi Hayashi, Takaaki Mizuki,
and Hideaki Sone. 2020. Secure implementations of a random bisection cut. Int.
J. Inf. Secur. 19, 4 (2020), 445–452. https://doi.org/10.1007/s10207-019-00463-w[41] Itaru Ueda, Akihiro Nishimura, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki
Sone. 2016. How to Implement a Random Bisection Cut. In Theory and Practiceof Natural Computing (LNCS, Vol. 10071), Carlos Martín-Vide, Takaaki Mizuki,
and Miguel A. Vega-Rodríguez (Eds.). Springer, Cham, 58–69. https://doi.org/10.
1007/978-3-319-49001-4_5[42] Y. Watanabe, Y. Kuroki, S. Suzuki, Y. Koga, M. Iwamoto, and K. Ohta. 2018.
Card-Based Majority Voting Protocols with Three Inputs Using Three Cards. In
2018 International Symposium on Information Theory and Its Applications (ISITA).
218–222. https://doi.org/10.23919/ISITA.2018.8664324[43] Kenji Yasunaga. 2020. Practical Card-Based Protocol for Three-Input Majority.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E103.A, 11 (2020), 1296–
1298. https://doi.org/10.1587/transfun.2020EAL2025