Committed-Format AND Protocol Using Only Random Cuts∗
Yuta Abe

Takaaki Mizuki

Hideaki Sone

Tohoku University

Abstract
In the research area of card-based cryptography, designing committed-format AND protocols
that are efficient in terms of the number of required cards is a major topic. Such an AND protocol
should receive two pairs of face-down (physical) cards representing two secret input bits, fromwhich it should securely produce a pair of face-down cards representing the AND value of thetwo bits via a series of actions, such as shuffling and turning over cards, along with some helping
cards. The number of required cards typically depends on allowed kinds of shuffling operations.
This paper focuses on “RC-protocols” meaning to be able to use only the random cut (RC), whichis the easiest shuffling operation to implement. The best committed-format AND RC-protocol
currently known was devised by Stiglic in 2001, where eight cards are used (i.e., his protocol needs
four helping cards). Since then, it has been an open question to determine whether there exists a
committed-format AND RC-protocol using less than eight cards. In this study, we answer to thequestion: We propose a six-card committed-format AND RC-protocol (using exactly two randomcuts). Therefore, we can reduce the number of required cards by two.

1

Introduction

Card-based cryptography provides us a practical method for performing secure multiparty computations using a deck of physical cards. A card-based protocol typically uses a two-colored deck of cards,
such as ♣ and ♥ , with their backs being ? . A pair of cards of different colors is used to represent
a Boolean value, as follows:♣ ♥ = 0, ♥ ♣ = 1.
According to this encoding rule, a pair of face-down cards representing a bit x ∈ {0, 1} is called acommitment, denoted by? ?.
| {z }x

In the research area of card-based cryptography, designing committed-format AND protocols thatare efficient in terms of the number of required cards is a major topic. Such an AND protocol should
receive two commitments? ? ? ?
| {z } | {z }abto a, b ∈ {0, 1} as input, from which it should securely produce a commitment? ?
| {z }a∧b

to the AND value a ∧ b via a series of actions, such as shuffling and turning over cards, along with somehelping cards. As an example of committed-format AND protocols, this paper begins with introducing
Stiglic’s AND protocol (Stiglic, 2001), which was devised in 2001.
∗ This is a post-peer-review, pre-copyedit version of an article published in Natural Computing. The final authenticatedversion is available online at: https://doi.org/10.1007/s11047-021-09862-2.

1

1.1

Stiglic’s AND protocol

Given commitments to a and b along with four helping cards ♣ ♣ ♥ ♥ , Stiglic’s AND protocol (Stiglic, 2001) proceeds as follows.
1. Place the two input commitments and the four helping cards, and turn over the face-up cardsas:? ? ♥ ♣ ? ? ♣ ♥ → ? ? ? ? ? ? ? ?.
| {z }| {z }| {z }| {z }aabb

2. Apply a random cut, denoted by h·i, to the sequence of eight cards:
h ? ? ? ? ? ? ? ? i→ ? ? ? ? ? ? ? ? .
The term random cut means a cyclic shuffle such that the sequence of cards will be shifted
randomly with the offset being unknown to everyone. Thus, if we attach numbers to the cards
for the sake of convenience:
1

2

3

4

5

6

7

8

? ? ? ? ? ? ? ?,then a random cut results in one of the following eight sequences (with a probability of 1/8):
1

2

3

4

5

6

7

8

? ? ? ? ? ? ? ?,
2

3

4

5

6

7

8

1

? ? ? ? ? ? ? ?,
..
.
8

1

2

3

4

5

6

7

? ? ? ? ? ? ? ? .
The random cut is considered to be one of the easiest shuffling operations to implement; a specificimplementation of a random cut is the Hindu cut (Ueda et al., 2016).
3. Reveal the first two cards (from the left).
(a) If the revealed cards are ♥ ♥ , then a commitment to a ∧ b is obtained as follows:♥ ♥ ? ? ? ? ? ?.
| {z }a∧b(b) If the revealed cards are ♣ ♣ , then we obtain♣ ♣ ? ? ? ? ? ?.
| {z }a∧b(c) If the revealed cards are ♣ ♥ or ♥ ♣ , turn over the third card.
i. If the three face-up cards are ♣ ♥ ♥ , we have♣ ♥ ♥ ? ? ? ? ? .
| {z }a∧b

