Cooking Cryptographers: Secure Multiparty
Computation Based on Balls and Bags
Daiki Miyahara

Yuichi Komano

Takaaki Mizuki

Hideaki Sone

Cyberscience Center,
Tohoku University
Sendai, Japan
National Institute of Advanced
Industrial Science and Technology
Tokyo, Japan

Corporate R&D Center,Toshiba Corporation
Kawasaki, Japan

Cyberscience Center,
Tohoku University
Sendai, Japan
National Institute of Advanced
Industrial Science and Technology
Tokyo, Japan

Cyberscience Center,
Tohoku University
Sendai, Japan

Abstract—Imagine two cryptographers wishing to securely
compute the AND value of their secret input bits. They arein the kitchen, where all they have are three saucepans with
Borscht soup and some kinds of ingredients. Interestingly, bysecretly putting ingredients in the saucepans depending on their
inputs, they can find only the AND value from the taste of thecooked Borscht. Because cooking for secure computations is not
so convenient, let us regard ingredients and saucepans (with
Borscht soup) as balls and bags, respectively, which are easy
to handle and also familiar tools for learning Probability in highschool. Then, our problem is generalized as: Can we realize secure
multiparty computations (MPCs) with balls and bags?
There are techniques to realize MPCs with everyday objects,
such as physical cards, coins, and a PEZ dispenser. We encode
the input bits with such objects and securely compute somepredetermined function using them. In this paper, we present
a novel technique based on the physical properties of balls andbags. That is, our challenges are how to utilize an interesting
feature that the balls become disordered immediately after they
are put into a bag, namely they are “automatically shuffled.” Wegive the first framework of MPCs using balls and bags (namely,ball-based cryptography), and propose secure AND computationand general MPCs. Our protocols are realizations of usable
security which helps people with understanding the principlesof MPCs as well as solving social problems in daily life.
Index Terms—Secure multiparty computation, Real-life handson cryptography, Urn problem

I. Introduction
Three cryptographers are just cooking Borscht soup at the
kitchen. Each of them has brought typical ingredients for
Borscht soup such as carrots and onions. They might bepaying for the ingredients, or some of them might be funded
by NFSA (National Fictional Security Agency). The three
cryptographers respect each other’s ideology to have a relation
to NFSA, but they wonder if they eat food funded by NFSA.
All they have in the kitchen are the ingredients (namely, carrots
and onions) and saucepans with Borscht soup. Then, they© 2021 IEEE. Personal use of this material is permitted. Permission fromIEEE must be obtained for all other uses, in any current or future media,
including reprinting/republishing this material for advertising or promotional
purposes, creating new collective works, for resale or redistribution to servers
or lists, or reuse of any copyrighted component of this work in other works.
The accepted version of the article is available online at https://doi.
ieeecomputersociety.org/10.1109/CSF51468.2021.00034

decide to resolve their uncertainty by conducting a secure
AND computation with the ingredients and saucepans, to makesure whether they all paid or not. We call this the Cooking
Cryptographers Problem, which is named in honor of the
Dining Cryptographers Problem [1].
A. Cooking Cryptographers
For simplicity, let us consider the Cooking Cryptographers
Problem with two players. Assume that Alice and Bob haveprivate inputs a, b ∈ {0, 1}, respectively (the individual input
is 0 if he/she was supported by NFSA; otherwise, it is 1).
Our goal is to compute the two-input logical AND function
f (a, b) = a ∧ b without revealing any information except forthe output value. Remembering that they are in the kitchen, let
us construct a secure protocol for this function using cooking
tools and ingredients. Interestingly, we can give an exampleof the computation using two carrots, four onions, and threesaucepans, as follows.
1) There are three saucepans filled with Borscht soup
(containing no ingredient yet) on kitchen countertops aswell as two carrots and four onions on a tray. Each of
Alice and Bob picks one carrot and two onions from thetray.
2) If a = 0, Alice puts the carrot into the second saucepan
and the onions into the other saucepans privately (so thatBob cannot learn which saucepan contains the carrot).
If a = 1, she puts the carrot into the first saucepan andthe onions into the other saucepans.

The ingredients go to the bottom so that nobody sees
them directly in any saucepans.
3) If b = 0, Bob privately puts the carrot into the thirdsaucepan and the onions into the other saucepans. If
b = 1, he puts the carrot into the first saucepan and theonions into the other saucepans.

Note that the two carrots are in the same saucepan if
and only if a = b = 1.

confirm correctness and security of a protocol, we constructa diagram showing probability traces of the protocol, which
was proposed in [6] for card-based protocols. We believe thatball-based cryptography is a realization of usable security thathelps people with understanding the principles of MPCs.
C. Outline

4) Alice and Bob shuffle the three saucepans so that theresulting order of the three saucepans becomes unknown
to them.
5) After simmering the Borscht soup in the three saucepans,they enjoy eating the cooked Borscht soup in the threesaucepans; if there is a saucepan of Borscht soup onlywith carrots, we have f (a, b) = a ∧ b = 1 (meaningthat none of Alice and Bob was supported by NFSA);
otherwise, a ∧ b = 0.
B. Contribution
In this paper, we formalize the above two-party protocol
with a general setting. Because it is not so easy or realistic
to cook Borscht soup whenever people want to perform asecure computation, let us replace ingredients and saucepans(with Borscht soup) by colored balls (such as red and whiteballs) and non-transparent bags, respectively. Assume that abag possibly includes balls but the colors of the balls areinvisible from the outside. Balls and bags are easy to prepare,and they are also familiar tools for learning Probability inhigh school. Therefore, basing on balls and bags will be morehuman-friendly than cooking soup for secure computations.
Then, our problem is reformulated as: Can we realize
secure multiparty computations (MPCs) [2] with such balls
and bags? As will be reviewed in Section I-D, there are
MPC protocols with familiar tools, such as a deck of physicalcards [3]–[5]. Unlike these existing protocols, we attempt
to construct the first protocol using colored balls and bags
together with simple actions: putting balls into a bag, shufflingthe order of bags, and taking balls from a bag. Notice that,similar to ingredients in Borscht soup, balls in a bag havean interesting property that a collection of balls automatically
becomes disordered once they are put into a bag, namely
automatic shuffle.i
We positively answer the above question; we construct simple protocols to establish MPCs of the logical AND function
with more than two inputs as well as general MPCs. We also
give a formal treatment for our protocols and their security(namely, ball-based cryptography). Proposed ball-based protocols are described in both formal and informal ways. To easilyi Although we believe that this automatic shuffle works well, shaking a bag
after putting balls into it would be another way to achieve this.

The remainder of this paper is organized as follows. In
Section II, we propose ball-based cryptography by presenting
a formal treatment of protocols using balls and bags. In
Section III, we show a pseudocode of the AND protocol
with two inputs introduced in Section I-A, and then show
a diagram of the protocol, which implies correctness andsecurity of the protocol. In Section IV, we extend the twoinput AND protocol to an AND protocol with more than two
inputs. In Section V, we further extend the protocols to design
general MPCs. In Section VI, we discuss the efficiency of
our AND protocols. In Section VII, we show implementation
examples for ball-based cryptography. We conclude this workin Section VIII. In Appendix A, we show a pseudocode ofcard-based AND protocol with five cards for comparison. In
Appendix B, we introduce different kinds of balls to haveefficient protocols.
D. Related Work
Physical objects enable us to achieve cryptographic tasks,
such as MPCs [7], zero-knowledge proofs [8], polling [9], andvisual secret sharing [10]. As we perform these secure protocols by hand, their principles can be intuitively understood;
hence, they are attractive. There are several researches on thissubject (called real-life hands-on cryptography), such as a deckof playing cards [3]–[5] (known as card-based cryptography),visual secret sharing sheets [11], coins [12], and a PEZ
dispenser [13], [14]. Real-life hands-on cryptography has been
attracting many young people to the field of security andprivacy.
Physical objects are powerful so that they provide solutions
to problems in cryptographic protocols (which cannot be
solved with only computational assumptions). Using tamperevident seals [15], we can implement standard cryptographic
protocols such as coin flipping and oblivious transfer which
are universally composable. Envelopes [16] can be used to implement collusion-free protocols. The use of a ballot box [17]was considered to perform rational secure computations.
Compared with these researches, our work employs theproperty of bags (namely, automatic shuffle) and utilize simple
actions with colored balls and bags for performing MPCs.
Related to probability theory, taking a ball out of a bag inball-based cryptography can be a variant of an urn problem
by regarding a bag as an urn. An urn problem often appears inprobability theory and statistics, where a player takes one ormore balls from an urn containing some balls. Some examplesof urn problems such as binomial distribution are known.
MPCs would be included in the collection of urn problems
due to our work.

E. Comparison with Card-Based Cryptography
Among related work introduced above, card-based cryptography is the most famous topic on real-life hands-on
cryptography. We note that card-based cryptography and ballbased cryptography are different; a state of balls in a bag isdenoted by a multiset (as will be seen in Section II-A) whilea playing card is defined as a fraction to represent two statesof face-down and face-up [18].
Let us discuss the relation between them. Although it istrue that a bag containing one ball can be regarded as a facedown card, balls and bags cannot be used to implement any
card-based protocol. This is because, with balls and bags, it
seems relatively difficult to realize a cyclic shuffle, which isused in a large number of card-based protocols to cyclically
shuffle a sequence of cards. On the other hand, any ball-based
protocol can be implemented by using a deck of playing cards
because a bag containing balls can be represented by a set offace-down cards. That is, we can regard a pile of cards as abag containing balls; by completely shuffling the pile of cards,
the property of being disordered is guaranteed. For instance,
the above two-party protocol can be implemented with two red
cards and four white ones. However, such an implementation is
no longer efficient because the famous five-card trick proposed
by Den Boer [3] requires only five cards; hence, the above twoparty protocol cannot be derived from card-based protocols
and the protocol is non-trivial. From the above discussion,balls and bags approach relies on a weaker assumption thancard-based cryptography. We believe that this is an advantage
of our approach because even such a weaker setting provides
us a simple way of performing secure computations.
We emphasize that practical usability in ball-based cryptography is as high as in card-based cryptography. Let uscompare the above two-party protocol with balls and bags
and the five-card trick [3], which is the most simple cardbased protocol for computing the logical AND. As will beshown in Protocols 1 and 4, the length of the pseudocode
of our proposed protocol is almost the same as that of the
five-card trick [3]. Indeed, both protocols proceed in a similarway, i.e., two players privately input balls or cards, shuffle asequence of bags or cards, and reveal all the colors of theballs or cards. Therefore, executing our proposed protocol iseasy for laypeople, and it is a beautiful tool of pedagogicalsignificance as is the five-card trick (a case study of usingcard-based cryptography in a university lecture was reported
in [19]). Moreover, physical assumptions they use are generalin daily life; the colors of balls in a bag are assumed to
be invisible in ball-based cryptography while the colors offace-down cards are assumed to be invisible in card-based
cryptography.
Overall, ball-based cryptography will open a new vista, andwe expect that it will contribute to increasing people who areinterested in computer security and privacy.
II. Formalizing Protocols Based on Balls and Bags
In this section, we present a formal treatment of protocols
based on balls and bags by constructing a model of ball-based

