Card-based Covert Lottery?
Yuto Shinoda1 , Daiki Miyahara1,4 , Kazumasa Shinagawa2,4 , Takaaki
Mizuki3 , and Hideaki Sone3
1

Graduate School of Information Sciences, Tohoku University, Sendai, Japan
2
The University of Electro-Communications, Tokyo, Japan
3
Cyberscience Center, Tohoku University, Sendai, Japan
4
National Institute of Advanced Industrial Science and Technology, Tokyo, Japan

Abstract. Before starting to play a two-player board game such as
Chess and Shogi (namely, Japanese chess), we have to determine who
makes the first move. Players’ strategies of Chess and Shogi often rely
on whether they will move first or not, and most players have their own
preferences. Therefore, it would be nice if we can take their individual
requests into account when determining who goes first. To this end, if
the two players simply tell their preferable moves to each other, they
will notice the other’s strategy. Thus, we want the players to determine
the first move according to their requests while hiding any information
about them. Note that this problem cannot be solved by a typical way
done in Chess, namely, a coin-flipping. In this paper, we formalize thisproblem in a cryptographic perspective and propose a secure protocolthat solves this problem using a deck of physical cards. Moreover, we
extend this problem to the multi-player setting: Assume that there is asingle prize in a lottery drawing among more than two players, each of
who has an individual secret feeling ‘Yes’ or ‘No’ that indicates whether
he/she really wants to get the prize or not. If one or more players have
‘Yes,’ we want to randomly and covertly choose a winner among thosehaving ‘Yes.’ If all of them have ‘No,’ we want to randomly pick a winneramong all the players. We solve this extended problem, which we call the“covert lottery” problem, by proposing a simple card-based protocol.
Keywords: Secure multiparty computations · Physical cryptography· Card-based protocols · Real-life hands-on cryptography · Deck of
cards

1

Introduction

Consider a situation where two players are about to play Chess or Shogi (namely,
Japanese chess); then, they have to determine who makes the first move. In thiscase, one typical way is to flip a coin, i.e., to randomly choose a player whogoes first. Another way is to use Rock paper scissors to choose a player who
has a right to determine whether he/she makes the first move or not as he/she?

This paper appears in Proceedings of SecITC 2020. The final authenticated version
is available online at https://doi.org/10.1007/978-3-030-69255-1_17.

2

Y. Shinoda et al.

likes. On the other hand, in Chess or Shogi, there are many players’ strategies
depending on whether they make the first move or the second move. Therefore,
they want to take their favorite turn, which implies that coin flipping is not an
ideal method (because their preferable choices are not taken into account at all).
In addition, since individual players tend to have their own preferences aboutsuch first-move-oriented or second-move-oriented strategies, they do not want
to give out the information of the move they want to take, which implies thatRock paper scissors is not an ideal method as well (because the choice of thewinner of Rock paper scissors results in possibly giving out his/her strategy tothe opponent). Thus, we need a more intellectual way to determine who goesfirst while keeping their preferences secret and taking them into account as muchas possible.
More specifically, we want to have a protocol to perform the following: If two
players’ preferences are different, i.e., one wants to make the first move while
the other wants to make the second move, then the protocol is supposed to tell
the players that the former should go first; if their preferences coincide, then the
protocol randomly chooses one of the two players and tells the result. In thispaper, we will construct such a protocol to solve the “Chess player’s dilemma”
mentioned thus far.
1.1

Defining the Functionality for Two Players