ii. If the three face-up cards are ♥ ♣ ♣ , we have♥ ♣ ♣ ? ? ? ? ?.
| {z }
a∧b2

iii. If the three face-up cards are ♣ ♥ ♣ or ♥ ♣ ♥ , turn them over and return to Step 2.
This is Stiglic’s AND protocol, which uses the random cut in Step 2. Because the probability that
Step 3–(c)–iii occurs and we go back to Step 2 is 1/2, the expected number of shuffles (namely, randomcuts) is two. Thus, Stiglic’s AND protocol is not a finite-runtime one but a Las Vegas algorithm.

1.2

The History of Committed-Format AND Protocols

As seen above, Stiglic’s AND protocol uses a two-color deck of eight cards. Including this protocol,
Table 1 enumerates all the existing committed-format AND protocols.
Table 1: Existing Committed-format AND protocolsCrépeau–Kilian, 1993 (Crépeau and Kilian, 1994)
Niemi–Renvall, 1998 (Niemi and Renvall, 1998)
Stiglic, 2001 (Stiglic, 2001)
Mizuki–Sone, 2009 (Mizuki and Sone, 2009)
Koch–Walzer–Härtel, 2015 (Koch et al., 2015)
Abe–Mizuki–Sone, 2018 (Abe et al., 2018, 2021)
Koch, 2018 (Koch, 2018)
Ruangwises–Itoh, 2018 (Ruangwises and Itoh, 2019)

Card#Colors #Cards
4
10
2
12
2
8
2
6
2
4
2
5
2
5
2
4
2
5

Shufflerandom cut
random cut
random cut
random bisection cut
includes non-uniform shuffle
includes non-uniform non-closed shuffle
random cut + random bisection cut
includes non-closed shuffle
includes non-closed shuffle

FiniteX
X

X

As known from Table 1, there are several kinds of shuffles. Remember the random cut applied at
Step 2 of Stiglic’s AND protocol explained in Section 1.1: This random cut shifts the sequence of eightcards randomly, and hence, using the cyclic permutation (1 2 · · · 8), the shuffle can be written as:(shuf, {id, (1 2 · · · 8), (1 2 · · · 8)2 , · · · , (1 2 · · · 8)7 }),where id is the identity permutation. Generally, a shuffle can be expressed as(shuf, Π, F)
using a set of permutations Π and a probability distribution F on Π; when the distribution F is
uniform, we omit it in the description. An action (shuf, Π, F) results in rearranging a sequence ofcards following a permutation π drawn from Π according to the distribution F.
We now formally define a random cut for a (sub)sequence of length n starting at the k-th position,
as follows:(shuf, RCk,n )where
RCk,n = {id, (k k + 1 · · · k + n − 1), · · · ,(k k + 1 · · · k + n − 1)n−1 }.
A protocol using such random cuts only as shuffling actions is called an RC-protocol in this paper.
Stiglic’s AND protocol is an RC-protocol, and the first protocol (Crépeau and Kilian, 1994) and thesecond protocol (Niemi and Renvall, 1998) in Table 1 are also RC-protocols.
Another well-known shuffle is the “random bisection cut,” that bisects a sequence of cards andswaps the two halves randomly. For example, a random bisection cut for six cards can be written as(shuf, {id, (1 4)(2 5)(3 6)}).

3