secure computations. We also discuss active security of our
proposed scheme, i.e., how we should deal with malicious
players who may deviate arbitrary from a protocol.
A. Notations
Remember the AND protocol (which computes f (a, b) =a ∧ b) proposed in Section I-A. We now replace ingredientsand saucepans with balls and bags, respectively. That is, we
use two red balls, four white balls, and three bags as illustrated
in Fig. 1; this is an example of executing our AND protocol
using balls and bags when a = b = 1.
Let • and ◦ denote a red ball and a white ball, respectively.
Assume that all balls are indistinguishable except for theircolors. Seeing Fig. 1, notice that we have to consider two
kinds of multisets of balls, namely a “bag” and a “tray.” Thus,
we introduce two expressions of a multiset of balls: {{·}} isan invisible multiset representing a bag possibly containing
balls, and [·] is a visible multiset representing a tray. We
use “invisible multiset” and “bag” interchangeably; we callan invisible multiset of balls {{b1 , . . . , b` }} a bag (into whichballs are put) where b1 , . . . , b` ∈ {•, ◦} for a natural number`. Similarly, we call an visible multiset of balls [b1 , . . . , b` ] a
tray (on which balls are put).
We assume that the size of bags is suitable so that once balls
are put into a bag, the order of the balls automatically becomes
disordered. We call this property automatically shuffle. For example, {{•, ◦, •}} and {{•, •, ◦}} are indistinguishable to players.
In this paper, we write red balls first in an (in)visible multiset
to unify the notation. It is interesting that constructing MPCs
is possible even with balls and bags having such a property.
Using these notations, at the beginning of the two-party
protocol proposed in Section I-A, we have three empty bags
(invisible multisets) {{}}, {{}}, {{}} and a tray (visible multiset)[•, •, ◦, ◦, ◦, ◦] on a table. Let us describe it with a tuple:([•, •, ◦, ◦, ◦, ◦]; {{}}, {{}}, {{}}; [], [], []) .

(1)

We call this tuple a configuration. The first part of theconfiguration (before the first semi-colon) is a multiset ofavailable balls, its second part (between the first and second
semi-colons) is a sequence of bags, and its last part is asequence of trays keeping balls picked from the bags. The
last part may be omitted if there is no visible ball at that time.
Let us review the two-player protocol with these notations.
At Step 2, Alice holds one red ball and two white balls, i.e.,[•, ◦, ◦], and puts them into the three bags depending on thevalue of a; the above configuration is transformed into as
follows:([•, •, ◦, ◦, ◦, ◦]; {{}}, {{}}, {{}}; [], [], []) → ([•, ◦, ◦]; {{◦}}, {{•}}, {{◦}}; [], [], []) , ([•, ◦, ◦]; {{•}}, {{◦}}, {{◦}}; [], [], []) ,if a = 0,
if a = 1.

(2)

Fig. 1: An example of executing our ball-based AND protocol with two inputs (when a = b = 1)
At Step 3, Bob also puts balls depending on b; there are four
possibilities:([]; {{◦, ◦}}, {{•, ◦}}, {{•, ◦}}; [], [], []) ,if (a, b) = (0, 0),([]; {{•, ◦}}, {{•, ◦}}, {{◦, ◦}}; [], [], []) ,if (a, b) = (0, 1),([]; {{•, ◦}}, {{◦, ◦}}, {{•, ◦}}; [], [], []) , if (a, b) = (1, 0),([]; {{•, •}}, {{◦, ◦}}, {{◦, ◦}}; [], [], []) , if (a, b) = (1, 1).

(3)

B. Definition of Protocols

Let pi j for i, j ∈ {0, 1} represent the probability that the
input (a, b) is (i, j). Then, the first line in (3) occurs witha probability of p00 , the second line occurs with a probabilityof p01 , and so on. Therefore, we now denote the above status(3) by([]; {{◦, ◦}}, {{•, ◦}}, {{•, ◦}}; [], [], []) (p00 , 0, 0, 0),([]; {{•, ◦}}, {{•, ◦}}, {{◦, ◦}}; [], [], []) (0, p01 , 0, 0),([]; {{•, ◦}}, {{◦, ◦}}, {{•, ◦}}; [], [], []) (0, 0, p10 , 0),([]; {{•, •}}, {{◦, ◦}}, {{◦, ◦}}; [], [], []) (0, 0, 0, p11 ),(4)

where a 4-tuple (q00 , q01 , q10 , q11 ) on the right side means thatqi j is the conditional probability that (a, b) = (i, j) and thecurrent configuration is the left one.
Next, at Step 4, the three bags are shuffled; the resulting
configurations will be:([]; {{◦, ◦}}, {{•, ◦}}, {{•, ◦}}; [], [], []) ( p300 , p301 , p310 , 0),([]; {{•, ◦}}, {{•, ◦}}, {{◦, ◦}}; [], [], []) ( p300 , p301 , p310 , 0),([]; {{•, ◦}}, {{◦, ◦}}, {{•, ◦}}; [], [], []) ( p300 , p301 , p310 , 0),([]; {{•, •}}, {{◦, ◦}}, {{◦, ◦}}; [], [], []) (0, 0, 0, p311 ),(5)([]; {{◦, ◦}}, {{•, •}}, {{◦, ◦}}; [], [], []) (0, 0, 0, p311 ),([]; {{◦, ◦}}, {{◦, ◦}}, {{•, •}}; [], [], []) (0, 0, 0, p311 ).
Finally, Alice and Bob take all the balls out of the threebags; this is denoted by the last part of the configurations,
namely visible multisets, as follows:p p p
00
0110([], {{}}, {{}}, {{}}; [◦, ◦], [•, ◦], [•, ◦])p0 , p0 , p0 , 0 ,p p p
00
0110([], {{}}, {{}}, {{}}; [•, ◦], [•, ◦], [◦, ◦])p0 , p0 , p0 , 0 ,p p p
00
0110([], {{}}, {{}}, {{}}; [•, ◦], [◦, ◦], [•, ◦])
,
,
,
0
,
p0 p0 p0(6)([], {{}}, {{}}, {{}}; [•, •], [◦, ◦], [◦, ◦]) (0, 0, 0, 1),([], {{}}, {{}}, {{}}; [◦, ◦], [•, •], [◦, ◦]) (0, 0, 0, 1),([], {{}}, {{}}, {{}}; [◦, ◦], [◦, ◦], [•, •]) (0, 0, 0, 1),

where p0 = p00 + p01 + p10 . The last part of the configurations,
i.e., balls picked from each bag, tells us that the AND valuea∧b is obtained depending on whether two red balls are takenfrom the same bag or not and that no information except for the
output is leaked (see Section III for more rigorous discussion).

Let us introduce a formal definition of protocols based onballs and bags.
Before going into the details, we first introduce extended
operations for a sequence of multisets. Let X = (X1 , . . . , Xk )and Y = (Y1 , . . . , Yk ) be sequences of multisets of the samelength k. We define the following two operations: X ∪ Y B(X1 ∪ Y1 , . . . , Xk ∪ Yk ) and union(X) B X1 ∪ · · · ∪ Xk .
Next, we formally define a configuration (examples ofwhich were seen in Section II-A).
Definition 1 (Configuration): Let D be a multiset of balls
and k ≥ 1 be an integer (representing the number of bags).
We call a triple (T 0 ; B; T) = (T 0 ; B1 , . . . , Bk ; T 1 , . . . , T k ) a
configuration if it satisfies the following:T 0 ⊆ D is a tray, where all balls in D are put here before
the execution of a protocol;k• B = (B1 , . . . , Bk ) ⊆ D is a sequence of k bags;k• T = (T 1 , . . . , T k ) ⊆ D is a sequence of k trays representing that balls in T i were taken out of Bi for every i,
1 ≤ i ≤ k;
• T 0 ∪ union(B ∪ T) = D.
•

We denote by C(D,k) the set of all configurations derived by
fixing D and k.
Given a configuration (T 0 ; B1 , . . . , Bk ; T 1 , . . . , T k ), balls intrays T 0 and T 1 , . . . , T k are visible while balls in bags
B1 , . . . , Bk are invisible. We assume that the number of balls
inside each bag is known to the public. Bearing this inmind, we define a visible configuration vis(C) for a configuration C = (T 0 ; B1 , . . . , Bk ; T 1 , . . . , T k ) as follows: vis(C) B(T 0 ; |B1 |, . . . , |Bk |; T 1 , . . . , T k ), where |Bi | denotes the numberof elements (balls) in Bi . Wen also define the seto of all visible
configurations as Vis(D,k) = vis(C) | C ∈ C(D,k) .ii
ii Information about a configuration transition (e.g., a red ball was moved
to the second bag) can be captured by a visible “configuration-trace” that will
be mentioned later.

We are now ready to formally define a “protocol” P
achieving MPCs using balls and bags.
Definition 2 (Protocol):A protocol P is a tuple(D, k, n, U, Q, A) satisfying the following:• D is a multiset over {•, ◦}, representing balls used in the
protocol and k ≥ 1 is the number of bags; therefore,
the initial configuration is C 0 = (D; B0 ; T0 ) such that
union(B0 ∪ T0 ) = φ and |B0 | = |T0 | = k.
• n ≥ 2 represents the number of players participating in
the protocol.
• U is the set of players’ possible inputs. In the sequel, we
fix it to U = {0, 1}n , meaning that each player’s input isa bit.
• Q is a set of states with two distinguished states, namely,
the initialstate q0 and the final state q f .
• A :Q \ {q f } × Vis(D,k) → Q × Action is an action
function, which specifies the next state and an action,
given a current state and a visible configuration. The
set Action includes the following actions, where we
describe each action for a configuration C = (T 0 ; B; T) =(T 0 ; B1 , . . . , Bk ; T 1 , . . . , T k ).
– (PublicPut, b, p) for b ∈ T 0 and p ∈ {1, 2, . . . , k}: Thisputs the ball b from the tray T 0 into the p-th bag B p
publicly (i.e., the color of the ball is known to allplayers). That is, it transforms C into the following
configuration C 0 :C 0 = (T 0 \ [b]; B1 , . . . , B p−1 , B p ∪{{b}}, B p+1 , . . . , Bk ; T).
Note that the player executing this action must show
the ball b to other players before putting it into thebag.
– (PrivatePut, i, I0 , I1 ) for i, 1 ≤ i ≤ n, and sequencesof k multisets I0 = (I01 , . . . , I0k ) and I1 = (I11 , . . . , I1k )such that union(I0 ) = union(I1 ) ⊆ T 0 and |I0j | = |I1j |for every j, 1 ≤ j ≤ k: This makes the i-th
player holding an input xi ∈ {0, 1} take balls fromT 0 and then privately put them into B as specified
by I xi . That is, it transforms C into the following
configuration C 0 :C 0 = (T 0 \union(I xi ); B ∪ I xi ; T).
Because union(I0 ) = union(I1 ), the numbers of • and◦ in I0 and I1 are the same.
– (Shuf, R) for R ⊆ {1, 2, . . . , k}: This shuffles bags
specified by R so that the resulting order of thebags becomes unknown to all players. That is, ittransforms C into the following configuration C 0 :
C 0 = T 0 ; Bπ−1 (1) , Bπ−1 (2) , . . . , Bπ−1 (k) ; T ,where π is uniformly drawn at random from the setof all permutations such that all positions except for
R are fixed points (i.e., π(i) = i for any i < R).
– (Take, p) for p ∈ {1, 2, . . . , k}: This takes a ball outof the p-th bag B p and then the ball is put on the

tray T p . That is, it transforms C into the following
configuration C 0 :C 0 B (T 0 ; B0 ; T0 ), whereB0 = (B1 , . . . , B p−1 , B p \ {{b}}, B p+1 , . . . , Bk ), andT0 = (T 1 , . . . , T p−1 , T p ∪ [b], T p+1 , . . . , T k ),for a (taken) ball b ∈ B p . Note that the taken ball
was drawn uniformly at random from B p . Also note
that, during this action, no player can get information
about other balls in B p . If we take all balls in all bags,
we write this action as (TakeAll).
– (Back, b, p) for b ∈ T p and p ∈ {1, 2, . . . , k}: This puts
the ball b on the p-th tray T p back to the tray T 0 . Thatis, it transforms C into the following configuration
C0:
C 0 = (T 0 ∪ [b]; B; T 1 , . . . , T p−1 , T p \ [b], T p+1 , . . . , T k ).
If we put all balls on all trays back to T 0 , we write
this action as (BackAll).
– (MergeBags, p1 , p2 ) for p1 , p2 ∈ {1, 2, . . . , k}: Thismerges the p1 -th bag with the p2 -th bag, i.e., allballs in B p1 are moved into B p2 without revealing
the colors of the balls. That is, it transforms C into
the following configuration C 0 :C 0 = (T 0 ; B1 , . . . , B p1−1 , {{}}, . . . , B p2 ∪ B p1 , . . . , Bk ; T).
– (Return, e) for some expression e. This special action
indicates that the protocol terminates with the outpute.
Given inputs x = (x1 , . . . , xn ) ∈ U = {0, 1}n , a protocol
P = (D, k, n, U, Q, A) proceeds as follows. Balls and bags
corresponding to D and k, respectively, are on the table,i.e., the initial configuration is C 0 = (D; B0 ; T0 ) where
union(B0 ∪ T0 ) = φ and |B0 | = |T0 | = k. Each i-th player
privately holds an input xi ∈ {0, 1}, and the state of the protocol
is q0 ∈ Q. Then, the configuration and the state are transformed
according to the output of the action function A(q0 , vis(C0 )).
The protocol continues to apply the action function A with
its current configuration and state being transformed until thestate becomes q f ; it terminates with (Return, e).
Let f be a Boolean function such that f : {0, 1}n → {0, 1}.
We say that a protocol P is correct for f if e (which is an
output of Return) derived by executing P is always equivalent
to the value of f (x1 , . . . , xn ).
C. Security
Let us consider security of a protocol P. We first consider
that all players in P are semi-honest, i.e., they correctly
follow a protocol’s description, but attempt to learn additional
information from information derived during the execution of
P. In this case, the security of P intuitively means that no
information except for the output is leaked from balls takenout of bags.
For the definition of the security, let us mention someterms. Consider an execution of a protocol P; the enumeration

(vis (C0 ) , vis (C1 ) , . . . , vis (Ct )) of all visible configurations
from the initial to the final one (where Ci−1 is transformed
into Ci by an action) is called a visible configuration-trace (ofP).
Definition 3 (Security): Let P = (D, k, n, U, Q, A) be a
protocol that is correct for f . Let V be the random variable
representing the visible configuration-trace of P, M be therandom variables representing the inputs of P, and F be therandom variable representing the output of f . We say that P
is secure for f if it satisfies
Pr [M = x | F = 0] = Pr [M = x | V = v, F = 0] , andPr [M = x | F = 1] = Pr [M = x | V = v, F = 1] ,for any x ∈ U and visible configuration-trace v.
Next, we consider malicious players who arbitrary deviate
from the protocol’s description. Note that such malicious
players are always able to obtain information about a private
input by illegally taking balls from bags immediately after anhonest player performs PrivatePut. Another possible attack is
to mark bags so that each bag can be identified even after
the order of the bags are shuffled via Shuffle. To prevent such
illegal actions, every player should observe each other to force
malicious players to be semi-honest (and immediately abort
the protocol if such attacks are detected). However, malicious
players can yet deviate by putting different colorsiii of balls
via PrivatePut that is not specified in P because it is a private
action. Therefore, if we consider malicious players in ourmodel, it intuitively suffices to consider whether or not theycan violate correctness and security of P via PrivatePut.
III. AND Protocol with Two Inputs
In this section, based on the definitions in Section II-B, wepresent a formal description of our AND protocol with two
inputs (x1 , x2 ) ∈ {0, 1}2 introduced in Sections I-A and II-A.
We first review the principle of our AND protocol and thenpresent its description. Finally, a diagram of the AND protocol
is given in Fig. 2, from which its correctness and security canbe confirmed.
A. Principle and Description
Remember the AND protocol introduced in Sections I-A
and II-A. Alice and Bob put • into the (first) bag B1 if his/her
private bit is 1; otherwise, they are supposed to put • into
different bags, B2 and B3 .
formally,
Aliceholding x1
actsby MorePrivatePut, 1, ([◦], [•], [◦]), ([•], [◦], [◦]) , and the possible
configurations
will be as in (2). Then, Bob holding x2 acts by
PrivatePut, 2, ([◦], [◦], [•]), ([•], [◦], [◦]) , and the possible
configurations will be as in (4). That is, sequences of balls
they privately put represent the values of their private inputs.
After shuffling the three bags and then taking all balls, they
can know that the AND value is 1 if there is [•, •]; otherwise,iii Malicious players cannot put a different number of balls into a bag via

PrivatePut because that number is fixed and verifiable by observing the bag

as defined in Definition 2.

Protocol 1. The two-input AND protocol:[•, •, ◦, ◦, ◦, ◦], 3, 2, {0, 1}2 , Q, A .
1) (PrivatePut, 1, ([◦], [•], [◦]), ([•], [◦], [◦]))
2) (PrivatePut, 2, ([◦], [◦], [•]), ([•], [◦], [◦]))
3) (Shuf, {1, 2, 3})4) (TakeAll)5) if visible conf. includes [•, •] then6)
(Return, x1 ∧ x2 = 1)
7) else8)(Return, x1 ∧ x2 = 0)
0. No information about the inputs (beyond the output) is
leaked.
As seen above, our two-input AND protocol uses six balls
and three bags; a formal description of the protocol is shownin Protocol 1. See Table I for the performance of the protocol
and Section VI is devoted to the discussion about it (as well asthat of our multi-input AND protocol which will be presented
in Section IV).
B. Security: A diagram of status transitions
To confirm the correctness and security of the AND protocol
against semi-honest players, we construct a diagram in Fig. 2
showing status transitions of the protocol. This method was
first proposed in [20] for card-based protocols, and thenan extended diagram was proposed in [6], which uses theprobability trace below.
Definition 4 (Probability Trace): Let P be a protocol withan input set U = {0, 1}n , and let v be a visible configurationtrace. We regard every input x ∈ U = {0, 1}n as a decimal
number x, 1 ≤ x ≤ |U| = 2n . A |U|-tuple (q1 , q2 , . . . , q|U| )such that q x = Pr [M = x, Gv = C | V = v] for every x ∈ U
is called a probability trace for a configuration C and thevisible configuration-trace v, where M, Gv , and V are randomvariables of the original input, configuration when v is seen,
and visible configuration-trace, respectively.
See Fig. 2 again. Each “box” in the figure including
several pairs of a configuration and a probability trace iscalled a status. Each status is associated with a prefix ofthe visible configuration-trace. As stated in Section II-A andformally defined in Definition 4, a probability trace next toa configuration represents the conditional probability that thecurrent configuration is the configuration, given the prefix ofthe visible sequence-trace.
A status in Fig. 2 is transformed into the next status by anaction as follows:• The topmost status consists of a single pair of
the initial configuration C 0 and the probability trace(p00 , p01 , p10 , p11 ).
• The first (and second) action is PrivatePut. For instance,
when x1 = 0, three balls specified by I10 = ([◦], [•], [◦])
are privately put into the bags, and the probability trace
becomes (p00 , p01 , 0, 0).
• The third action is Shuf. After the action, there are threepossible configurations with the equal probability, i.e.,1/3. This can be seen in the coefficient in the probability
traces for the three configurations.
• The fourth action is TakeAll, yielding six visible configurations. Assume for example that we have observed([◦, ◦], [•, ◦], [•, ◦]). The fourth coordinate in the probability trace is 0, and other coordinates are all p00 +p301 +p10 ,and hence, we know that the inputs must not be (1,1).
It means that the output is “x1 ∧ x2 = 0”. Furthermore,no information about the inputs is leaked because the
distribution of the conditional probability that the inputs
are (0,0), (0,1), and (1,0) is the same as the one ofknowing x1 ∧ x2 before the execution of the protocol.
This AND protocol is also secure against malicious players
because although malicious Alice (or Bob) could put a redball into a bag of different position that contradicts to thevalue of her private input, this attack can be regarded as she
inputs the negation of her input. That is, it can be simulated
in ideal/real simulation paradigm [21] (although its rigorous
proof is omitted).
IV. AND Protocol with More Than Two Inputs
In this section, we deal with secure AND computation withmore than two inputs. That is, we present a general AND
protocol that securely computes x1 ∧ · · · ∧ xn , given that nplayers P1 , . . . , Pn hold private input bits x1 , . . . , xn ∈ {0, 1},
respectively.
A. Idea
Simply extending the two-input AND does not work.: Asstated in Section III-A, our two-input AND protocol computes
the AND value by making two players privately put • into
the same bag if and only if their private bits both are 1. If
we simply extend this principle, can we construct an n-input
AND protocol for any n? Consider for instance that there arethree players P1 , P2 , and P3 where Pi holds his/her private bitxi ∈ {0, 1} for every i, 1 ≤ i ≤ 3. We prepare four (empty)
bags B1 , B2 , B3 , and B4 and make each player Pi privately put• into the (first) bag B1 if xi is 1 (otherwise, into the (i+1)-stbag Bi+1 ) and ◦ into the remaining bags. Then, the resulting
configurations will be as follows:(; {{◦, ◦, ◦}}, {{•, ◦, ◦}}, {{•, ◦, ◦}}, {{•, ◦, ◦}}; )(; {{•, ◦, ◦}}, {{•, ◦, ◦}}, {{•, ◦, ◦}}, {{◦, ◦, ◦}}; )(; {{•, ◦, ◦}}, {{•, ◦, ◦}}, {{◦, ◦, ◦}}, {{•, ◦, ◦}}; )(; {{•, ◦, ◦}}, {{◦, ◦, ◦}}, {{•, ◦, ◦}}, {{•, ◦, ◦}}; )(; {{•, •, ◦}}, {{•, ◦, ◦}}, {{◦, ◦, ◦}}, {{◦, ◦, ◦}}; )(; {{•, •, ◦}}, {{◦, ◦, ◦}}, {{•, ◦, ◦}}, {{◦, ◦, ◦}}; )(; {{•, •, ◦}}, {{◦, ◦, ◦}}, {{◦, ◦, ◦}}, {{•, ◦, ◦}}; )(; {{•, •, •}}, {{◦, ◦, ◦}}, {{◦, ◦, ◦}}, {{◦, ◦, ◦}}; )(p000 , 0, 0, 0, 0, 0, 0, 0),(0, p001 , 0, 0, 0, 0, 0, 0),(0, 0, p010 , 0, 0, 0, 0, 0),(0, 0, 0, p100 , 0, 0, 0, 0),(0, 0, 0, 0, p011 , 0, 0, 0),(0, 0, 0, 0, 0, p101 , 0, 0),(0, 0, 0, 0, 0, 0, p110 , 0),