Now we formally define the functionality that we wish to achieve.
Suppose that two players P1 and P2 have secret input bits x1 , x2 ∈ {0, 1}that represent their preferences, respectively. That is, for each player Pi , xi = 1
means that he/she wants to play the first move and xi = 0 means that he/shewants to play the second move. For an input (x1 , x2 ), the functionality F outputs
a single bit y ∈ {0, 1}. The output bit y is determined as follows. If x1 6= x2 , i.e.,they have different preferences, then y is equal to x1 which means that P1 (andalso P2 ) gets his/her preferred move. On the other hand, if x1 = x2 , i.e., they
have the same preference, then y is chosen uniformly randomly. Thus, F = 1
means that P1 is going to make the first move, and F = 0 means that P2 isgoing to make the first move.
The functionality F is also expressed as follows:(x1
if x1 6= x2 ,F(x1 , x2 ) :=(1)$i←
− {0, 1} if x1 = x2 .
$Here, ←
− represents that the left element is randomly chosen from the right set.
We note that a player who fails to take the desired move will know that it is
the case of x1 = x2 . For example, when both players wish to take the first move
but P1 fails to take the first move (by the outcome of the random choice of F), P1
will know that P2 also wishes to take the first move while P2 cannot distinguishwhether x1 = x2 or not. At a first glance, it seems unfair. However, we believethat this is unavoidable since when both players have the same preference, thebest way is to play a coin tossing.

Card-based Covert Lottery

1.2

3

Defining the Functionality for Multiple Players

We moreover consider the case where the number of players is further extended
to a general number of n (≥ 2). Specifically, consider the case where only one
person is drawn from n players. For example, assume that there is a single prize
in a lottery drawing among n players, each of who has an individual secret feeling‘Yes’ or ‘No’ that indicates whether he/she really wants to get the prize or not.
If one or more players have ‘Yes,’ we want to randomly and covertly choose awinner among those having ‘Yes.’ If all of them have ‘No,’ we want to randomly
pick a winner among all the players. We call this extended problem the “covert
lottery” problem.
Considering n players, each player Pi , 1 ≤ i ≤ n, has a secret input bitxi ∈ {0, 1} that represents a wish. That is, xi = 0 means that Pi does not want
to be the winner, and xi = 1 means that he/she wants to be the winner. First,
the function True : {0, 1}n → 2{1,2,...,n} is defined as:True(x1 , x2 , . . . , xn ) := {i | xi = 1, 1 ≤ i ≤ n},(2)

where 2{1,2,...,n} is the power set of {1, 2, . . . , n}. The functionality Gn for thecovert lottery protocol is defined as follows:( $i←− True(x1 , . . . , xn ) if True(x1 , . . . , xn ) 6= ∅,Gn (x1 , . . . , xn ) :=(3)$i←
− {1, 2, . . . , n}otherwise.
Recall that, basically, we want to draw a lottery among players Pi with xi = 1,
and if there is no such player, a winner is randomly chosen from all players.
This functionality leaks to a player Pi who has xi = 1 and Gn 6= i the factthat xGn = 1. Also, if xi = 0 and Gn = i, this problem will leak to Pi thefact that all players Pj with j 6= i also have xj = 0. However, this property isinherently owned by Gn , as well.
Let us show that Gn is a natural extension of F defined in Eq. (1). Con$sider the case where n = 2 for Gn . In this case, it is obvious that G2 (0, 0) ←−${1, 2}, G2 (1, 1) ←− True(1, 1) = {1, 2}, G2 (1, 0) = 1 and G2 (0, 1) = 2. Thus, G2
and F are essentially the same, although the formats of output are different.
Therefore, Gn is a generalization of F.
1.3

Contribution

In this paper, we propose a card-based protocol for realizing the above-mentionedfunctionality F. In particular, we construct a secure protocol for deciding thefirst move using a deck of physical cards. Our protocol uses only four cards andone shuffle, and its procedure is very simple.
We moreover construct a covert lottery protocol to realize the functionality
Gn by applying the six-card AND protocol [21]. As will be explained in moredetails later, the proposed protocol makes use of the extra card sequence that is
not used as output in the six-card AND protocol [21].

4

1.4

Y. Shinoda et al.

Related Work

Card-based cryptography provides ways for secure multi-party computations using a deck of physical cards, and various protocols and their computation models
have been proposed (e.g., [10–12,19,20,27,28,35]) since the seminal work of Den
Boer [4] in 1989. Some specific applications are three-input majority voting protocols [23, 25, 38, 39], which output a majority vote for or against three participants while keeping their input secret, millionaire protocols [14,24,26], which secretly compare who has the largest amount of money, ranking protocols [33, 34],
which output the rich list without revealing each amount of money, a secretgrouping protocol [8], which classifies players into groups, and zero-knowledge
proof protocols (e.g., [2, 5, 7, 13, 15, 16, 29–31]), which prove the existence of asolution to a puzzle instance without revealing the solution itself.
In addition to using a deck of cards, cryptographic protocols based on various
kinds of physical tools have been proposed (e.g., [1, 3, 6, 18, 22]).

2

Preliminary

In this section, we introduce basic primitives used in our protocols. In Section 2.1,
we define a deck of cards. In Sections 2.2 and 2.3, we present two shuffles, therandom bisection cut and the pile-scramble shuffle. In Section 2.4, we introduce
the existing six-card AND protocol.

2.1

Deck of Cards

We assume that the face of cards is either ♣ or ♥ and that their back sides are
the same ? . All cards having the same face are assumed to be indistinguishable.
We call those cards of two suits binary cards. A deck of binary cards is used in
our protocol presented in Section 3.
Using two cards ♣ and ♥ , a single bit of information is encoded as follows:♣ ♥ = 0,♥ ♣ = 1.

A pair of face-down cards ? ? is called a commitment to x ∈ {0, 1} if it encodes
the value x according to the above encoding rule. It is denoted by? ? .
| {z }x

We also use another type of cards called number cards. The face of eachnumber card has a positive integer like 1 2 · · · m and their back sides are thesame ? as binary cards. A deck having both binary cards and number cards isused in our protocol presented in Section 4.

Card-based Covert Lottery

2.2

5

Random Bisection Cut

A random bisection cut [21] is a shuffle operation, which is applicable to a sequence having an even number of cards. A random bisection cut for 2m cards
proceeds as follows. First, it bisects the sequence into the left m cards and theright m cards. Then, it randomly swaps the left and right piles. As a result, asequence of 2m cards (indistinguishable to the original sequence) is obtained.
The following is an example of applying a random bisection cut to two commitments a, b ∈ {0, 1}. First, it bisects a sequence of cards into two piles of cards
having the same number of cards. In this example, a sequence of four cards isdivided into commitments to a and b:? ? ? ? .
| {z } | {z }abNext, the left and right piles are swapped randomly. This results in two commitments to (a, b) or (b, a) with a probability of 1/2. Hereinafter, we denote a
random bisection cut by [ · | · ] as follows:hi→ ? ? ? ? .
? ?
? ?
Ueda et al. [36, 37] showed how to securely implement a random bisection
cut. According to their experiments, a random bisection cut can be implemented
so that nobody knows whether two piles are swapped or not.
2.3

Pile-scramble Shuffle

A pile-scramble shuffle [9] is a shuffle operation, which is applicable to a sequence of mk cards for some positive integers m and k. A pile-scramble shuffle
for m piles proceeds as follows. First, it splits a sequence of mk cards into mpiles (pile1 , pile2 , . . . , pilem ) each having k cards. Then it randomly permutes them piles. As a result, a sequence of m piles (pileπ−1 (1) , pileπ−1 (2) , . . . , pileπ−1 (m) )is obtained where π is a random permutation. A pile-scramble shuffle can be
securely implemented by the use of everyday objects such as envelopes.
2.4

Six-card AND Protocol

Mizuki and Sone [21] designed a six-card AND protocol. It takes two commitments to a, b ∈ {0, 1} along with two additional helping cards ♣ ♥ and outputs
a commitment to a ∧ b as follows:? ? ? ? ♣ ♥ → ? ? .
| {z } | {z }| {z }aba∧b

The protocol proceeds as follows.
1. Place two commitments to a, b ∈ {0, 1} and two binary cards ♣ ♥ as:6

Y. Shinoda et al.

? ? ? ? ? ? .
| {z } | {z } | {z }a0b2. Rearrange the sequence as:? ? ? ? ? ?
HHjH? ? ? ? ? ? .
3. Apply a random bisection cut to the sequence as:hi→ ? ? ? ? ? ? .
? ? ?
? ? ?
4. Rearrange the sequence as:? ? ? ? ? ?

@

@
R
@
R
@


? ? ? ? ? ?

.

5. Turn over the leftmost two cards. If they are ♣ ♥ , the middle pair is acommitment to a ∧ b. Otherwise, the right pair is a commitment to a ∧ b.
The other pair is a commitment to a ∧ b in both cases.
(i) ♣ ♥ ? ? ? ?
| {z } | {z }
a∧b

3

a∧b

(ii) ♥ ♣ ? ? ? ? .
| {z } | {z }
a∧b

a∧b

A Secure Protocol for Deciding the First TurnIn this section, we design a secure protocol for deciding the first turn. That is, ourprotocol should realize the functionality F defined in Eq. (1) in Section 1.1. The
protocol takes input commitments to x1 , x2 ∈ {0, 1}, and outputs a commitment
to F(x1 , x2 ) which designates whether the first player P1 takes the first move ornot, as follows:? ? ? ? → ? ? .
| {z } | {z }| {z }x1

x2

F (x1 ,x2 )In Section 3.1, we explain the idea behind constructing our protocol. In Section 3.2, we give the protocol construction.
3.1

Idea

First, note that when x1 6= x2 , we have x1 = x2 ; when x1 = x2 , we have
{x1 , x2 } = {0, 1}. Then, using x2 , Equation (1) is rewritten as(
x1 = x2
if x1 6= x2 ,F(x1 , x2 ) =(4)$i←− {x1 , x2 } if x1 = x2 .

Card-based Covert Lottery7$− {x1 , x2 } always satisfies r = x1 = x2 . Therefore, instead ofIf x1 = x2 , r ←Equation (4), we can simply write$

F(x1 , x2 ) = r ←− {x1 , x2 }.

(5)

Therefore, if we have the following two commitments, it suffices to randomly
choose one of them without knowing which is which:? ? ? ? .
| {z } | {z }x1x2This can be done with a random bisection cut, as seen in the next subsection.

3.2

Description

Our protocol for performing the functionality F proceeds as follows.
1. Place two commitments to x1 , x2 ∈ {0, 1} where xi is Pi ’s preference:? ? ? ? .
| {z } | {z }x1x2

2. Apply the NOT computation to the commitment to x2 by swapping the two
cards:? ? ? ? → ? ?
| {z } | {z }x1x2

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

3. Apply a random bisection cut:hi
→ ? ? ? ? or ? ? ? ? .
? ? ? ? →? ?
? ?
| {z } | {z }| {z } | {z }| {z } | {z }
x1

x1

x2

x2

x2

x1

4. The left commitment is a commitment to F:? ? ? ? .
| {z }
F

Thus, our protocol surely follows Equation (5), implying that it realizes F.
Our protocol uses only four cards and one random bisection cut, and is very
simple.
Instead of applying a random bisection cut to the four cards in Step 3, we
may apply it to the first and third cards; in this case, the result will be obtained
based on the encoding ♣ = 0 and ♥ = 1.

84

Y. Shinoda et al.

Covert Lottery Protocol

In this section, we extend our protocol shown in the previous section: We propose
a card-base covert lottery protocol that realizes Gn . We first present the idea
behind this protocol and then show its description. Our proposed protocol takes
as input n commitments to x1 , x2 , . . . , xn (each of which represents player’s
preference) along with four binary cards and n number cards, and outputs asingle number card that represents a winner w = Gn (x1 , x2 , . . . , xn ):? ? ? ? ... ? ? ♣ ♣ ♥ ♥ 1 2 ... n → w .
| {z } | {z }| {z }x1

x2

xn

In Section 4.1, we explain the idea behind this protocol. In Section 4.2, weshow the protocol construction completely.
4.1

Idea

Let us look back at Equation (3). To realize Gn , it suffices to randomly choose
a single player from the set True(x1 , x2 , . . . , xn ) if there are players who arepositive to get the prize; otherwise, it suffices to randomly choose a single playerfrom the set of all players {1, 2, . . . , n}. To accomplish this, we first apply a pilescramble shuffle to the n input commitments x1 , x2 , . . . , xn to make the order ofthe inputs random. To keep track of correspondence between inputs and players,
a number card i is attached to each commitment xi , 1 ≤ i ≤ n, before applying
a pile-scramble shuffle:n
1
2? ? ? ? ... ? ? → ? ? ? ? ... ? ? .
| {z } | {z }| {z }| {z } | {z }| {z }
x1

x2

xn

x1

x2

xn

That is, the resulting sequence of cards after a pile-scramble shuffle is as follows:12n

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

n

1
2
?
?
?
? ? ? ? ... ? ? → ? ? ? ? ... ? ? ,| {z } | {z }| {z }| {z } | {z }| {z }
x1

x2

xn

X1

X2

Xn

where (X1 , X2 , . . . , Xn ) is generated by permuting (x1 , x2 , . . . , xn ) with a random permutation π.
If we turn over the commitments to X1 , X2 , . . . , Xn one by one from left toright, the first revealed commitment to 1 deserves a randomly chosen commitment from the set True(x1 , x2 , . . . , xn ) due to the pile-scramble shuffle. Thus, itsuffices to output the number card attached to it as the winner. If X1 = · · · =
Xn = 0, then it suffices to output the rightmost number card as a randomly
chosen winner from all players. We construct the protocol based on this principle. However, of course, if we simply reveal the commitments to X1 , X2 , . . . , Xn

Card-based Covert Lottery

9

Table 1. The resulting yi and token t where (X1 , X2 , . . . , X5 ) = (0, 1, 0, 1, 1).
i

Xi

t

yi = Xi ∧ tt := Xi ∧ t

1

♣ ♥

♥ ♣

♣ ♥

♥ ♣

2

♥ ♣

♥ ♣

♥ ♣

♣ ♥

3

♣ ♥

♣ ♥

♣ ♥

♣ ♥

4

♥ ♣

♣ ♥

♣ ♥

♣ ♥

5

♥ ♣

♣ ♥

♣ ♥ (= t)-

one by one, information about the input value of the winner and the number of
0s among (a part of) the inputs would be leaked. For example, let n = 5 and(X1 , X2 , X3 , X4 , X5 ) = (0, 0, 1, 0, 1). In this case, X1 , X2 , and X3 are revealed,
and hence, all players learn that at least two players’ inputs are 0s and thewinner’s input is 1. Let the inputs be (0, 0, 0, 0, 0) for another example. In thiscase, all players learn that all the inputs are 0s. To avoid this leakage, we shallperform the above computation while keeping the input values secret.
For this, we introduce a “token” commitment. A token is used to rewrite
each input commitment. That is, the winner is determined by making all of thecommitments correspond to 0s except for the first revealed commitment to 1.
Specifically, we repeatedly perform an AND computation of an input commitment (from left to right) and the token whose initial value is 1, and replace theinput commitment with the output of the AND computation (namely, it outputs
1 if and only if both the input and token are 1s). The token should remain 1
until the AND computation first outputs 1, and be 0 after it outputs 1. This
computation is accomplished by performing the AND computation of the token
and the negation of each input. To summarize, given an i-th input commitment
to Xi and the token commitment to t, we perform the following computation
and replace the i-th input commitment with a commitment to yi = Xi ∧ t andthe token commitment is updated by t := Xi ∧ t (1 ≤ i ≤ n − 1):? ? ? ? → ? ? ? ? ,| {z } | {z }| {z } | {z }
Xi

t

Xi ∧t

(6)

Xi ∧t

where the initial value of the token is t = 1. The n-th commitment is replacedwith the final token.
Let us take an example. Consider the case where (X1 , X2 , . . . , X5 ) = (0, 1, 0, 1, 1).
In this case, yi and t change depending on Xi and t, as shown in Table 1. First,
since X1 = 0, we have y1 = 0 ∧ 1 = 0 and t := 0 ∧ 1 = 1. Since X2 = 1,y2 = 1 ∧ 1 = 1, we have t := 1 ∧ 1 = 0. Since yi = Xi ∧ t and t := Xi ∧ t, once
the token t becomes 0, all of the remaining AND computations shall output 0s
as shown in Table 1.

10

Y. Shinoda et al.

To perform (6), it suffices to use the six-card AND protocol [21]; thus, we
can implement a card-based covert lottery protocol by using the six-card AND
protocol n−1 times. As mentioned above, we set the final commitment to yn = t.
If X1 , . . . , Xn−1 are all 0s, we have t = 1, and hence, yn = 1. If there is at least
1 among X1 , . . . , Xn−1 , we have t = 0, and hence, yn = 0. Note that, aside fromn input commitments, we use four binary cards for the token and the helping
cards in the six-card AND protocol.
4.2

Description

The description of our proposed protocol is as follows.
1. Each player secretly creates an input commitment; we now have n input
commitments as follows:? ? ? ? ... ? ? .
| {z } | {z }| {z }
x1x2

xn

2. Place a number card i above each commitment to xi and make n piles ofcards consisting of three cards:
1n2? ? ? ? ... ? ? .
| {z } | {z }| {z }
x1x2

xn

3. Turn over every number card and apply a pile-scramble shuffle to the sequence of piles:
1

2

n

x1

x2

xn

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

X2

Xn

Let X1 , X2 , . . . , Xn ∈ {0, 1} be the values of the resulting commitments after
the shuffle.
4. Using a pair of free binary cards, make a commitment to t = 1 by placing♥ ♣ and turning them over.
5. Let j = 1. Perform the following computation n − 1 times.
(a) Taking as input the commitment to Xj and the token commitment to t,
perform the six-card AND protocol [21] along with the remaining pairof free cards ♣ ♥ to obtain the following two commitments:? ? ? ? ♣ ♥ → ? ? ? ? ♣ ♥.
| {z } | {z }| {z } | {z }
Xj

t

Xj ∧t

Xj ∧t

Place the former commitment to yi = Xj ∧ t below the number cardas the commitment to Xj was there. Let the latter commitment be thenext token t. Note that the two face-up cards ♣ ♥ that were revealed
to determine the output can be reused in the next AND computation.

Card-based Covert Lottery

11

6. Let the commitment to t be a commitment to yn .
7. Apply a pile-scramble shuffle again to the sequence of n piles, each of which
consists of the commitment to yi and a number card:
?

?

?

?

?

?

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

y2

yn

Y1

Y2

Yn

Let Y1 , Y2 , . . . , Yn ∈ {0, 1} be the values of the resulting commitments after
the shuffle.
8. Turn over the commitments to Y1 , Y2 , . . . , Yn ; there should be exactly one
commitment to 1. Then, turn over the number card above it. We have thewinner represented by the revealed number card.
4.3

Security

We claim that all face-up symbols opened in an execution of the protocol areuniformly randomly and independently distributed from the inputs and output.
Face-down cards are opened in Steps 5(a) and 8 only. In Step 5(a), two cards
are opened by the six-card AND protocol. From the security of the six-card
AND protocol, these symbols are distributed uniformly randomly and independently from any other values. In Step 8, the commitments to Y1 , Y2 , . . . , Yn are
opened. We note that only a single Yi is a commitment to 1 and the others arecommitments to 0. From the property of the pile-scramble shuffle, the number i
is distributed uniformly randomly among {1, 2, . . . , n} and independently fromany other values. Therefore, all face-up symbols are uniformly randomly andindependently distributed from the inputs and output.

5

Conclusion

In this paper, we formalized a novel problem that determines who makes thefirst move in a two-player board game such as Chess and Shogi, and designed
a card-based protocol to solve this problem. Instead of randomly deciding thefirst move by a coin tossing, our protocol takes into account players’ preferences.
Moreover, we generalized the problem into a multi-player case, and designed a“covert lottery protocol” to solve the problem.
We left to reduce the number of cards and the number of shuffles as anopen problem. In card-based cryptography, they are considered to be the mostimportant complexity measures. Our two-player protocol requires four cards andone shuffle. Our multi-player protocol requires 3n+4 cards and n+1 shuffles.1 We
note that it is possible to reduce the number of shuffles by applying the techniqueof the card-based garbled circuits [32]. However, in general, it is difficult to reduce
both the number of cards and the number of shuffles at the same time.
1

If we make Xn be two free cards by a random bisection cut before Step 4, the numberof cards can be reduced to 3n + 2 while the number of shuffles becomes n + 2. If weapply the AND protocol based on the encode ♣ = 0 and ♥ = 1 [17], we can havea (3n + 1)-card 3n-shuffle protocol or a 3n-card (3n + 1)-shuffle protocol.

12

Y. Shinoda et al.

Another interesting problem is to consider a different problem similar to thecovert lottery protocol. For example, it is possible to generalize the covert lottery
protocol into a protocol with multiple winners although our protocol has a single
winner. As another example, since the covert lottery protocol can be viewed as
an election with candidacies, it would be worthwhile to consider a protocol for
an election that allows for nominations.
Acknowledgements. We thank the anonymous referees, whose comments havehelped us to improve the presentation of the paper. We thank the anonymous reviewer at some conference who have inspired us to present the protocol shown in
Section 3. This work was supported in part by JSPS KAKENHI Grant Numbers
JP19J21153 and JP20J01192.

References
1. Abe, Y., Iwamoto, M., Ohta, K.: Efficient private PEZ protocols for symmetric functions. In: Hofheinz, D., Rosen, A. (eds.) Theory of Cryptography. LNCS,
vol. 11891, pp. 372–392. Springer, Cham (2019), https://doi.org/10.1007/
978-3-030-36030-6_15
2. Bultel, X., Dreier, J., Dumas, J., Lafourcade, P., Miyahara, D., Mizuki, T., Nagao,
A., Sasaki, T., Shinagawa, K., Sone, H.: Physical zero-knowledge proof for Makaro.
In: Stabilization, Safety, and Security of Distributed Systems. LNCS, vol. 11201,
pp. 111–125 (2018), https://doi.org/10.1007/978-3-030-03232-6_8
3. Costiuc, M., MaimuŢ, D., Teşeleanu, G.: Physical cryptography. In: Simion, E.,
Géraud-Stewart, R. (eds.) Innovative Security Solutions for Information Technology and Communications. LNCS, vol. 12001, pp. 156–171. Springer, Cham (2020),
https://doi.org/10.1007/978-3-030-41025-4_11
4. Den Boer, B.: More efficient match-making and satisfiability the five card trick. In:
Quisquater, J.J., Vandewalle, J. (eds.) Advances in Cryptology—EUROCRYPT’89. LNCS, vol. 434, pp. 208–217. Springer, Berlin, Heidelberg (1990), https://doi.org/10.1007/3-540-46885-4_23
5. Dumas, J.G., Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: Interactive physical zero-knowledge proof for Norinori. In: Du, D.Z., Duan, Z., Tian,
C. (eds.) Computing and Combinatorics. LNCS, vol. 11653, pp. 166–177. Springer,
Cham (2019), https://doi.org/10.1007/978-3-030-26176-4_14
6. Fagin, R., Naor, M., Winkler, P.: Comparing information without leaking it. Commun. ACM 39(5), 77–85 (1996), https://doi.acm.org/10.1145/229459.229469
7. Gradwohl, R., Naor, M., Pinkas, B., Rothblum, G.N.: Cryptographic andphysical zero-knowledge proof systems for solutions of Sudoku puzzles. Theory of Computing Systems 44(2), 245–268 (2009), https://doi.org/10.1007/
s00224-008-9119-9
8. Hashimoto, Y., Shinagawa, K., Nuida, K., Inamura, M., Hanaoka, G.: Securegrouping protocol using a deck of cards. In: Shikata, J. (ed.) Information Theoretic Security. LNCS, vol. 10681, pp. 135–152. Springer, Cham (2017), https://doi.org/10.1007/978-3-319-72089-0_8
9. Ishikawa, R., Chida, E., Mizuki, T.: Efficient card-based protocols for generating a hidden random permutation without fixed points. In: Calude, C.S.,

Card-based Covert Lottery

13

Dinneen, M.J. (eds.) Unconventional Computation and Natural Computation.
LNCS, vol. 9252, pp. 215–226. Springer, Cham (2015), https://doi.org/10.1007/
978-3-319-21819-9_16
10. Kastner, J., Koch, A., Walzer, S., Miyahara, D., Hayashi, Y., Mizuki, T., Sone,
H.: The minimum number of cards in practical card-based protocols. In: Takagi, T., Peyrin, T. (eds.) Advances in Cryptology—ASIACRYPT 2017. LNCS,
vol. 10626, pp. 126–155. Springer, Cham (2017), https://doi.org/10.1007/
978-3-319-70700-6_5
11. 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
12. Koch, A., Walzer, S.: Foundations for actively secure card-based cryptography. In:
Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) Fun with Algorithms. Leibniz International Proceedings in Informatics (LIPIcs), vol. 157, pp. 17:1–17:23.
Schloss Dagstuhl, Dagstuhl, Germany (2020), https://doi.org/10.4230/LIPIcs.
FUN.2021.17
13. Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: A physical ZKP
for Slitherlink: How to perform physical topology-preserving computation. In:
Heng, S.H., Lopez, J. (eds.) Information Security Practice and Experience. LNCS,
vol. 11879, pp. 135–151. Springer, Cham (2019), https://doi.org/10.1007/
978-3-030-34339-2_8
14. Miyahara, D., ichi 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
15. Miyahara, D., Robert, L., Lafourcade, P., Takeshige, S., Mizuki, T., Shinagawa,
K., Nagao, A., Sone, H.: Card-based ZKP protocols for Takuzu and Juosan. In:
Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) Fun with Algorithms. Leibniz International Proceedings in Informatics (LIPIcs), vol. 157, pp. 20:1–20:21.
Schloss Dagstuhl, Dagstuhl, Germany (2020), https://doi.org/10.4230/LIPIcs.
FUN.2021.20
16. Miyahara, D., Sasaki, T., Mizuki, T., Sone, H.: Card-based physical zero-knowledge
proof for Kakuro. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 102(9),1072–1078 (2019), https://doi.org/10.1587/transfun.E102.A.1072
17. Mizuki, T.: Card-based protocols for securely computing the conjunction of multiple variables. Theor. Comput. Sci. 622(C), 34–44 (2016), https://doi.org/10.
1016/j.tcs.2016.01.039
18. Mizuki, T., Kugimoto, Y., Sone, H.: Secure multiparty computations using the
15 puzzle. In: Dress, A., Xu, Y., Zhu, B. (eds.) Combinatorial Optimization andApplications. LNCS, vol. 4616, pp. 255–266. Springer, Berlin, Heidelberg (2007),https://doi.org/10.1007/978-3-540-73556-4_28
19. 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
20. Mizuki, T., Shizuya, H.: Computational model of card-based cryptographic protocols and its applications. IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
E100.A(1), 3–11 (2017), https://doi.org/10.1587/transfun.E100.A.3
21. 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

14

Y. Shinoda et al.

22. Murata, S., Miyahara, D., Mizuki, T., Sone, H.: Public-PEZ cryptography. In:
Susilo, W., Deng, R.H., Guo, F., Li, Y., Intan, R. (eds.) Information Security.
LNCS, vol. 12472, pp. 59–74. Springer, Cham (2020), https://doi.org/10.1007/
978-3-030-62974-8_4
23. Nakai, T., Shirouchi, S., Iwamoto, M., Ohta, K.: Four cards are sufficient for acard-based three-input voting protocol utilizing private permutations. In: Shikata,J. (ed.) Information Theoretic Security. LNCS, vol. 10681, pp. 153–165. Springer,
Cham (2017), https://doi.org/10.1007/978-3-319-72089-0_9
24. Nakai, T., Tokushige, Y., Misawa, Y., Iwamoto, M., Ohta, K.: Efficient cardbased cryptographic protocols for millionaires’ problem utilizing private permutations. In: Foresti, S., Persiano, G. (eds.) Cryptology and Network Security.
LNCS, vol. 10052, pp. 500–517. Springer, Cham (2016), https://doi.org/10.
1007/978-3-319-48965-0_30
25. Nishida, T., Hayashi, Y., Mizuki, T., Sone, H.: Securely computing three-input
functions with eight cards. IEICE Trans. Fundam. Electron. Commun. Comput.
Sci. E98.A(6), 1145–1152 (2015), https://doi.org/10.1587/transfun.E98.A.
1145
26. Ono, H., Manabe, Y.: Efficient card-based cryptographic protocols for the millionaires’ problem using private input operations. In: Asia Joint Conference on
Information Security (AsiaJCIS). pp. 23–28 (2018), https://doi.org/10.1109/
AsiaJCIS.2018.00013
27. Ono, H., Manabe, Y.: Card-based cryptographic protocols with the minimum number of rounds using private operations. In: Pérez-Solà, C., Navarro-Arribas, G.,
Biryukov, A., Garcia-Alfaro, J. (eds.) Data Privacy Management, Cryptocurrencies and Blockchain Technology. LNCS, vol. 11737, pp. 156–173. Springer, Cham(2019), https://doi.org/10.1007/978-3-030-31500-9_10
28. 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
29. Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Physical zero-knowledge
proof for Suguru puzzle. In: Devismes, S., Mittal, N. (eds.) Stabilization, Safety,
and Security of Distributed Systems. LNCS, vol. 12514, pp. 235–247. Springer,
Cham (2020), https://doi.org/10.1007/978-3-030-64348-5_19
30. Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for Numberlink puzzle
and k vertex-disjoint paths problem. New Gener. Comput. 39(1), 3–17 (2021),
https://doi.org/10.1007/s00354-020-00114-y
31. Sasaki, T., Miyahara, D., Mizuki, T., Sone, H.: Efficient card-based zero-knowledge
proof for Sudoku. Theor. Comput. Sci. 839, 135–142 (2020), https://doi.org/
10.1016/j.tcs.2020.05.036
32. Shinagawa, K., Nuida, K.: A single shuffle is enough for secure card-based computation of any Boolean circuit. Discrete Applied Mathematics 289, 248–261 (2021),
https://doi.org/10.1016/j.dam.2020.10.013
33. Takashima, K., Abe, Y., Sasaki, T., Miyahara, D., Shinagawa, K., Mizuki, T., Sone,
H.: Card-based secure ranking computations. In: Li, Y., Cardei, M., Huang, Y.
(eds.) Combinatorial Optimization and Applications. LNCS, vol. 11949, pp. 461–
472. Springer, Cham (2019), https://doi.org/10.1007/978-3-030-36412-0_37
34. Takashima, K., Abe, Y., Sasaki, T., Miyahara, D., Shinagawa, K., Mizuki, T.,
Sone, H.: Card-based protocols for secure ranking computations. Theor. Comput.
Sci. 845, 122–135 (2020), https://doi.org/10.1016/j.tcs.2020.09.008

Card-based Covert Lottery

15

35. Toyoda, K., Miyahara, D., Mizuki, T., Sone, H.: Six-card finite-runtime XOR protocol with only random cut. In: Proceedings of the 7th ACM Workshop on ASIA
Public-Key Cryptography. pp. 2–8. APKC ’20, Association for Computing Machinery, New York, NY, USA (2020), https://doi.org/10.1145/3384940.3388961
36. Ueda, I., Miyahara, D., Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: Secure implementations of a random bisection cut. Int. J. Inf. Secur. 19(4), 445–452(2020), https://doi.org/10.1007/s10207-019-00463-w
37. Ueda, I., Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: How to implementa random bisection cut. In: Martín-Vide, C., Mizuki, T., Vega-Rodríguez, M.A.
(eds.) Theory and Practice of Natural Computing. LNCS, vol. 10071, pp. 58–69.
Springer, Cham (2016), https://doi.org/10.1007/978-3-319-49001-4_5
38. Watanabe, Y., Kuroki, Y., Suzuki, S., Koga, Y., Iwamoto, M., Ohta, K.: Card-based
majority voting protocols with three inputs using three cards. In: 2018 International
Symposium on Information Theory and Its Applications (ISITA). pp. 218–222(2018), https://doi.org/10.23919/ISITA.2018.8664324
39. Yasunaga, K.: Practical card-based protocol for three-input majority. IEICE Trans.
Fundam. Electron. Commun. Comput. Sci. E103.A(11), 1296–1298 (2020), https://doi.org/10.1587/transfun.2020EAL2025