The fourth protocol (Mizuki and Sone, 2009) and the seventh protocol (Abe et al., 2018, 2021) in
Table 1 use the random bisection cut.
The numbers of required cards of protocols typically depend on the allowed kinds of shuffles. For
example, if we are allowed to use “non-uniform shuffles,” we can construct a four-card protocol (Kochet al., 2015) as the fifth protocol in Table 1 (i.e., we do not need any helping card). A non-uniform
shuffle means (shuf, Π, F) such that the distribution F is not uniform. Similarly, a non-closed shufflemeans (shuf, Π, F) such that the set of permutations Π is not a group. As imagined, implementing
such non-uniform shuffles and/or non-closed shuffles is not easy; for instance, humans require somespecial cases to implement them. By contrast, as mentioned before, it is easy for humans to implement
the random cut.
Thus, in this study, we focus on the use of the easiest shuffle, the random cut, i.e., we deal onlywith RC-protocols.

1.3

Our Contribution

As seen in Section 1.1 and Table 1, Stiglic’s AND protocol requires eight cards, and this is the best
committed-format AND RC-protocol in terms of the number of cards; see also Table 2. Thus, since2001, it has been an open question to determine whether there exists a committed-format AND RCprotocol using less than eight cards. In this study, we will answer to the question.

Table 2: Committed-format AND RC-protocols and their numbers of shuffles
Card#Shuffles#Colors #Cards
Crépeau–Kilian, 1993 (Crépeau and Kilian, 1994)
4108 (expected)
Niemi–Renvall, 1998 (Niemi and Renvall, 1998)
2
12
7.5 (expected)
Stiglic, 2001 (Stiglic, 2001)
2
8
2 (expected)
Ours (§3)
2
62

FiniteX

That is, we propose a six-card committed-format AND RC-protocol. All the existing RC-protocols(as shown in Table 2) are not finite-runtime, that is, they are Las Vegas algorithms. By contrast, ourprotocol is finite-runtime, using exactly two random cuts, and hence, we believe that it is practical.
Note that, although this paper deals with only AND protocols, there are XOR protocols (e.g.,
Mizuki et al. (2006); Mizuki and Sone (2009); Toyoda et al. (2020)) and copy protocols (e.g., Mizuki
and Sone (2009); Nishimura et al. (2018)), which are often required when evaluating logical circuits(cf. Ono and Manabe (2020)). It should be also noted that more complex tasks, such as Millionaires’problem (e.g., Nakai et al. (2021)) and zero-knowledge proofs (e.g., Ruangwises and Itoh (2020)), canbe conducted using a deck of cards.

2

Preliminaries

In this section, we provide a basic technique used in our protocol presented later.
A rearrangement action (perm, π) results in permuting a sequence of cards according to the permutation π.
In Section 1.2, we formally defined a random
cut (shuf, RCk,n ). Here, we consider a combinationof it with rearrangement actions perm, π −1 and (perm, π) for a permutation π, namely,

−1 !
1
2
···
n
perm,
, (shuf, RC1,n ),π(1) π(2) · · · π(n)
4



1
perm,
π(1)

2
π(2)


n
.
π(n)

···
···

For simplicity of description of our protocol, we express these three actions together as one action, as
follows.
Definition 1 Let π be a permutation on {1, 2, · · · , n}, and let
σ = (π(1) π(2) · · · π(n)).
DefineRCσ = {σ i |1 5 i 5 n},and σ is called a generator. The action (shuf, RCσ ) is called a σ-random cut, sometimes denoted byσ-RC.
As mentioned above, the introductionof (shuf, RCσ ) is just for simplicity. To implement this, we
apply three actions perm, π −1 , (shuf, RC1,n ), and (perm, π). Alternatively, the following procedure
implements σ-RC with generator σ = (π(1) π(2) · · · π(n)).
1. Given a sequence of cards on the table, take the π(1)-th, π(2)-th, . . ., π(n)-th cards in this orderto make a bundle.
2. The Hindu cut (Ueda et al., 2016) is applied to the resulting card bundle. In other words, thefollowing is quickly performed a sufficient number of random times:• Take some from the bottom and put them on top.
3. From the top of the card bundle, return all cards to the π(n)-th, π(n−1)-th, . . ., π(1)-th positionsin this order.
Thus, σ-RC is implementable by the Hindu cut along with two rearrangements.

3

Proposal of Six-card Protocol