Our idea: Let us go back to Step 4 in the AND protocol
introduced in Section I-A (or the fourth status in Fig. 2).
Suppose that we replace the action (TakeAll) with (Take, 1),
i.e., taking a ball out of the (first) bag B1 in (5). There are two
possibilities, i.e., • is taken with a probability of 1/3 or ◦ istaken with a probability of 2/3.iv If it is •, the configurationsin (5) are transformed into the followings:v([]; {{◦}}, {{•, ◦}}, {{◦, ◦}}; [•], [], []) ( p200 , p201 , p210 , 0),([]; {{◦}}, {{◦, ◦}}, {{•, ◦}}; [•], [], []) ( p200 , p201 , p210 , 0),([]; {{•}}, {{◦, ◦}}, {{◦, ◦}}; [•], [], []) (0, 0, 0, p11 ).

Note that this (Take, 1) action does not leak any information
about the inputs because the coordinate-wise sum of theprobability traces in (8) is equal to (p00 , p01 , p10 , p11 ), meaningthat the (conditional) distribution on inputs does not change.
Then, consider that we add the fourth bag and make the third
player P3 act byPrivatePut, 3, x3 , ([◦], [], [], [•, ◦]), ([•], [], [], [◦, ◦]) .
That is, if x3 = 0, the configurations in (8) are transformed
into([]; {{◦, ◦}}, {{•, ◦}}, {{◦, ◦}}, {{•, ◦}}; [•], ) ( p000
, 0, p010, p100, 0, 0, 0, 0),
2
2
2
p000
p010 p100([]; {{◦, ◦}}, {{◦, ◦}}, {{•, ◦}}, {{•, ◦}}; [•], ) ( 2 , 0, 2 , 2 , 0, 0, 0, 0),([]; {{•, ◦}}, {{◦, ◦}}, {{◦, ◦}}, {{•, ◦}}; [•], ) (0, 0, 0, 0, 0, 0, p110 , 0).

If x3 = 1, the configurations in (8) are transformed into([]; {{•, ◦}}, {{•, ◦}}, {{◦, ◦}}, {{◦, ◦}}; [•], ) (0, p001
, 0, 0, p011
, p101, 0, 0),222p001p011 p101([]; {{•, ◦}}, {{◦, ◦}}, {{•, ◦}}, {{◦, ◦}}; [•], ) (0, 2 , 0, 0, 2 , 2 , 0, 0),([]; {{•, •}}, {{◦, ◦}}, {{◦, ◦}}, {{◦, ◦}}; [•], ) (0, 0, 0, 0, 0, 0, 0, p111 ).

As seen from the above configurations, there is {{•, •}} if the
AND value x1 ∧ x2 ∧ x3 is 1; otherwise, the four bags are a
permuted sequence of {{•, ◦}}, {{•, ◦}}, {{◦, ◦}}, {{◦, ◦}}. Thus, after(Shuf, {1, 2, 3, 4}) and (TakeAll), all the players can obtain the
AND value of the three inputs x1 ∧ x2 ∧ x3 without revealing
any information except for the output.
Next, let us consider n = 4. In the same way as n = 3,
assume that we replace the above action (TakeAll) (in the threeinput protocol) with (Take, 1) and then a red ball is taken. The
resulting configurations will be the followings:(; {{◦}}, {{•, ◦}}, {{◦, ◦}}, {{◦, ◦}}; [•], )(; {{◦}}, {{◦, ◦}}, {{•, ◦}}, {{◦, ◦}}; [•], )(7)(0, 0, 0, 0, 0, 0, 0, p111 ),where we omit the tray T 0 and empty trays. Therefore, after
shuffling the four bags and taking all balls, all the players canknow that the AND value is 1 if there is [•, •, •]; otherwise, 0.
As seen from (7), however, they obtain additional information
about the inputs from the number of • in a tray; for example,
if there is [•, •, ◦], it means that the number of 1 among the
inputs x1 , x2 , and x3 is two. Therefore, this straightforward
extension is not a secure computation of AND.

(8)(; {{◦}}, {{◦, ◦}}, {{◦, ◦}}, {{•, ◦}}; [•], )

p

p

p

p

p

p

p

001 010 100 011 101 110( 000
3 , 3 , 3 , 3 , 3 , 3 , 3 ,0),pp001 p010 p100 p011 p101 p110
( 000
3 , 3 , 3 , 3 , 3 , 3 , 3 ,0),p000 p001 p010 p100 p011 p101 p110
( 3 , 3 , 3 , 3 , 3 , 3 , 3 ,0),(9)(; {{•}}, {{◦, ◦}}, {{◦, ◦}}, {{◦, ◦}}; [•], ) (0, 0, 0, 0, 0, 0, 0, p111 ).

These are the “same” configurations as in (8), i.e., the firstbag contains a red ball if and only if x1 = x2 = x3 = 1. Thus,a four-input AND protocol can be constructed by making P4
privately put balls in a similar way to P3 when n = 3.
In this way, we can extend the two-input AND protocol to
the n-input one for n ≥ 3.
iv Remember that in Step 3, the three bags have been shuffled. Hence, taking
a ball out of B1 does not leak information about x1 and x2 .
v If it is ◦, we return ◦ into B and then repeat shuffling bags and taking a
1ball out of B1 until • is taken.

([•, •, ◦, ◦, ◦, ◦]; {{}}, {{}}, {{}}; [], [], []) (p00 , p01 , p10 , p11 )(PrivatePut, 1, ([◦], [•], [◦]), ([•], [◦], [◦]))([•, ◦, ◦]; {{◦}}, {{•}}, {{◦}}; [], [], []) (p00 , p01 , 0, 0)([•, ◦, ◦]; {{•}}, {{◦}}, {{◦}}; [], [], []) (0, 0, p10 , p11 )(PrivatePut, 2, ([◦], [◦], [•]), ([•], [◦], [◦]))(p00 , 0, 0, 0)(0, p01 , 0, 0)(0, 0, p10 , 0)(0, 0, 0, p11 )([]; {{◦, ◦}}, {{•, ◦}}, {{•, ◦}}; [], [], [])([]; {{•, ◦}}, {{•, ◦}}, {{◦, ◦}}; [], [], [])([]; {{•, ◦}}, {{◦, ◦}}, {{•, ◦}}; [], [], [])([]; {{•, •}}, {{◦, ◦}}, {{◦, ◦}}; [], [], [])(Shuf, {1, 2, 3})([]; {{◦, ◦}}, {{•, ◦}}, {{•, ◦}}; [], [], [])([]; {{•, ◦}}, {{•, ◦}}, {{◦, ◦}}; [], [], [])([]; {{•, ◦}}, {{◦, ◦}}, {{•, ◦}}; [], [], [])([]; {{•, •}}, {{◦, ◦}}, {{◦, ◦}}; [], [], [])([]; {{◦, ◦}}, {{•, •}}, {{◦, ◦}}; [], [], [])([]; {{◦, ◦}}, {{◦, ◦}}, {{•, •}}; [], [], [])( p300 , p301 , p310 , 0)
( p300 , p301 , p310 , 0)
( p300 , p301 , p310 , 0)(0, 0, 0, p311 )(0, 0, 0, p311 )(0, 0, 0, p311 )(TakeAll)([]; {{}}, {{}}, {{}}; [◦, ◦], [•, ◦], [•, ◦]) ( pp000 , pp010 , pp100 , 0)
⇒ (Return, x1 ∧ x2 = 0)([]; {{}}, {{}}, {{}}; [•, •], [◦, ◦], [◦, ◦]) (0, 0, 0, 1)⇒ (Return, x1 ∧ x2 = 1)([]; {{}}, {{}}, {{}}; [•, ◦], [•, ◦], [◦, ◦]) ( pp000 , pp010 , pp100 , 0)
⇒ (Return, x1 ∧ x2 = 0)([]; {{}}, {{}}, {{}}; [◦, ◦], [•, •], [◦, ◦]) (0, 0, 0, 1)⇒ (Return, x1 ∧ x2 = 1)([]; {{}}, {{}}, {{}}; [•, ◦], [◦, ◦], [•, ◦]) ( pp000 , pp010 , pp100 , 0)
⇒ (Return, x1 ∧ x2 = 0)([]; {{}}, {{}}, {{}}; [◦, ◦], [◦, ◦], [•, •]) (0, 0, 0, 1)⇒ (Return, x1 ∧ x2 = 1)

Fig. 2: A diagram of the two-input AND protocol with two inputs x1 , x2 ∈ {0, 1} introduced in Sections I-A and II-A, wherep0 = p00 + p01 + p10 .
B. Description
Based on the idea explained above, we present an informal
description of our AND protocol with n (≥ 3) inputs, in whichcorrectness and security are also described.
1) Players prepare n + 1 empty bags, two red balls, and 2n
white balls.
2) If x1 = 0, a player P1 privately puts a red ball into thesecond bag and a white ball into each of the first andthird bags. If x1 = 1, P1 privately puts a red ball into
the first bag and a white ball into each of the second
and third bags.
3) If x2 = 0, a player P2 privately puts a red ball into
the third bag and a white ball into each of the first andsecond bags. If x2 = 1, P2 privately puts a red ball into
the first bag and a white ball into each of the second
and third bags.
4) For i = 3 to n, repeat the following.

a) Shuffle the first i bags (which are not empty).
b) Take a ball from the first bag. If its color is red,then player Pi holds the red ball and other two
white balls. If its color is white, then they puts thewhite ball into the first bag again and go back to
the previous step. (Note that since the bags havebeen shuffled in the previous step, the probability
1, whichthat the color of the taken ball is red is n+1
is independent of the input.)c) If xi = 0, Pi privately puts the red ball into the(i + 1)-st bag and the white ball into the first bag.
If xi = 1, Pi privately puts the red ball into thefirst bag and the white ball into the (i + 1)-st bag.
Another white ball is put into the (i + 1)-st bag.
Note that the two red balls are in the first bag if
and only if x1 ∧ x2 ∧ · · · ∧ xi = 1.

Protocol 2. The AND protocol with n (≥ 3) inputs:([•, •, ◦, ◦, . . . , ◦], n + 1, n, {0, 1}n , Q, A).
1) (PrivatePut, 1, I10 , I11 )2) (PrivatePut, 2, I20 , I21 )3) for i ← 3 to n do
4)
while(1)5)(Shuf, {1, 2, . . . , i})6)(Take, 1)7)
if taken ball = • then
8)
(Back, •, 1)
9)(PrivatePut, i, Ii0 , Ii1 )
10)
break
11)
else if taken ball = ◦ then
12)
(Back, ◦, 1)
13)(PublicPut, ◦, 1)14) (Shuf, {1, 2, . . . , n + 1})
15) (TakeAll)16) if visible conf. includes [•, •] then17)
(Return, x1 ∧ · · · ∧ xn = 1)18) else
19)(Return, x1 ∧ · · · ∧ xn = 0)x1∧ ⋯ ∧ xi-1=0/xi=0⋯⋯x1∧ ⋯ ∧ xi-1=0/xi=1⋯This multi-input AND protocol is also secure against malicious players in the same reason for the two-input AND
protocol mentioned in Section III-B. Moreover, the protocol
is a collusion-free protocol [16], i.e., it prevents malicious
players from obtaining additional information by coordinating
their actions during the execution of the protocol. This isbecause players are assumed to be in the same place, andhence, they can observe each other’s actions to be performed ina correct manner. That is, actions used in our protocols satisfy
observability (as in [16, Theorem 4]). Although colluding
players can share information about the colors of balls they
put into bags via PrivatePut, it does not help them obtain extra
information because the number of red balls in bags is always
two in the protocol (when taking balls).
V. Protocols for Any Boolean Functionx1∧ ⋯ ∧ xi-1=1/xi=0⋯x1∧ ⋯ ∧ xi=1⋯⋯5) Shuffle the n + 1 bags.
6) Take all the balls from the n + 1 bags. If there is a bag
including two red balls, then we have x1 ∧ · · · ∧ xn = 1;otherwise, x1 ∧ · · · ∧ xn = 0.
A formal description is shown in Protocol 2. Here,I10 = [◦], [•], [◦], [], . . . , [] ,I20 = [◦], [◦], [•], [], . . . , [] ,I11 = I21 = [•], [◦], [◦], [], . . . , [] ,and for every i, 3 ≤ i ≤ n,
 1 2