This section presents our proposed protocol using only the random cut, namely a committed-format
AND RC-protocol using six cards.
Our AND protocol proceeds, as follows.
1. Place two helping cards to the right of two input commitments and turn them over:? ? ? ? ♥ ♣ →? ? ? ? ? ?.

| {z } | {z }| {z } | {z }

a

a

b

b

2. Apply (shuf, RCσ1 ) with generator σ1 = (1 2 4 6 3 5) (denoted by h·iσ1 ) to the sequence of six
cards:

→? ? ? ? ? ?

? ? ? ? ? ?.

σ1

3. Turn over the second card. We denote this action by (turn, {2}).
(a) If ♥ appears:? ♥ ? ? ? ?,reveal the fifth card. (The probability of this ♥ appearing is 1/2.)

5

i. If ♣ appears:? ♥ ? ? ♣ ?,reveal the first card. (The probability of this ♣ appearing is 2/3.)
A. If ♣ appears, turn over all face-up cards:♣ ♥ ? ? ♣ ?

→? ? ? ? ? ?.

Apply (perm, (1 2 5 6 3 4)). Then, go to the next step (4). (The probability of this♣ appearing is 1/2.)
B. If ♥ appears, turn over all face-up cards:♥ ♥ ? ? ♣ ?

→? ? ? ? ? ?.

Apply (perm, (1 3 4)(2 6)), and go to the next step (4).
ii. If ♥ appears, turn over all face-up cards:? ♥ ? ? ♥ ? → ? ? ? ? ? ?.
Apply (perm, (2 6 5 3)), and go to the next step (4).
(b) If ♣ appears:? ♣ ? ? ? ?,reveal the sixth card. (The probability of this ♣ appearing is 1/2.)
i. If ♥ appears:? ♣ ? ? ? ♥,reveal the fourth card.
A. If ♥ appears, turn over all face-up cards:? ♣ ? ♥ ? ♥ → ? ? ? ? ? ?.
Apply (perm, (1 4 3)(2 5)), and go to the next step (4). (The probability of this ♥appearing is 1/2.)
B. If ♣ appears, turn over all face-up cards:? ♣ ? ♣ ? ♥ → ? ? ? ? ? ?.
Apply (perm, (1 4 6 5 3)), and go to the next step (4).
ii. If ♣ appears, turn over all face-up cards:? ♣ ? ? ? ♣ → ? ? ? ? ? ?.
Go to the next step (4). (The probability of this ♣ appearing is 1/3.)
4. Apply (shuf, RCσ2 ) with generator σ2 = (1 2 6 3 4 5):
→? ? ? ? ? ?

? ? ? ? ? ?.

σ2

5. Reveal the first card.
(a) If ♥ appears:♥ ? ? ? ? ?,reveal the fourth card. (The probability of this ♥ appearing is 1/2.)
6

i. When ♣ appears, the third and second cards constitute a commitment to a ∧ b:2

3

3

♥ ? ? ♣ ? ?

→

2

? ? .
| {z }
a∧b(The probability of this ♣ appearing is 2/3.)
ii. If ♥ appears, the second and fifth cards constitute a commitment to a ∧ b:2

5

♥ ? ? ♥ ? ?

2

→

5

? ? .
| {z }a∧b(b) If ♣ appears:♣ ? ? ? ? ?,reveal the sixth card.
i. If ♥ appears, the fifth and third cards constitute a commitment to a ∧ b:
3

5

♣ ? ? ? ? ♥

5

→

3

? ? .
| {z }a∧b

ii. If ♣ appears, the second and fifth cards constitute a commitment to a ∧ b:2

2

5

♣ ? ? ? ? ♣

→

5

? ? .
| {z }
a∧b

This is our six-card committed-format AND protocol that uses only two random cuts. Since theprotocol does not include any loop, it terminates with a finite number of shuffles (namely, two randomcuts).

4

Correctness and Security of Our Protocol