i−1
i
i+1
k
[◦], [], . . . , [], [•, ◦], [], . . . , [] ,
Ii1 = [•], [], . . . , [], [◦, ◦], [], . . . , [] .

Ii0 =C. Correctness and Security
Figure 3 shows a part of the diagram of the n-input
AND protocol described in Section IV-A; the partial diagram
corresponds to Steps 3–13 in Protocol 2. From this figure, we
can see that there is {{•, •}} if and only if x1 = x2 = · · · = xi = 1.
We can furthermore see that (Take, 1) leaks no information
about the inputs because the probability of taking a red ball1
is always i+1, which is independent of the inputs. Therefore,
this protocol is secure against semi-honest players.

In this section, we will explain how to realize protocols for
any Boolean function with balls and bags. To achieve it, we
will propose committed-format AND and NOT protocols thatare known to be functionally complete. Note that in our AND
protocols shown in Sections III and IV, the balls should be
revealed to obtain the AND values in the final step. Namely,
the previous AND protocols cannot be used as building blocks
for a composition of another protocol. As a building block for
a composite protocol, the following property called committedformat is required: We say a protocol is committed-format if
its output can be an input for another (next) protocol without
revealing balls themselves.
Note that in the sequel, we will construct committed-format
protocols with balls, where sizes of all balls are the same.
On the other hand, in Appendix B, we will discuss efficientcommitted-format AND, NOT, and COPY protocols that canalso realize any Boolean function by introducing two kinds ofballs with different sizes.
A. Committed-Format AND protocol
Encoding: We encode a Boolean value with two bags,
each of which includes the same number of balls, as follows:{{◦, ◦, ◦, . . . , ◦}}, {{•, ◦, ◦, . . . , ◦}} = 0,{{•, ◦, ◦, . . . , ◦}}, {{◦, ◦, ◦, . . . , ◦}} = 1.

(10)

That is, a pair of bags where the second (resp. first) bag
contains exactly one red ball • represents 0 (resp. 1). A pairof bags representing a bit x ∈ {0, 1} according to the above
encoding rule is called a commitment to x.
Let us replace a Return action in Definition 2 with a Result
action for a committed-format protocol: (Result, p1 , p2 ) for
p1 , p2 ∈ {1, . . . , k}. This means that the protocol terminateswith the commitment consisting of the p1 -th and p2 -th bags.
Idea: Given two commitments to x1 ∈ {0, 1} andx2 ∈ {0, 1}, a committed-format AND protocol produces acommitment to x1 ∧ x2 . Let B1 and B2 be two bags constituting
a commitment to x1 , and B3 and B4 be those constituting acommitment to x2 such that |B1 | = |B2 | = |B3 | = |B4 | = m.
Suppose that we merge B3 with B1 via MergeBags (i.e., B1
and B3 become such that |B1 | = 2m and |B3 | = 0) and put m