Our protocol can be expressed as a KWH-tree, as shown in Figure 1.
The KWH-tree (Koch et al., 2015) is a diagram representing a protocol with nodes corresponding
to “states” and edges corresponding to actions that connect them. Here, Xab represents the probability
that the input is (a, b), and we have X11 + X10 + X01 + X00 = 1. A polynomial annotating a cardsequence in a state, such as 61 (X10 + X01 ), represents the conditional probability that the current
sequence is the one next to the polynomial, given the trace of visible sequences observed so far (wherea “visible sequence” means a sequence of symbols on the faces of all lying cards on the table). When aturn action is applied, it divides a state into two states; intuitively, if the conditional probabilities are‘split’ with ’equal ratio,’ no information leaks. Formally, if the sum of probabilities in a state is equal
to X11 + X10 + X01 + X00 , then the information about input a, b is kept secret. Refer to Koch et al.
(2015); Kastner et al. (2017); Mizuki and Shizuya (2017) for more details.
The KWH-tree guarantees that our protocol is correct and secure: The bottom states tell us that theoutput commitment is correct; the sum of probabilities in every state is equal to X11 +X10 +X01 +X00 =1, meaning that the (conditional) distribution on input does not change, and hence, the protocol issecure.

7♡♣♡♣♡♣ X11♡♣♣♡♡♣ X10♣♡♡♣♡♣ X01♣♡♣♡♡♣ X00(shuf, RCσ1 )♡♣♡♣♡♣ 16 X11♡♡♣♣♡♣ 61 X11♡♡♣♡♣♣ 61 X11♣♡♣♡♣♡ 61 X11♣♣♡♡♣♡ 61 X11♣♣♡♣♡♡ 61 X11♡♣♣♡♡♣ 61 (X10 + X01 )♡♡♣♣♣♡ 61 (X10 + X01 )♣♡♡♡♣♣ 61 (X10 + X01 )♣♣♣♡♡♡ 61 (X10 + X01 )♡♣♡♣♣♡ 61 (X10 + X01 )♣♡♡♣♡♣ 61 (X10 + X01 )♣♡♣♡♡♣ 16 X00♡♣♣♡♣♡ 16 X00♣♡♡♣♣♡ 16 X00♣♣♡♡♡♣ 16 X00♡♣♣♣♡♡ 16 X00♡♡♡♣♣♣ 16 X00(turn, {2})revealed ♣♡♣♡♣♡♣ 13 X11♣♣♡♡♣♡ 31 X11♣♣♡♣♡♡ 31 X11♡♣♣♡♡♣ 31 (X10 + X01 )♣♣♣♡♡♡ 31 (X10 + X01 )♡♣♡♣♣♡ 31 (X10 + X01 )1
2

revealed ♡♡♣♣♡♣♡ 13 X00♣♣♡♡♡♣ 13 X00♡♣♣♣♡♡ 13 X00♡♡♣♣♡♣ 13 X11♡♡♣♡♣♣ 31 X11♣♡♣♡♣♡ 31 X11

12♡♡♣♣♣♡ 13 (X10 + X01 )♣♡♡♡♣♣ 13 (X10 + X01 )♣♡♡♣♡♣ 13 (X10 + X01 )(turn, {6})revealed ♡2
3(turn, {5})revealed ♣♣♣♡♡♣♡ 12 X11♣♣♡♣♡♡ 12 X11♣♣♣♡♡♡ 12 (X10 + X01 )♡♣♡♣♣♡ 21 (X10 + X01 )♡♣♣♡♣♡ 21 X00♡♣♣♣♡♡ 12 X00
1
2

revealed ♡♡♡♣♡♣♣ 12 X11♣♡♣♡♣♡ 12 X11♡♡♣♣♣♡ 12 (X10 + X01 )♣♡♡♡♣♣ 21 (X10 + X01 )♣♡♡♣♣♡ 21 X00♡♡♡♣♣♣ 12 X00♡♣♡♣♡♣ X11♡♣♣♡♡♣ X10 + X01♣♣♡♡♡♣ X00

1
2