p000···01 p000···10([◦, . . . , ◦]; {{◦}}, {{•, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{}}; [•]) ( p000···00
i−1 , i−1 , i−1 , . . . , 0, 0)p000···01 p000···10([◦, . . . , ◦]; {{◦}}, {{◦, ◦}}, {{•, ◦}}, . . . , {{◦, ◦}}, {{}}; [•]) ( p000···00,
i−1i−1 , i−1 , . . . , 0, 0)..
.
p000···01 p000···10([◦, . . . , ◦]; {{◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{•, ◦}}, {{}}; [•]) ( p000···00
i−1 , i−1 , i−1 , . . . , 0, 0)([◦, . . . , ◦]; {{•}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{}}; [•]) (0, 0, 0, . . . , p111···10 , p111···11 )(Back, 1)
p000···01 p000···10([•, ◦, . . . , ◦]; {{◦}}, {{•, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{}}; ) ( p000···00
i−1 , i−1 , i−1 , . . . , 0, 0)p000···01 p000···10([•, ◦, . . . , ◦]; {{◦}}, {{◦, ◦}}, {{•, ◦}}, . . . , {{◦, ◦}}, {{}}; ) ( p000···00
i−1 , i−1 , i−1 , . . . , 0, 0)..
.
p000···01 p000···10([•, ◦, . . . , ◦]; {{◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{•, ◦}}, {{}}; ) ( p000···00
i−1 , i−1 , i−1 , . . . , 0, 0)([•, ◦, . . . , ◦]; {{•}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{}}; ) (0, 0, 0, . . . , p111···10 , p111···11 )(PrivatePut, i, Ii0 , Ii1 )([◦, . . . , ◦]; {{◦, ◦}}, {{•, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{•, ◦}}; )([◦, . . . , ◦]; {{◦, ◦}}, {{◦, ◦}}, {{•, ◦}}, . . . , {{◦, ◦}}, {{•, ◦}}; )([◦, . . . , ◦]; {{•, ◦}}, {{•, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; )([◦, . . . , ◦]; {{•, ◦}}, {{◦, ◦}}, {{•, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; )..
.

p000···10( p000···00
i−1 , 0, i−1 , . . . , 0, 0)p000···10( p000···00,
0,i−1i−1 , . . . , 0, 0)(0, p000···01
i−1 , 0, . . . , 0, 0)p000···01(0, i−1 , 0, . . . , 0, 0)([◦, . . . , ◦]; {{◦, ◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{•, ◦}}, {{•, ◦}}; )([◦, . . . , ◦]; {{•, ◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{•, ◦}}, {{◦, ◦}}; )([◦, . . . , ◦]; {{•, ◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{•, ◦}}; )([◦, . . . , ◦]; {{•, •}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; )p000···10( p000···00
i−1 , 0, i−1 , . . . , 0, 0)(0, p000···01
i−1 , 0, . . . , 0, 0)(0, 0, 0, . . . , p111···10 , 0)(0, 0, 0, . . . , 0, p111···11 )(Shuf, {1, 2, 3, . . . , i, i + 1})([◦, . . . , ◦]; {{•, ◦}}, {{•, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; ) pi+1000···00, p000···01 , p000···10 , . . . , pi+1111···10
C 2 , 0
 p C2 pi+1 C2 pi+1 C2
p111···10000···01000···10000···00([◦, . . . , ◦]; {{•, ◦}}, {{◦, ◦}}, {{•, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; ),,, . . . , i+1 C2 , 0
 i+1 C2 pi+1 C2 pi+1 C2

p111···10000···01000···10([◦, . . . , ◦]; {{◦, ◦}}, {{•, ◦}}, {{•, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; ) pi+1000···00
C2 , i+1 C2 , i+1 C2 , . . . , i+1 C2 , 0..
.
([◦, . . . , ◦]; {{•, ◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{•, ◦}}; ) pi+1000···00, p000···01 , p000···10 , . . . , pi+1111···10
C 2 , 0
 p C2 pi+1 C2 pi+1 C2
p111···10000···00
000···01000···10([◦, . . . , ◦]; {{◦, ◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{•, ◦}}, {{•, ◦}}; ), i+1 C2 , i+1 C2 , . . . , i+1 C2 , 0
i+1 C 2([◦, . . . , ◦]; {{•, •}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; ) (0, 0, 0, . . . , 0, p111···11
i+1 )([◦, . . . , ◦]; {{◦, ◦}}, {{•, •}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; ) (0, 0, 0, . . . , 0, p111···11
i+1 )p111···11([◦, . . . , ◦]; {{◦, ◦}}, {{◦, ◦}}, {{•, •}}, . . . , {{◦, ◦}}, {{◦, ◦}}; ) (0, 0, 0, . . . , 0, i+1 )..
.
([◦, . . . , ◦]; {{◦, ◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{•, •}}, {{◦, ◦}}; ) (0, 0, 0, . . . , 0, p111···11
i+1 )([◦, . . . , ◦]; {{◦, ◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{•, •}}; ) (0, 0, 0, . . . , 0, p111···11
i+1 )(Take, 1)◦ is taken with prob. 2/3.

([◦, . . . , ◦]; {{•}}, {{•, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; [◦])([◦, . . . , ◦]; {{•}}, {{◦, ◦}}, {{•, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; [◦])([◦, . . . , ◦]; {{◦}}, {{•, ◦}}, {{•, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; [◦])..
.
([◦, . . . , ◦]; {{•}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{•, ◦}}; [◦])([◦, . . . , ◦]; {{◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{•, ◦}}, {{•, ◦}}; [◦])([◦, . . . , ◦]; {{◦}}, {{•, •}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; [◦])([◦, . . . , ◦]; {{◦}}, {{◦, ◦}}, {{•, •}}, . . . , {{◦, ◦}}, {{◦, ◦}}; [◦])..
.

• is taken with prob. 1/3.

p
000···00 2p000···01,, p000···10 , . . . , pi+1111···10C2 , 0 pi+1 C2 p i+12 p i+1 C2

p111···10000···00
000···01000···10,,, . . . , i+1 C2 , 0 pi+1 C2 pi+1 C2 pi+1 C2
p111···10000···00
000···10, i+1000···01
C2 , i+1 C2 , . . . , i+1 C2 , 0
i+1 C 2
p000···00, p000···01 , p000···10 , . . . , pi+1111···10C2 , 0 pi+1 C2 pi+1 C2 pi+1 C2
p111···10000···00
000···01000···10, i+1 C2 , i+1 C2 , . . . , i+1 C2 , 0
i+1 C 2)(0, 0, 0, . . . , 0, p111···11i(0, 0, 0, . . . , 0, p111···11)i([◦, . . . , ◦]; {{◦}}, {{•, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; [•]) ( p000···00, p000···01, p000···10, . . . , p111···10
, 0)
i
i
i
i
([◦, . . . , ◦]; {{◦}}, {{◦, ◦}}, {{•, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; [•]) ( p000···00, p000···01, p000···10, . . . , p111···10
, 0)
i
i
i
i
..
.
([◦, . . . , ◦]; {{◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{•, ◦}}; [•]) ( p000···00, p000···01, p000···10, . . . , p111···10
, 0)
i
i
i
i
([◦, . . . , ◦]; {{•}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{◦, ◦}}; [•]) (0, 0, 0, . . . , 0, p111···11 )([◦, . . . , ◦]; {{◦}}, {{◦, ◦}}, {{◦, ◦}}, . . . , {{◦, ◦}}, {{•, •}}; [◦]) (0, 0, 0, . . . , 0, p111···11)iFig. 3: A crucial part of a diagram of the AND protocol with n inputs x1 , x2 , . . . , xn ∈ {0, 1}n for the loop index i ∈ {3, 4, . . . , n−1},where empty trays and empty bags (over the (i + 2)-nd) are omitted for simplicity.
white balls into each of B2 and B4 (i.e., they become such that
|B2 | = 2m and |B4 | = 2m). Then, the resulting configurations
will be as follows:(; {{◦, ◦, ◦, . . . , ◦}}, {{•, ◦, ◦, . . . , ◦}}, {{}}, {{•, ◦, ◦, . . . , ◦}}; )(; {{•, ◦, ◦, . . . , ◦}}, {{•, ◦, ◦, . . . , ◦}}, {{}}, {{◦, ◦, ◦, . . . , ◦}}; )(; {{•, ◦, ◦, . . . , ◦}}, {{◦, ◦, ◦, . . . , ◦}}, {{}}, {{•, ◦, ◦, . . . , ◦}}; )(; {{•, •, ◦, . . . , ◦}}, {{◦, ◦, ◦, . . . , ◦}}, {{}}, {{◦, ◦, ◦, . . . , ◦}}; )(p00 ,0,0,0),(0,p01 ,0,0),(0,0,p10 ,0),(0,0,0,p11 ),where we omit the tray T 0 . Note that these are similar to (4)if we eliminate the empty bag B3 , i.e., two red balls are in

B1 if and only if x1 = x2 = 1. Therefore, we can compute an
AND value via (Shuf, {1, 2, 4}) and (TakeAll) in the same way
to our two-input AND protocol.
Next, let us consider how to produce a commitment to x1 ∧x2from the above configurations (where B3 is removed). Supposethat we repeat applying (Shuf, {1, 2, 3}) and (Take, 1) until thecolor of a taken ball is redvi . Then, the resulting configurations
vi If it is ◦, we return ◦ into B .
1Protocol 3. The committed-format AND protocol, where thenumber of balls in each bag is denoted by m:[◦, . . . , ◦], 4, 2, {0, 1}2 , Q, A .
Initial state (where empty trays are omitted):([◦, . . . , ◦]; {{◦, ◦, . . . , ◦}}, {{•, ◦, . . . , ◦}}, {{◦, ◦, . . . , ◦}}, {{•, ◦, . . . , ◦}}; )(p00 , 0, 0, 0)([◦, . . . , ◦]; {{◦, ◦, . . . , ◦}}, {{•, ◦, . . . , ◦}}, {{•, ◦, . . . , ◦}}, {{◦, ◦, . . . , ◦}}; )(0, p01 , 0, 0)([◦, . . . , ◦]; {{•, ◦, . . . , ◦}}, {{◦, ◦, . . . , ◦}}, {{◦, ◦, . . . , ◦}}, {{•, ◦, . . . , ◦}}; )(0, 0, p10 , 0)([◦, . . . , ◦]; {{•, ◦, . . . , ◦}}, {{◦, ◦, . . . , ◦}}, {{•, ◦, . . . , ◦}}, {{◦, ◦, . . . , ◦}}; )(0, 0, 0, p11 )Steps:
1) (MergeBags, 3, 1)
2) (PublicPut, ◦ · · · ◦, 2)3) (PublicPut, ◦ · · · ◦, 4)4) while(1)5)(Shuf, {1, 2, 4})
6)(Take, 1)7)
if taken ball = • then
8)
break
9)
else
10)
(Back, ◦, 1)
11)(PublicPut, ◦, 1)12) (MergeBags, 4, 2)13) (PublicPut, ◦ · · · ◦, 1)14) (Result, 1, 2)

B. How to Construct a Protocol for Any Function

will be as follows:(; {{◦, ◦, . . . , ◦}}, {{•, ◦, . . . , ◦}}, {{◦, ◦, . . . , ◦}};[•]) ( p200, p201, p210,0),(; {{◦, ◦, . . . , ◦}}, {{◦, ◦, . . . , ◦}}, {{•, ◦, . . . , ◦}};[•]) ( p200, p201, p210,0), (11)(; {{•, ◦, . . . , ◦}}, {{◦, ◦, . . . , ◦}}, {{◦, ◦, . . . , ◦}};[•]) (0, 0, 0, p11 ),where we omit the empty bag and empty trays. From the above
configurations, notice that if we merge B2 and B3 into one
bag, say B2 , then a pair of B1 and B2 can be a commitment
to x1 ∧ x2 . Thus, we can obtain the output commitment bymoving all the balls in B3 into B2 (and put 2m white balls
into B1 to make the numbers of balls be the same).
Description: Given two commitments to x1 ∈ {0, 1} andx2 ∈ {0, 1}, our committed-format AND protocol informallyproceeds as follows.
1) Merge the first bag constituting the commitment to x2
with the first bag constituting the commitment to x1 .
Note that there is a bag including two red balls if andonly if x1 ∧ x2 = 1.
x1=0/x2=0

⋯

x1

⋯

x1=1/x2=0⋯⋯

x1=0/x2=1

x2⋯⋯

If its color is white, then put it into the first bag again
and go back to the previous step.
5) Put white balls into the first bag so that the number ofballs in that bag becomes the same as in the mergedbag. The first and second bag constitute a commitment
to x1 ∧ x2 .
A formal description is shown in Protocol 3. We denoteby B1 and B2 two bags constituting a commitment to x1
and by B3 and B4 those constituting a commitment to x2 .
Hereinafter, for successive two actions (PublicPut, b1 , p) and(PublicPut, b2 , p), we simply write (PublicPut, b1 b2 , p).
We omit a diagram of our committed-format AND protocol
as it is similar to that of our multi-input AND protocol shownin Fig. 3. We discuss the performance of the protocol in
Section VI.

⋯⋯

VI. Performance of Our Protocols

x1=1/x2=1⋯⋯⋯

See (10) again. We note that a committed-format NOT
protocol can be easily constructed; just swapping two bags
constituting a commitment to x ∈ {0, 1} results in a commitment to the negation x̄.
We now have committed-format AND and NOT protocols
as shown above. Based on these protocols, we can constructa protocol for any Boolean function f as follows.
1) Create a Boolean circuit representing f (with AND and
NOT gates).
2) Each player prepares a required number of commitments
to his/her private input via PrivatePut according to thecircuit.
3) Obtain a commitment to the output value of f by evaluating the circuit using our committed-format AND/NOT
protocols. If the number of balls is different between
input commitments when performing the AND protocol,
players put white balls such that the number of balls
becomes the same.
Since our committed-format AND protocol is secure and any
information about the inputs and output does not leak (becauseof committed-format), the above protocol for f is also secureagainst semi-honest players. However, unlike our proposed
AND protocols, the above protocol is not secure against
malicious players because they possibly perform PrivatePut
multiple times, and hence, the protocol cannot ensure that they
consistently perform PrivatePut without contradicting to theirprivate inputs. (We solve this security issue in Appendix B byconstructing a copy protocol that duplicates a commitment.)⋯

2) Put white balls into the second bags constituting thecommitments to x1 and x2 so that the numbers of ballsin those bags become the same as in the merged bag.
3) Shuffle the three bags.
4) Take a ball from the first bag. If its color is red, thenmerge the third bag with the second bag. Note that thefirst bag includes a red ball if and only if x1 ∧ x2 = 1.

This section discusses the efficiency of our AND protocols
shown in Sections III, IV, and V-A. Table I summarizes theperformance of our proposed protocols. We evaluated them interms of two items: the number of balls and bags, and runtime.
The Number of Balls and Bags: Our two-input AND
protocol requires six balls (namely, two red and four whiteballs) and three bags. Our conjecture is that two bags would
be insufficient for a secure computation of the two-input AND
computation. On the other hand, our AND protocol with ninputs requires 2n + 2 balls (namely, two red and 2n whiteballs) and n + 1 bags. Our committed-format AND protocol
would be inefficient because it requires 8m balls (and fourbags) where m denotes the number of balls in each of bags
constituting input commitments.
Let C be a Boolean circuit with the logical AND/NOT gatesand d(C) denote the depth of C. Let us consider the numberof required balls for our committed-format AND protocol that
evaluates the “final” AND gate for C (i.e., it is of the depthd(C)), denoted by αd(C) . Remember that the number of balls ineach of bags constituting the output commitment is four times
greater than that of input commitments in our committedformat AND protocol. Thus, we have αd(C) = 2 × 4d(C) , i.e.,αd(C) = O(4d(C) ).
Runtime: Our two-input AND protocol has a deterministic runtime. By contrast, our AND protocol with n inputs andcommitted-format AND protocol are Las Vegas algorithms.
Each protocol includes a repetition of shuffling bags and taking
a ball until • appears. Let us estimate the expected number ofthe repetition.
For our AND protocol with n inputs, let us first consider
the case of n = 3 as a simple case. Remember that we repeat(Shuf, {1, 2, 3}) and (Take, 1) (and (PublicPut, •, 1)) from (4)until • appears. The expected number of the repetition is three
because the probability of taking • is exactly 1/3. Then, let us
consider the case of n = 4. In addition to the actions for n =3, we repeat (Shuf, {1, 2, 3, 4}) and (Take, 1) from four bags
including eight balls (namely, two red and six white balls) until• is taken. Therefore, the expected number of the repetition is
3 + 4 = 7.
When we have n (≥ 3) inputs, the expected number of therepetition can be written as follows:nX(n − 2)(n + 3)
.
k=
2
k=3
That is, it is O (n2 ).
For our committed-format AND protocol, let us also show
the expected number of the repetition. The probability of
taking • (as in (11)) is 2/(6m−2) because the total numbers of
red and white balls in the bags are 2 and 6m − 2, respectively.
Thus, the expected number of the repetition is 3m − 1. As
for the number of balls, let us consider the expected numberof the repetition for our committed-format AND protocol that
evaluates the final AND gate for C, denoted by βd(C) . We haveβd(C) = 3 × 4d(C)−1 − 1, i.e., βd(C) = O(4d(C) ).
VII. Implementation Examples
In this section, we show implementation examples for ballbased cryptography to show the feasibility of using (physical)
balls and bags. For this, we purchased two-colored balls forapproximately $1 and three bags for approximately $3 asshown in Fig. 4. Using these balls and bags, we implemented
all the actions defined in Definition 2 (except for Back andResultvii ), as shown in Fig. 5. As a result, we confirmed thatvii Back can be performed without using a bag, and Result requires no balland bag.

Fig. 4: Two-colored balls and three bags we purchased. The
bags are closed at the top with drawstrings.

ball-based cryptography proposed in this study is based onrealistic physical operations and is feasible for humans.
VIII. Conclusion
In this work, we showed that balls and bags provide usa simple way for achieving a secure computation of thelogical AND. We formalized protocols with balls and bags
and showed how to construct a diagram of a protocol, fromwhich its correctness and security can be confirmed. Moreover,
we presented general MPCs by constructing committed-format
AND and NOT protocols. In Appendix B, we also proposed
efficient committed-format protocols using different kinds ofballs.
Acknowledgements
We thank the anonymous referees, whose comments havehelped us to improve the presentation of the paper. This work
was supported in part by JSPS KAKENHI Grant Numbers
JP18H05289, JP19J21153, and JP21K11881.
References[1] D. Chaum, “The dining cryptographers problem: Unconditional senderand recipient untraceability,” Journal of Cryptology, vol. 1, no. 1, pp.
65–75, 1988. [Online]. Available: https://doi.org/10.1007/BF00206326[2] A. C. Yao, “Protocols for secure computations,” in IEEE Symposium
on Foundations of Computer Science, ser. FOCS ’82. Washington:
IEEE Computer Society, 1982, pp. 160–164. [Online]. Available:
https://doi.org/10.1109/SFCS.1982.88[3] B. Den Boer, “More efficient match-making and satisfiability the five
card trick,” in Advances in Cryptology—EUROCRYPT ’89, ser. Lecture
Notes in Computer Science, J.-J. Quisquater and J. Vandewalle, Eds.,
vol. 434. Berlin, Heidelberg: Springer, 1990, pp. 208–217. [Online].
Available: https://doi.org/10.1007/3-540-46885-4_23[4] C. Crépeau and J. Kilian, “Discreet solitary games,” in Advances in
Cryptology—CRYPTO’ 93, ser. Lecture Notes in Computer Science,
D. R. Stinson, Ed., vol. 773. Berlin, Heidelberg: Springer, 1994, pp.
319–330. [Online]. Available: https://doi.org/10.1007/3-540-48329-2_
27[5] T. Mizuki, M. Kumamoto, and H. Sone, “The five-card trick can bedone with four cards,” in Advances in Cryptology—ASIACRYPT 2012,ser. Lecture Notes in Computer Science, X. Wang and K. Sako, Eds.,
vol. 7658. Berlin, Heidelberg: Springer, 2012, pp. 598–606. [Online].
Available: https://doi.org/10.1007/978-3-642-34961-4_36

TABLE I: The efficiency of our proposed protocols, where m denotes the number of balls in each of bags constituting an input
commitment.
Function# of Balls# of Bags

RuntimeDeterministic

two-input AND

§III

6

3

n-input AND§IV

2n + 2n+1

Expectedcommitted-format AND

§V-A

8m

4

Expected

Boolean circuit C§V-B

2 × 4d(C)

2 × #input-node

Expected(a) PublicPut(b) PrivatePut(d) Take(e) MergeBags(c) Shuf

Fig. 5: Implementing all the actions defined in Definition 2[6] T. Mizuki and Y. Komano, “Analysis of information leakage due tooperative errors in card-based protocols,” in Combinatorial Algorithms,
ser. Lecture Notes in Computer Science, C. Iliopoulos, H. W. Leong,and W.-K. Sung, Eds., vol. 10979. Cham: Springer, 2018, pp. 250–262.
[Online]. Available: https://doi.org/10.1007/978-3-319-94667-2_21[7] R. Fagin, M. Naor, and P. Winkler, “Comparing information without
leaking it,” Commun. ACM, vol. 39, no. 5, pp. 77–85, 1996. [Online].
Available: https://doi.acm.org/10.1145/229459.229469[8] R. Gradwohl, M. Naor, B. Pinkas, and G. N. Rothblum, “Cryptographic
and physical zero-knowledge proof systems for solutions of Sudoku
puzzles,” Theory of Computing Systems, vol. 44, no. 2, pp. 245–268,
2009. [Online]. Available: https://doi.org/10.1007/s00224-008-9119-9[9] T. Moran and M. Naor, “Polling with physical envelopes: A rigorous
analysis of a human-centric protocol,” in Advances in Cryptology—
EUROCRYPT 2006, ser. Lecture Notes in Computer Science,
S. Vaudenay, Ed., vol. 4004. Berlin, Heidelberg: Springer, 2006, pp.
88–108. [Online]. Available: https://doi.org/10.1007/11761679_7[10] M. Naor and A. Shamir, “Visual cryptography,” in Advancesin Cryptology—EUROCRYPT ’94, ser. Lecture Notes in Computer
Science, A. De Santis, Ed., vol. 950. Berlin, Heidelberg: Springer, 1995,
pp. 1–12. [Online]. Available: https://doi.org/10.1007/BFb0053419[11] P. D’Arco and R. De Prisco, “Secure computation without computers,”
Theoretical Computer Science, vol. 651, pp. 11–36, 2016. [Online].
Available: https://doi.org/10.1016/j.tcs.2016.08.003[12] Y. Komano and T. Mizuki, “Multi-party computation based on physicalcoins,” in Theory and Practice of Natural Computing, ser. Lecture Notes
in Computer Science, D. Fagan, C. Martín-Vide, M. O’Neill, and M. A.
Vega-Rodríguez, Eds., vol. 11324. Cham: Springer, 2018, pp. 87–98.
[Online]. Available: https://doi.org/10.1007/978-3-030-04070-3_7[13] J. Balogh, J. A. Csirik, Y. Ishai, and E. Kushilevitz, “Privatecomputation using a PEZ dispenser,” Theoretical Computer Science,
vol. 306, no. 1, pp. 69–84, 2003. [Online]. Available: https://doi.org/10.1016/S0304-3975(03)00210-X[14] Y. Abe, M. Iwamoto, and K. Ohta, “Efficient private PEZ protocols
for symmetric functions,” in Theory of Cryptography, ser. Lecture
Notes in Computer Science, D. Hofheinz and A. Rosen, Eds., vol.
11891. Cham: Springer, 2019, pp. 372–392. [Online]. Available:
https://doi.org/10.1007/978-3-030-36030-6_15[15] T. Moran and M. Naor, “Basing cryptographic protocols on
tamper-evident seals,” Theoretical Computer Science, vol. 411,
no. 10, pp. 1283 – 1310, 2010. [Online]. Available: https://doi.org/10.1016/j.tcs.2009.10.023[16] M. Lepinksi, S. Micali, and a. shelat, “Collusion-free protocols,”
in ACM Symposium on Theory of Computing, ser. STOC ’05.
New York: ACM, 2005, pp. 543–552. [Online]. Available: https://doi.org/10.1145/1060590.1060671[17] S. Izmalkov, S. Micali, and M. Lepinski, “Rational secure computationand ideal mechanism design,” in IEEE Symposium on Foundations ofComputer Science, ser. FOCS ’05. USA: IEEE Computer Society, 2005,
pp. 585–594. [Online]. Available: https://doi.org/10.1109/SFCS.2005.64[18] T. Mizuki and H. Shizuya, “A formalization of card-based cryptographic
protocols via abstract machine,” International Journal of Information
Security, vol. 13, no. 1, pp. 15–23, 2014. [Online]. Available:
https://doi.org/10.1007/s10207-013-0219-4[19] A. Marcedone, Z. Wen, and E. Shi, “Secure dating with four or
fewer cards,” Cryptology ePrint Archive, Report 2015/1031, 2015,
https://eprint.iacr.org/2015/1031.
[20] A. Koch, S. Walzer, and K. Härtel, “Card-based cryptographic
protocols using a minimal number of cards,” in Advances in
Cryptology—ASIACRYPT 2015, ser. Lecture Notes in Computer

Protocol 4. The five-card trick [3]1) PrivatePut, 1, ( ♥ ♣   ), ( ♣ ♥   )2) PrivatePut, 2, (   ♣ ♥ ), (   ♥ ♣ )3) PublicPut, (  ♥  )4) (Turn, {3})5) (Shuf, {π | π = (1 2 3 4 5)i , 0 ≤ i ≤ 4})6) (Turn, {1, 2, 3, 4, 5})7) if visible seqence includes ♥ ♥ ♥ then8)
(Return, x1 ∧ x2 = 1)
9) else10)(Return, x1 ∧ x2 = 0)

If we take all big or small balls in all bags, we write itas (TakeAll, S ).
• (MoveBetweenBags, p1 , p2 , S ) for p1 , p2 ∈ {1, 2, . . . , k}
and S ∈ {“small”,“big”}: This moves a ball (whose sizeis specified by S ) in the p1 -th bag into the p2 -th bag
without revealing the color of the moved ball. If the p1 th bag includes only balls of the same size, S is omitted.
B. Efficient Committed-Format AND Protocol

Science, T. Iwata and J. H. Cheon, Eds., vol. 9452. Berlin,
Heidelberg: Springer, 2015, pp. 783–807. [Online]. Available: https://doi.org/10.1007/978-3-662-48797-6_32[21] O. Goldreich, S. Micali, and A. Wigderson, “How to play ANY
mental game,” in ACM Symposium on Theory of Computing, ser.
STOC ’87. New York: ACM, 1987, pp. 218–229. [Online]. Available:
https://doi.org/10.1145/28395.28420

Appendix A
A Pseudocode of Card-based AND protocol with Five Cards
We show a pseudocode of the five-card trick proposed by
Den Boer [3] in Protocol 4, where formal descriptions ofactions are derived in [18], and PrivatePut and PublicPut are
defined in a similar way to our ball-based model.
Appendix B
Protocols with Different Kinds of Balls
In this section, we discuss efficient committed-format
AND/NOT protocols that can also realize any Boolean function by introducing two kinds of balls with different sizes.
Moreover, we propose a “COPY” protocol that duplicates aninput commitment without revealing any information about the
input value.
A. Extended Model
We hereinafter encode a Boolean value with two bags, eachof which contains a single ball, as follows:{{◦}}, {{•}} = 0,{{•}}, {{◦}} = 1.

(12)Note that this encoding rule is a special version of (10).
Let us introduce two kinds of balls with different sizes. We
denote by and  a red ball and a white ball, respectively,
which are bigger than • and ◦. We hereinafter call {•, ◦} smallballs and { , } big balls. We assume that we can distinguishsmall balls and big balls in a bag by hands. For example, if
we have a bag {{ , , •, ◦}}, we can take only big (or small)balls out of the bag.
For the discussion about a protocol with different kinds ofballs, let us extend actions in Definition 2 as follows.
• (Take, p, S ) for p ∈ {1, 2, . . . , k} and S ∈ {“small”,“big”}:
This takes a ball out of the p-th bag, such that the size ofthe taken ball is specified by S . If the p-th bag includes
only balls of the same size, the description of S is omitted.

In this subsection, we present an AND protocol that produces a commitment to the logical AND of a given input
commitments. We call such a protocol a committed-format
AND protocol. Before describing it, let us mention the idea
behind the protocol.
a) Idea: See (11) again. Remember that in ourcommitted-format AND protocol shown in Section V-A, B2
and B3 are merged in the final step to produce an output
commitment, increasing the number of required (white) balls
for the protocol. Let us consider how to make it efficient.
Suppose that given input commitments to x1 ∈ {0, 1} andx2 ∈ {0, 1}, we proceed in the same way to the committedformat AND protocol until merging B3 with B2 . The resulting
configurations will be as follows:(; {{◦}}, {{•, ◦}}, {{◦, ◦}}; [•], [], []) ( p200 , p201 , p210 , 0),(; {{◦}}, {{◦, ◦}}, {{•, ◦}}; [•], [], []) ( p200 , p201 p210 , 0),(; {{•}}, {{◦, ◦}}, {{◦, ◦}}; [•], [], []) (0, 0, 0, p11 ),where empty bags and trays are omitted. Our idea is that
decreasing the number of white balls in B2 and B3 by threeyields a commitment to x1 ∧ x2 . To achieve this, we first moveballs in B3 into B2 ; the resulting configurations will be as
follows:(; {{◦}}, {{•, ◦, ◦, ◦}}; [•], [])(p00 , p01 , p10 , 0),(; {{•}}, {{◦, ◦, ◦, ◦}}; [•], [])(0, 0, 0, p11 ),Then, we put and  into B1 and B2 , respectively (and put
three ◦, ◦, ◦ into B1 ). As seen later, these big balls “preserve”
the current order of the two bags. The resulting configurations
will be as follows:(; {{ , ◦, ◦, ◦, ◦}}, {{, •, ◦, ◦, ◦}}; [•], []) (p00 , p01 , p10 , 0),(; {{ , •, ◦, ◦, ◦}}, {{, ◦, ◦, ◦, ◦}}; [•], []) (0, 0, 0, p11 ).
To decrease the number of white balls in B1 and B2 , we first
shuffle B1 and B2 (after moving the ball on T 1 ):(; {{ , ◦, ◦, ◦, ◦}}, {{, •, ◦, ◦, ◦}}; [], []) ( p200 , p201 , p210 , 0),(; {{, •, ◦, ◦, ◦}}, {{ , ◦, ◦, ◦, ◦}}; [], []) ( p200 , p201 , p210 , 0),(; {{ , •, ◦, ◦, ◦}}, {{, ◦, ◦, ◦, ◦}}; [], []) (0, 0, 0, p211 ),(; {{, ◦, ◦, ◦, ◦}}, {{ , •, ◦, ◦, ◦}}; [], []) (0, 0, 0, p211 ).
Then, we can take all small balls without revealing any
information about the inputs; if B1 includes •, the resulting
configuration will be as follows:(; {{}}, {{ }}; [•, ◦, ◦, ◦], [◦, ◦, ◦, ◦])(p00 , p01 , p10 , 0),(; {{ }}, {{}}; [•, ◦, ◦, ◦], [◦, ◦, ◦, ◦])(0, 0, 0, p11 ),Now, one can see that B1 and B2 is a “commitment” to x1 ∧x2 with big balls. Then, we put • and ◦ into B1 and B2 ,respectively:(; {{, •}}, {{ , ◦}}; [], []) (p00 , p01 , p10 , 0),(; {{ , •}}, {{, ◦}}; [], []) (0, 0, 0, p11 ).
Now, one can see that the number of white balls has been
decreased by three from (8). Then, we shuffle B1 and B2 :(; {{, •}}, {{ , ◦}}; [], []) ( p200 , p201 , p210 , 0),(; {{ , ◦}}, {{, •}}; [], []) ( p200 , p201 , p210 , 0),Protocol5. The efficient AND protocolin committed format:[ , , ◦, ◦, ◦, ◦, ◦], 4, 2, {0, 1}2 , Q, A .

(; {{ , •}}, {{, ◦}}; [], []) (0, 0, 0, p211 ),(; {{, ◦}}, {{ , •}}; [], []) (0, 0, 0, p211 ).

Initial state:

As seen from the above configurations, we can obtain acommitment to x1 ∧x2 after taking all big balls and rearranging
B1 and B2 according to the order of the taken big balls.
b) Description: Given two commitments to x1 ∈ {0, 1}
and x2 ∈ {0, 1}, our efficient committed-format AND protocol
proceeds as shown in Protocol 5. We denote by B1 and B2
two bags constituting a commitment to x1 and by B3 andB4 those constituting a commitment to x2 . Hereinafter, forsuccessive actions (PublicPut, b1 , p) and (PublicPut, b2 , p), we
simply write (PublicPut, b1 b2 , p).
The correctness and security of the protocol can be confirmed from its diagram dipicted in Fig. 6.
Note that in contrast to the committed-format AND protocol
shown in Section V-A, our efficient one shown in this subsection always requires 11 (two big and nine small) balls, fourbags, and a expected number of four repetitions, i.e., constant.
C. COPY Protocol
In this subsection, we present a COPY protocol. Given a
commitment to x ∈ {0, 1}, our COPY protocol produces two
commitments to x. Remember that we decrease the number ofballs by using and  in the above committed-format AND
protocol. Our COPY protocol proceeds in a similar way that
we “increase” the number of balls in each bag constituting the
input commitment to x.
The correctness and security of our COPY protocol can be
confirmed from its diagram. Due to the page length limitation,
its description and diagram are omitted.
D. How to Construct a Protocol for Any Function
We now have committed-format AND, COPY, and NOT
protocols as shown in Sections B-B and B-C. Based on these
protocols, we can construct a protocol for any function as
follows. If we want to compute an arbitrary function f given
commitments to each of the inputs, we first create a Boolean
circuit representing f , and then construct a protocol based on
the circuit by combining AND/COPY/NOT protocols.

([
([
([
([

, , ◦, ◦, ◦, ◦, ◦]; {{◦}}, {{•}}, {{◦}}, {{•}}; [], [], [], []), , ◦, ◦, ◦, ◦, ◦]; {{◦}}, {{•}}, {{•}}, {{◦}}; [], [], [], []), , ◦, ◦, ◦, ◦, ◦]; {{•}}, {{◦}}, {{◦}}, {{•}}; [], [], [], []), , ◦, ◦, ◦, ◦, ◦]; {{•}}, {{◦}}, {{•}}, {{◦}}; [], [], [], [])(p00 , 0, 0, 0)(0, p01 , 0, 0)(0, 0, p10 , 0)(0, 0, 0, p11 )Steps:
1) (MergeBags, 3, 1)
2) (PublicPut, ◦, 2)3) (PublicPut, ◦, 4)4) while(1)5)(Shuf, {1, 2, 4})
6)(Take, 1, “small00 )7)
if taken ball = • then
8)
break
9)
else
10)
(Back, ◦, 1)
11)(PublicPut, ◦, 1)12) (MergeBags, 4, 2)13) (PublicPut, ◦ ◦ ◦ , 1)14) (PublicPut, , 2)15) (Shuf, {1, 2})16) (TakeAll, “small”)
17) if visible conf. = ([•, ◦, ◦, ◦], [◦, ◦, ◦, ◦]) then18)
(BackAll)
19)(PublicPut, •, 1)
20)(PublicPut, ◦, 2)21) else
22)(BackAll)
23)(PublicPut, •, 2)
24)(PublicPut, ◦, 1)25) (Shuf, {1, 2})26) (TakeAll, “big”)
27) if visible conf. = ([ ], []) then28)
(Result, 1, 2)29) else
30)(Result, 2, 1)