revealed ♣♣♣♡♣♡♡ X11♡♣♡♣♣♡ X10 + X01♡♣♣♣♡♡ X00♡♡♣♣♡♣ X11♣♡♡♣♡♣ X10 + X01♣♡♣♡♡♣ X00

1
2

revealed ♡(shuf, RCσ2 ) ♣♡♣♡♣♡ X11♣♡♡♡♣♣ X10 + X01♣♡♡♣♣♡ X00

1
2♡♡♣♡♣♣ X11♡♡♣♣♣♡ X10 + X01♡♡♡♣♣♣ X00(perm, (2 6 5 3))(shuf, RCσ2 )(perm, (1 2 5 6 3 4))(perm, (1 4 6 5 3))(perm, (1 4 3)(2 5))

1
3(turn, {1})revealed ♣♣♣♡♡♣♡ X11♣♣♣♡♡♡ X10 + X01♡♣♣♡♣♡ X00

2
3

revealed ♣1
3(turn, {4})revealed ♡♣♡♣♡♡♣ 13 X00♣♡♡♣♣♡ 13 X00♡♡♡♣♣♣ 13 X00(perm, (1 3 4)(2 6))(shuf, RCσ2 )(shuf, RCσ2 )(shuf, RCσ2 )♡♡♣♡♣♣ 16 X11♡♣♡♣♡♣ 16 X11♡♣♡♣♣♡ 16 X11♣♡♡♡♣♣ 16 X11♣♡♣♣♡♡ 16 X11♣♣♣♡♡♡ 16 X11(shuf, RCσ2 )♡♡♣♣♡♣ 61 (X10 + X01 + X00 )♡♡♣♣♣♡ 61 (X10 + X01 + X00 )♡♣♣♡♡♣ 61 (X10 + X01 + X00 )♣♡♡♣♣♡ 61 (X10 + X01 + X00 )♣♣♡♡♡♣ 61 (X10 + X01 + X00 )♣♣♡♡♣♡ 61 (X10 + X01 + X00 )(turn, {1})revealed ♡♡♡♣♡♣♣ 13 X1♡♣♡♣♡♣ 13 X1♡♣♡♣♣♡ 13 X1

1
2

revealed ♣♡♡♣♣♡♣ 13 X0♡♡♣♣♣♡ 13 X0♡♣♣♡♡♣ 13 X0♣♡♡♡♣♣ 13 X1♣♡♣♣♡♡ 13 X1♣♣♣♡♡♡ 13 X1(turn, {4})revealed ♣2
3

revealed ♡
1
2 X1
1
2 X1
1
2 X0
1
2 X0

♡♣♡♣♡♣♡♣♡♣♣♡♡♡♣♣♡♣♡♡♣♣♣♡⇒ (result, 3, 2)

12♣♡♡♣♣♡ 13 X0♣♣♡♡♡♣ 13 X0♣♣♡♡♣♡ 13 X0(turn, {6})revealed ♡

1
3

2
3

revealed ♣
1
2 X1
1
2 X1
1
2 X0
1
2 X0

♣♡♣♣♡♡♣♣♣♡♡♡♣♡♡♣♣♡♣♣♡♡♣♡⇒ (result, 5, 3)♡♡♣♡♣♣ X1♡♣♣♡♡♣ X0⇒ (result, 2, 5)

13♣♡♡♡♣♣ X1♣♣♡♡♡♣ X0⇒ (result, 2, 5)

Figure 1: A KWH-tree for our 6-card committed-format AND RC-protocol

85Conclusion

In this paper, we designed a six-card committed-format AND RC-protocol. Our protocol uses only
two random cuts and we believe that it is practical.
Kastner et al. (Kastner et al., 2017) provided an impossibility result, which implies that there
exists no four-card committed-format AND RC-protocol. Thus, determining whether there is a fivecard committed-format AND RC-protocol is an interesting open problem.