(p00 , 0, 0, 0)(0, p01 , 0, 0)(0, 0, p10 , 0)(0, 0, 0, p11 )(; {{◦}}, {{•}}, {{◦}}, {{•}}; [], [], [], [])(; {{◦}}, {{•}}, {{•}}, {{◦}}; [], [], [], [])(; {{•}}, {{◦}}, {{◦}}, {{•}}; [], [], [], [])(; {{•}}, {{◦}}, {{•}}, {{◦}}; [], [], [], [])(MergeBags, 3, 1)(PublicPut, ◦, 2)(PublicPut, ◦, 4)(; {{◦, ◦}}, {{◦, ◦}}, {{}}, {{•, ◦}}; [], [], [], [])(; {{•, ◦}}, {{•, ◦}}, {{}}, {{◦, ◦}}; [], [], [], [])(; {{•, ◦}}, {{◦, ◦}}, {{}}, {{•, ◦}}; [], [], [], [])(; {{•, •}}, {{◦, ◦}}, {{}}, {{◦, ◦}}; [], [], [], [])(p00 , 0, 0, 0)(0, p01 , 0, 0)(0, 0, p10 , 0)(0, 0, 0, p11 )(Shuf, {1, 2, 3})(; {{◦, ◦}}, {{•, ◦}}, {{•, ◦}}; [], [], [])(; {{•, ◦}}, {{•, ◦}}, {{◦, ◦}}; [], [], [])(; {{•, ◦}}, {{◦, ◦}}, {{•, ◦}}; [], [], [])(; {{•, •}}, {{◦, ◦}}, {{◦, ◦}}; [], [], [])(; {{◦, ◦}}, {{•, •}}, {{◦, ◦}}; [], [], [])(; {{◦, ◦}}, {{◦, ◦}}, {{•, •}}; [], [], [])(Back, ◦, 1)(PublicPut, ◦, 1)(Shuf, {1, 2, 3})( p300 , p301 , p310 , 0)
( p300 , p301 , p310 , 0)
( p300 , p301 , p310 , 0)(0, 0, 0, p311 )(0, 0, 0, p311 )(0, 0, 0, p311 )(Take, 1)• is taken with prob. 1/3.