References
Abe Y, Hayashi Y, Mizuki T, Sone H (2018) Five-card AND protocol in committed format using only
practical shuffles. In: Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop,
ACM, New York, NY, USA, APKC ’18, pp 3–8
Abe Y, Hayashi Y, Mizuki T, Sone H (2021) Five-card AND computations in committed format
using only uniform cyclic shuffles. New Generation Computing URL https://doi.org/10.1007/
s00354-020-00110-2
Crépeau C, Kilian J (1994) Discreet solitary games. In: Stinson DR (ed) Advances in Cryptology —CRYPTO’ 93, Springer, Berlin, Heidelberg, Lecture Notes in Computer Science, vol 773, pp 319–330
Kastner J, Koch A, Walzer S, Miyahara D, Hayashi Y, Mizuki T, Sone H (2017) The minimum numberof cards in practical card-based protocols. In: Takagi T, Peyrin T (eds) Advances in Cryptology –ASIACRYPT 2017, Springer, Cham, Lecture Notes in Computer Science, vol 10626, pp 126–155
Koch A (2018) The landscape of optimal card-based protocols. Cryptology ePrint Archive, Report
2018/951, URL https://eprint.iacr.org/2018/951
Koch A, Walzer S, Härtel K (2015) Card-based cryptographic protocols using a minimal number ofcards. In: Iwata T, Cheon JH (eds) Advances in Cryptology – ASIACRYPT 2015, Springer, Berlin,
Heidelberg, Lecture Notes in Computer Science, vol 9452, pp 783–807
Mizuki T, Shizuya H (2017) Computational model of card-based cryptographic protocols and its applications. IEICE Transactions on Fundamentals of Electronics, Communications and Computer
Sciences E100.A(1):3–11, DOI 10.1587/transfun.E100.A.3
Mizuki T, Sone H (2009) Six-card secure AND and four-card secure XOR. In: Deng X, Hopcroft JE,
Xue J (eds) Frontiers in Algorithmics, Springer, Berlin, Heidelberg, Lecture Notes in Computer
Science, vol 5598, pp 358–369
Mizuki T, Uchiike F, Sone H (2006) Securely computing XOR with 10 cards. The Australasian Journalof Combinatorics 36:279–293
Nakai T, Misawa Y, Tokushige Y, Iwamoto M, Ohta K (2021) How to solve millionaires’ problem with two kinds of cards. New Generation Computing URL https://doi.org/10.1007/
s00354-020-00118-8
Niemi V, Renvall A (1998) Secure multiparty computations without computers. Theoretical Computer
Science 191(1–2):173–183, DOI 10.1016{\slash}S0304-3975(97)00107-2
Nishimura A, Nishida T, Hayashi Y, Mizuki T, Sone H (2018) Card-based protocols using unequal
division shuffles. Soft Computing 22:361–371, DOI 10.1007/s00500-017-2858-2
Ono H, Manabe Y (2020) Card-based cryptographic logical computations using private operations.
New Generation Computing

9

Ruangwises S, Itoh T (2019) AND protocols using only uniform shuffles. In: van Bevern R, Kucherov
G (eds) Computer Science – Theory and Applications, Springer, Cham, Lecture Notes in Computer
Science, vol 11532, pp 349–358
Ruangwises S, Itoh T (2020) Physical zero-knowledge proof for Numberlink puzzle and kvertex-disjoint paths problem. New Generation Computing URL https://doi.org/10.1007/
s00354-020-00114-y
Stiglic A (2001) Computations with a deck of cards. Theoretical Computer Science 259(1–2):671–678,
DOI 10.1016{\slash}S0304-3975(00)00409-6
Toyoda K, Miyahara D, Mizuki T, Sone H (2020) Six-card finite-runtime XOR protocol with only
random cut. In: Proceedings of the 7th ACM on ASIA Public-Key Cryptography Workshop, ACM,
New York, NY, USA, APKC’20, pp 1–7
Ueda I, Nishimura A, Hayashi Y, Mizuki T, Sone H (2016) How to implement a random bisection cut.
In: Martı́n-Vide C, Mizuki T, Vega-Rodrı́guez MA (eds) Theory and Practice of Natural Computing,Springer, Cham, Lecture Notes in Computer Science, vol 10071, pp 58–69

10