◦ is taken with prob. 2/3.
(; {{◦}}, {{•, ◦}}, {{•, ◦}}; [◦], [], [])(; {{•}}, {{•, ◦}}, {{◦, ◦}}; [◦], [], [])(; {{•}}, {{◦, ◦}}, {{•, ◦}}; [◦], [], [])(; {{◦}}, {{•, •}}, {{◦, ◦}}; [◦], [], [])(; {{◦}}, {{◦, ◦}}, {{•, •}}; [◦], [], [])( p300 , p301 , p310 , 0)
( p600 , p601 , p610 , 0)
( p600 , p601 , p610 , 0)(0, 0, 0, p211 )(0, 0, 0, p211 )(; {{◦}}, {{•, ◦}}, {{◦, ◦}}; [•], [], []) ( p200 , p201 , p210 , 0)(; {{◦}}, {{◦, ◦}}, {{•, ◦}}; [•], [], []) ( p200 , p201 , p210 , 0)(; {{•}}, {{◦, ◦}}, {{◦, ◦}}; [•], [], []) (0, 0, 0, p11 )(MergeBags, 3, 1)(PublicPut, ◦ ◦ ◦ , 1)
(PublicPut, , 2)(; {{ , ◦, ◦, ◦, ◦}}, {{, •, ◦, ◦, ◦}}; [], []) (p00 , p01 , p10 , 0)(; {{ , •, ◦, ◦, ◦}}, {{, ◦, ◦, ◦, ◦}}; [], []) (0, 0, 0, p11 )(Shuf, {1, 2})• is taken out of B2 with prob. 1/2.

(; {{ , ◦, ◦, ◦, ◦}}, {{, •, ◦, ◦, ◦}}; [], [])(; {{, •, ◦, ◦, ◦}}, {{ , ◦, ◦, ◦, ◦}}; [], [])(; {{ , •, ◦, ◦, ◦}}, {{, ◦, ◦, ◦, ◦}}; [], [])(; {{, ◦, ◦, ◦, ◦}}, {{ , •, ◦, ◦, ◦}}; [], [])( p200 , p201 , p210 , 0)
( p200 , p201 , p210 , 0)(0, 0, 0, p211 )(0, 0, 0, p211 )(TakeAll, “small”)(; {{ }}, {{}}; [◦, ◦, ◦, ◦], [•, ◦, ◦, ◦]) (p00 , p01 , p10 , 0)(; {{}}, {{ }}; [◦, ◦, ◦, ◦], [•, ◦, ◦, ◦]) (0, 0, 0, p11 )(BackAll)(PublicPut, •, 2)(PublicPut, ◦, 1)• is taken out of B1 with prob. 1/2.
(; {{}}, {{ }}; [•, ◦, ◦, ◦], [◦, ◦, ◦, ◦]) (p00 , p01 , p10 , 0)(; {{ }}, {{}}; [•, ◦, ◦, ◦], [◦, ◦, ◦, ◦]) (0, 0, 0, p11 )(BackAll)(PublicPut, •, 1)(PublicPut, ◦, 2)(; {{ , ◦}}, {{, •}}; [], []) (p00 , p01 , p10 , 0)(; {{, ◦}}, {{ , •}}; [], []) (0, 0, 0, p11 )(; {{, •}}, {{ , ◦}}; [], []) (p00 , p01 , p10 , 0)(; {{ , •}}, {{, ◦}}; [], []) (0, 0, 0, p11 )(Shuf, {1, 2})(; {{, •}}, {{ , ◦}}; [], [])(; {{ , ◦}}, {{, •}}; [], [])(; {{ , •}}, {{, ◦}}; [], [])(; {{, ◦}}, {{ , •}}; [], [])(Shuf, {1, 2})( p200 , p201 , p210 , 0)
( p200 , p201 , p210 , 0)(0, 0, 0, p211 )(0, 0, 0, p211 )(TakeAll, “big”)
is taken out of B2 with prob. 1/2.

(; {{•}}, {{◦}}; [], [ ]) (p00 , p01 , p10 , 0)(; {{◦}}, {{•}}; [], [ ]) (0, 0, 0, p11 )⇒ (Result, 2, 1)

is taken out of B1 with prob. 1/2.

(; {{◦}}, {{•}}; [ ], []) (p00 , p01 , p10 , 0)(; {{•}}, {{◦}}; [ ], []) (0, 0, 0, p11 )⇒ (Result, 1, 2)

Fig. 6: A diagram of the committed-format AND protocol, given two commitments to x1 ∈ {0, 1} and x2 ∈ {0, 1}, where weomit the tray T 0 and renumber the positions of the bags after deleting unused empty bags.