How to Implement a Random Bisection Cut
Itaru Ueda1 , Akihiro Nishimura1 , Yu-ichi Hayashi2 , Takaaki Mizuki3 , andHideaki Sone3
1

Graduate School of Information Sciences, Tohoku University
6–3–09 Aramaki-Aza-Aoba, Aoba, Sendai 980–8579, Japan{itaru.ueda.t6,akihiro.nishimura.p3}[atmark]dc.tohoku.ac.jp
2
Faculty of Engineering, Tohoku Gakuin University
1–13–1 Chuo, Tagajo, Miyagi 985–8537, Japan
3
Cyberscience Center, Tohoku University
6–3 Aramaki-Aza-Aoba, Aoba, Sendai 980–8578, Japantm-paper+cardsebi[atmark]g-mail.tohoku-university.jp

Abstract. By using a deck of cards, it is possible to realize a securecomputation. In particular, since a new shuﬄing operation, called arandom bisection cut, was devised in 2009, many eﬃcient protocols havebeen designed. The shuﬄe functions in the following manner. A sequenceof cards is bisected, and the two halves are swapped randomly. This
results in two possible cases, depending on whether the two halves of thecard sequence are swapped or not. Because there are only two possibilities
when a random bisection cut is performed, it has been suggested that
information regarding the result of the shuﬄe could sometimes be leaked
visually. Thus, in this paper we propose some methods for implementing
a random bisection cut without leaking such information.
Keywords: Cryptography, Card-based protocols, Real-life hands-on
cryptography, Secure multi-party computations

1

Introduction

It is known that by using a deck of cards, we can realize secure computations. For
example, consider a secure AND computation of bits a ∈ {0, 1} and b ∈ {0, 1},
i.e., assume that we would only like to know the value of a ∧ b. By utilizing a
black card ♣ and a red card ♥ , we can represent the value of a bit as follows:♣ ♥ = 0, ♥ ♣ = 1.
According to this encoding, each of the input bits a and b can be represented by
two face-down cards of diﬀerent colors:? ? ? ? .
     abThis paper appears in Proceedings of TPNC 2016. The ﬁnal publication is available
at Springer via http://dx.doi.org/10.1007/978-3-319-49001-4_5.

2

I. Ueda, A. Nishimura, Y. Hayashi, T. Mizuki, and H. Sone

Table 1: Some of committed AND protocols# of # of Type of Avg. #colors cards shuﬄe of trials
Crépeau and Kilian [2] 4
10RC
6
Niemi and Renvall [12] 2
12
RC
2.5
Stiglic [15]28RC2Mizuki and Sone [10]
2
6
RBC
1
RC: Random Cut, RBC: Random Bisection Cut

A pair of face-down cards (such as in the above example) is called a commitment.
That is, the two cards on the left constitute a commitment to a, and the two
cards on the right constitute a commitment to b. As in this example, the cards
we use are either black cards ♣ or red cards ♥ , whose backs are assumed to be
identical ? . As shown in Table 1, many protocols have been designed to performa secure AND computation, among which we now introduce the Mizuki-Sone
AND protocol [10], designed in 2009. Given commitments to inputs a and b alongwith two additional cards ♣ ♥ , the protocol works as follows.
1. A commitment to 0 is placed between the two input commitments:? ? ♣ ♥ ? ? → ? ? ? ? ? ? .
            
a

b

a

0

b

2. Rearrange the sequence order as follows:? ? ? ? ? ?
QQ
sQ? ? ? ? ? ? .
3. Apply a random bisection cut:
? ? ?  ? ? ? → ? ? ? ? ? ? .

A random bisection cut is a shuﬄing operation that bisects a sequence ofcards and swaps the two halves randomly. Therefore, the shuﬄe results in
two possible cases, depending on whether the two halves are swapped or not,each with a probability of 1/2.
4. Rearrange the sequence order as follows:? ? ? ? ? ?

@
@

R @
@
R
+

? ? ? ? ? ? .

How to Implement a Random Bisection Cut(a) Bisect a sequence of cards

3(b) Shuﬄe the two halvesFig. 1: Execution of a random bisection cut

5. Turn over the two left-most cards. Then, we are able to obtain a commitment
to a ∧ b as follows:♣ ♥ ? ? ? ? or ♥ ♣ ? ? ? ? .
    
a∧b

a∧b

Although we omit an explanation regarding the correctness and secrecy ofthis protocol, one can conﬁrm that it outputs a commitment to a ∧ b using six
cards after one execution of the random bisection cut [10]. (A protocol such as
this that outputs commitments is called a committed protocol.)In practice, humans can perform a random bisection cut by shuﬄing the two
halves after bisecting a given sequence of cards, as illustrated in Figure 1. Thus,
given a sequence of six cards
1

2

3

4

5

6

4

5

? ? ? ? ? ? ,a random bisection cut results in
1

2

3

4

5

6

? ? ? ? ? ?

or

6

1

2

3

? ? ? ? ? ? ,with a probability of 1/2 for each possibility, where the numbers attached to thecards are for the sake of convenience.
Following the computational model formalized in [4, 8], this random bisection
cut can be described as follows:(shuﬄe, {id, (1 4)(2 5)(3 6)}),
where id represents the identity permutation, and an expression such as (1 4)represents a cyclic permutation. Therefore, id indicates that the two halves are
not swapped, and the permutation (1 4)(2 5)(3 6) indicates that the two halves
are swapped. Historically, random bisection cuts ﬁrst appeared when a six-card
AND protocol was designed in 2009 [10]. Even before that, some committed AND
protocols had been designed. These earlier protocols employed the random cut
as a shuﬄing operation, as shown in Table 1. A random cut refers to a cyclic
shuﬄing operation. For example, given eight face-down cards
1

2

3

4

5

6

7

8

? ? ? ? ? ? ? ? ,4

I. Ueda, A. Nishimura, Y. Hayashi, T. Mizuki, and H. Sonea random cut results in one of the following eight cases, each with a probabilityof 1/8:
1

2

3

4

5

6

7

8

2

3

4

5

6

7

8

1

8

1

2

3

4

5

6

7

? ? ? ? ? ? ? ? , ? ? ? ? ? ? ? ? , ... , ? ? ? ? ? ? ? ? .
Therefore by following the computational model in [4, 8], we can similarly describe
the random cut as(shuﬄe, {id, π, π 2 , π 3 , π 4 , π 5 , π 6 , π 7 }) ,where π = (8 7 6 5 4 3 2 1).

Table 2: Some other protocols# of # of Type of Avg. #colors cards shuﬄe of trials◦ Non-committed AND Protocols
den Boer [1]2
5RC1
Mizuki-Kumamoto-Sone [7] 2
4
RBC
1◦ Committed XOR ProtocolsCrépeau-Kilian [2]
4
14
RC
6
Mizuki-Uchiike-Sone [11]
2
10
RC
2
Mizuki-Sone [10]
2
4
RBC
1

As seen in Table 1, committed AND computations have become more eﬃcientby virtue of the introduction of the random bisection cut in 2009. This introduction
also provided the additional beneﬁt that we were able to improve the eﬃciency
of non-committed AND computations and committed XOR computations, asdetailed in Table 2. In addition, further eﬃcient protocols have been designed
using random bisection cuts [3, 5, 6, 13, 14].
As explained above, card-based protocols are intended in practice to be executed by humans, who would like to actually perform secure computations using
a real deck of cards. Hence, when we execute a card-based protocol, it is expectedthat all players gather at the same physical location, and perform operations
such as shuﬄes in public, as in the case of ordinary card games [9].
In order to implement a random cut in such a situation, it is suﬃcient thateach player cuts a sequence of face-down cards in turn until all players are satisﬁedwith the result. Indeed, we note that in practice it is relatively easy to implementa random cut such that nobody is able to determine the result of the shuﬄe atall. We will discuss this further in Section 4.
Meanwhile, when we execute a random bisection cut in reality, as illustrated
in Figure 1, there exists a concern that the result of the shuﬄe may leak, because
there are only two possibilities, i.e., the two halves of the card sequence areswapped or not. Therefore, this paper provides some methods for executing arandom bisection cut securely.

How to Implement a Random Bisection Cut

5This paper is composed as follows. In Section 2, we present some methods
for implementing a random bisection cut using auxiliary tools. In Section 3,
we propose methods to reduce the execution of a random bisection cut tothe execution of random cuts using dummy cards. In Section 4, we discuss
implementations of the random cut, and conﬁrm through a basic experimentthat humans are able to implement random cuts securely, implying that random
bisection cuts can also be implemented securely.

2

Executing a Random Bisection Cut Using AuxiliaryTools

In this section, we provide methods for implementing a random bisection cut by
using auxiliary tools that consist of everyday objects.
2.1

The Use of Paper Clips, Envelopes, or Boxes

When players operate a random bisection cut, if they are not familiar withplaying cards and have diﬃculty shuﬄing the two halves such that each halfstays together, as in Figure 1(b), then they may want to secure each half using
paper clips or envelopes [7, 10]. By using these auxiliary tools, we are able to ﬁx
each of the two halves together as shown in Figure 2. Following this, it suﬃces
to swap the two bundles of cards randomly.
However, as explained in Section 1, the result of the shuﬄe could be revealed
when we execute a random bisection cut in public. That is, someone may counthow many times the two bundles are swapped. To avoid such a leak of information,
one solution is that each player shuﬄes the two bundles behind his/her backor under a table, so that other players cannot see whether the two bundles areswapped or not. In this case, it may be preferable to use envelopes or boxes (asillustrated in Figure 3) rather than paper clips, to avoid malicious actions.
However, as mentioned in Section 1, it is desirable for all actions to be
performed in front of all players and/or third parties publicly. Therefore, in
Sections 2.2 and 3 we present implementations of random bisection cuts where
every action can be performed completely in public.

Fig. 2: Each half is placed in an envelope

Fig. 3: Each half is placed in a box

6

I. Ueda, A. Nishimura, Y. Hayashi, T. Mizuki, and H. Sone(a) Separator andtwo halves(b) One half isplaced on the separator(c) The pile consisting of one half
and the separator
is ﬂipped(d) The other halfis placed on the
pileFig. 4: Setup for spinning throw(a) Hold the pile of cards(b) Throw the pile like a coin

Fig. 5: A spinning throw

2.2

The Use of a Separator Card and Rubber BandIn this subsection, we present a novel method of performing a random bisection
cut using a separator card with a rubber band. Both sides of the separator (asshown in the middle of Figure 4 (a)) must be indistinguishable.
The method works as follows. First, a sequence of cards is bisected, with one
half placed on the separator, as shown in Figure 4(b). Second, the pile consistingof one half and the separator is turned over, as in Figure 4(c)1 . Third, the otherhalf is placed on the pile, as shown in Figure 4(d), and these are ﬁxed together
using a rubber band, to prevent the cards from scattering. Next, the pile isthrown in a spinning manner (as illustrated in Figure 5). We call this action aspinning throw. After the pile is caught, we are completely unsure of which halfis on the top. Finally, the rubber band is removed, and the actions described in
Figure 4 are undone in reverse order, from (d) to (a). In this manner, we canconduct a random bisection cut securely.

3

Executing a Random Bisection Cut Using Dummy
Cards

In this section, we propose methods for reducing the execution of a random
bisection cut to the execution of random cuts using dummy cards.
1

The separator prevents information regarding the color of cards from being leaked.

How to Implement a Random Bisection Cut

7

It is assumed throughout this section that we want to apply a random bisection
cut to a sequence of 2n cards, where n ≥ 2:
n cards

n cards







? ? ··· ?  ? ? ··· ? .
3.1

The Use of Cards of Other Colors

Here, as dummy cards we use cards whose backs are ? and faces are diﬀerent
from ♣ and ♥ , namely  or ♠ . Speciﬁcally, we use 2s  and 2t ♠ cards,
where s, t ≥ 1. That is, we have a total of 2(s + t) additional cards.
By using such dummy cards, we are able to implement a random bisection
cut as follows.
1. Place dummy cards with their faces down, as follows:n cards

dummy cards

dummy cards

n cards










? ? ··· ? ? ? ··· ? ? ? ··· ? ? ? ··· ? ,where the dummy cards are arranged as below:
s cards

t cards






? ? ··· ? ? ? ··· ? .






♠ ♠

♠

2. Apply a random cut:
? ? ··· ? ? ? ··· ? ? ? ··· ? ? ? ··· ?

.

3. Turn over the left-most card.
(a) If the face-up card is  , then turn over cards forward (in the right-handdirection) until t ♠ cards appear. Now, we have determined the positionsof all of the dummy cards, and hence we can remove them all:t cards

n cards

s+t cards

n cards

           
 ···  ♠ ··· ♠ ? ··· ?  ··· ♠ ? ··· ?  ···  .
(b) If the face-up card is ♠ , then turn over cards backward (aside fromcyclic rotations) until s  cards appear. Now, we have determined thepositions of all of the dummy cards, and hence we can remove them all:n cards

s+t cards

n cards

s cards

           
♠ ··· ♠ ? ··· ?  ··· ♠ ? ··· ?  ···  ♠ ··· ♠ .
(c) If the face-up card is ♣ or ♥ , then turn it over again and return toStep 2.

8

I. Ueda, A. Nishimura, Y. Hayashi, T. Mizuki, and H. Sone

In this manner, after all of the dummy cards are removed, a random bisection
cut has been completed.
In Step 3, the probability that either (a) or (b) occurs is (s + t)/(n + s + t).
Therefore, we are able to implement a random bisection cut using 2(s + t) dummycards after an average of (n + s + t)/(s + t) executions of the random cut.
This method of discarding dummy cards was ﬁrst devised by Crépeau andKilian [2], when they proposed some random permutation generating protocols.
Here, we have adopted their idea.
Regarding the parameters s and t, there is a trade-oﬀ between the numberof required cards and the average number of executions of the random cut. For
example, if we want to implement the Mizuki-Sone six-card AND protocol [10]with an average number of two random cuts, then we require six additionaldummy cards, and hence this requires more cards than Stiglic’s eight-card AND
protocol [15] (although the former might have the advantage that it is simpler tounderstand its correctness).
Moreover, we can select the parameters as s = 1 and t = 0, i.e., the above
method works even with only two  dummy cards (and no ♠ cards).
3.2

Utilizing Vertical Asymmetricity of the Backs of Cards

In Section 3.1, we required additional types of cards to reduce the execution of arandom bisection cut to the execution of random cuts. On the other hand, in
this section we do not use such additional cards, but rather employ the samecards that we have used before ( ♣ and ♥ ) as dummy cards.
Our method works as follows. We exploit the vertical asymmetricity of thebacks of cards ? . Because the back is asymmetric, it can be seen as either ?
or ¿ , depending on the setting. Now, we describe how to implement a random
bisection cut by executing a random cut with 2m additional dummy cards, wherem ≥ 1. (Here, any cards of type ♥ or ♣ can be used as dummy cards.)
1. Arrange the 2m additional dummy cards with their upsides facing down, as
follows:
m cards
n cards
m cards
n cards









¿ ¿ ··· ¿ ? ? ··· ? ¿ ¿ ··· ¿ ? ? ··· ? .
2. Apply a random cut:
? ? ··· ? ¿ ¿ ··· ¿ ? ? ··· ? ¿ ¿ ··· ¿.

3. Cyclically shift the ﬁrst several cards to the rightmost positions, withoutchanging their order, so that the ﬁrst card will be a dummy card:? ··· ? ¿ ··· ¿ ? ··· ? ¿ ··· ¿ ? ··· ?
↓m cards

n cards

m cards

n cards










¿ ¿ ··· ¿ ? ? ··· ? ¿ ¿ ··· ¿ ? ? ··· ? .

How to Implement a Random Bisection Cut

9

4. Remove all dummy cards:
n cards

n cards






? ? ··· ? ? ? ··· ? .
In this manner, by using 2m additional cards and executing one random cut,
we are able to implement a random bisection cut. For example, the Mizuki-Sone
six-card AND protocol [10] can be implemented with one random cut by adding
two additional cards.
In this method, we must apply a random cut to cards that have asymmetricbacks, and hence information regarding the result of the shuﬄe could be leaked
more easily than with cards that have identical backs.
Taking this into account, we will discuss secure implementations of the random
cut in the next section.

4

Secrecy of Implementations of the Random Cut

In Section 3, we proposed some methods for reducing the execution of a random
bisection cut to the execution of random cuts. In general, it is believed that arandom cut can be securely implemented by humans. To support this belief,
we discuss the secure implementation of a random cut by performing a shuﬄewith a real deck of cards. Speciﬁcally, in Section 4.1 we point out that a naive
implementation is not secure, and then propose a secure implementation that wecall the “Hindu cut.” In Section 4.2, we demonstrate that the “Hindu cut” is infact a secure implementation of a random cut by conducting a basic experiment.
4.1

Discussion Regarding Implementations

Because a random cut consists of a cyclic shuﬄe, its simple implementation
proceeds as in Figure 6: some cards (or a card) are taken from the top of the pile,and then moved to the bottom of the pile (this is called a cut). At every cut, weshould change the number of cards that are to be moved. To verify whether thissimple implementation is secure, we conducted an experiment.
We asked eleven students in our laboratory to observe one author executing asimple implementation of a random cut with a pile of eight cards. We then asked
them to track a speciﬁc card.
While most of the participants were unable to recognize the location of
the targeted card and gave up guessing, three participants were able to follow
the move and track the speciﬁc card with a high probability. Therefore, in thepresence of people who are capable of following the cutting move, such a simple
implementation is not secure.
Thus, we require an alternative secure implementation of the random cut. The
three participants who were able to break the simple implementation informed
us that they could visually observe how many cards were moved at every cut,and summed up the numbers. Hence, the key consideration is how to make it
impossible for people to count the number of cards moved during every cut.

10

I. Ueda, A. Nishimura, Y. Hayashi, T. Mizuki, and H. Sone

Fig. 6: Simple execution of a random cut

Fig. 7: Execution of a “Hindu cut”

Fig. 8: A card sequence
including two upsidedown cards

One idea is to move cards from the bottom to the top of the pile insteadof moving them from the top to the bottom when executing a cut operation.
By doing so, it becomes diﬃcult to recognize the number of cards that havebeen moved. Moreover, if the positions of the cards are out of alignment, as
in Figure 6, then it is possible to easily recognize the number of cards moved.
Therefore, we should ensure that cards are not out of alignment when we executecut operations.
Based on this idea, we found that a variation of the so-called Hindu shuﬄe(shown in Figure 7) is eﬀective for preventing the cut operation from being
revealed (we call this the Hindu cut). In fact, the three participants mentioned
above were unable to guess the speciﬁc cards, and hence they all gave up following
the implementation of a Hindu cut.
Next, in order to verify the security of the Hindu cut, we conducted anotherexperiment based on the method presented in Section 3.2, which exploits thevertical asymmetricity of the backs of cards. That is, we placed two cards (out ofeight) with their upsides down and applied a Hindu cut, as illustrated in Figure 8.
Clearly, these upside-down cards are advantageous to people who wish to track
the move. Furthermore, we asked the participants to guess the location of a
speciﬁc upside-down dummy card out of the two. (There are only two possibilities
after the shuﬄe, by virtue of the two upside-down cards.) As a result, even thethree participants mentioned above gave up guessing the speciﬁc dummy card.
4.2

Conﬁrming the Security of the Hindu Cut

In order to conﬁrm the security of the Hindu cut more, we requested 72 participants (as shown in Table 3) who came to the Sone-Mizuki laboratory booth in
the Open Campus of Tohoku University in 2016, to watch a movie depicting theexecution of a Hindu cut. In the movie, we employ the same sequence of cards as
in Section 4.1. We arranged two upside-down cards, named A and B, and applied

How to Implement a Random Bisection Cut

Table 3: Number of examinees

Table 4: Result of our experiment# ofratio of Male andparticipants Female (M:F)
72
62 : 10

Choice# of answers(1) I have no idea.
64(2) Deﬁnitely, it must be A.
5(3) Deﬁnitely, it must be B.
3

11

a Hindu cut. The time taken for the execution was 30 seconds, and the movie
can be found at https://youtu.be/Zm-IpuOobIY. Following the Hindu cut, we
asked every participant whether he/she could determine which card was the left
upside-down card with certainty. Each participant was asked to choose his/heranswer from the following three options.
(1) I have no idea2 .
(2) Deﬁnitely, it must be A.
(3) Deﬁnitely, it must be B.
The result is presented in Table 4. Most of the participants submitted theanswer (1), whereas ﬁve people gave the answer (2), and three gave the answer(3)3 . For the participants whose answers were (2) or (3), we requested that they
watch additional movies and answer again, in order to rule out wild guesses. As
a result, none of the participants were able to answer correctly for all of the ﬁvemovies that we had prepared.
Thus, we can conclude that the Hindu cut is an eﬀective method for implementing a random cut securely, although we recognize that a more careful andwide ranging investigation is still required.

5

Conclusion

The random bisection cut has played an important role in improving card-based
protocols. However, implementation issues have not previously been discussed.
Therefore, in this paper we have proposed some novel methods for implementing
the random bisection cut, and demonstrated that humans are able to implement
it in practice.

Acknowledgments
We thank the anonymous referees, whose comments have helped us to improve
the presentation of the paper. We would like to oﬀer our special thanks to
Kohei Yamaguchi, who provided an excellent implementation of the random
bisection cut, the spinning throw, as introduced in Section 2.2. In addition, we
2

If a participant could not track the move with conﬁdence, then he/she is assumed
not to have any motivation to reveal secret information from the result of the shuﬄe.
3
We note that the correct answer was B.

12

I. Ueda, A. Nishimura, Y. Hayashi, T. Mizuki, and H. Sone

are grateful to all members of the Sone-Mizuki laboratory in Tohoku University,
who cooperated with our experiment in Section 4. This work was supported by
JSPS KAKENHI Grant Number 26330001.

References
1. den Boer, B.: More eﬃcient match-making and satisﬁability: the ﬁve card trick. In:
Quisquater, J.J., Vandewalle, J. (eds.) Advances in Cryptology — EUROCRYPT’89, Lecture Notes in Computer Science, vol. 434, pp. 208–217. Springer Berlin
Heidelberg (1990)
2. Crépeau, C., Kilian, J.: Discreet solitary games. In: Stinson, D.R. (ed.) Advancesin Cryptology — CRYPTO ’93, Lecture Notes in Computer Science, vol. 773, pp.
319–330. Springer Berlin Heidelberg (1994)
3. Ishikawa, R., Chida, E., Mizuki, T.: Eﬃcient card-based protocols for generating ahidden random permutation without ﬁxed points. In: Calude, C.S., Dinneen, M.J.
(eds.) Unconventional Computation and Natural Computation, Lecture Notes in
Computer Science, vol. 9252, pp. 215–226. Springer International Publishing (2015)
4. Koch, A., Walzer, S., Härtel, K.: Card-based cryptographic protocols using aminimal number of cards. In: Iwata, T., Cheon, J. (eds.) Advances in Cryptology– ASIACRYPT 2015, Lecture Notes in Computer Science, vol. 9452, pp. 783–807.
Springer Berlin Heidelberg (2015)
5. Mizuki, T.: Card-based protocols for securely computing the conjunction of multiple
variables. Theoretical Computer Science 622, 34–44 (2016)
6. Mizuki, T., Asiedu, I.K., Sone, H.: Voting with a logarithmic number of cards.
In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds.) Unconventional
Computation and Natural Computation, Lecture Notes in Computer Science, vol.
7956, pp. 162–173. Springer Berlin Heidelberg (2013)
7. Mizuki, T., Kumamoto, M., Sone, H.: The ﬁve-card trick can be done with four
cards. In: Wang, X., Sako, K. (eds.) Advances in Cryptology — ASIACRYPT
2012, Lecture Notes in Computer Science, vol. 7658, pp. 598–606. Springer Berlin
Heidelberg (2012)
8. Mizuki, T., Shizuya, H.: A formalization of card-based cryptographic protocols via
abstract machine. International Journal of Information Security 13(1), 15–23 (2014)
9. Mizuki, T., Shizuya, H.: Practical card-based cryptography. In: Ferro, A., Luccio,F., Widmayer, P. (eds.) Fun with Algorithms, Lecture Notes in Computer Science,
vol. 8496, pp. 313–324. Springer International Publishing (2014)
10. 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, Lecture Notes in Computer
Science, vol. 5598, pp. 358–369. Springer Berlin Heidelberg (2009)
11. Mizuki, T., Uchiike, F., Sone, H.: Securely computing XOR with 10 cards. The
Australasian Journal of Combinatorics 36, 279–293 (2006)
12. Niemi, V., Renvall, A.: Secure multiparty computations without computers. Theoretical Computer Science 191(1–2), 173–183 (1998)
13. Nishida, T., Hayashi, Y., Mizuki, T., Hideaki, S.: Securely computing three-input
functions with eight cards. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences 98(6), 1145–1152 (2015)
14. Nishida, T., Hayashi, Y., Mizuki, T., Sone, H.: Card-based protocols for any
boolean function. In: Jain, R., Jain, S., Stephan, F. (eds.) Theory and Applicationsof Models of Computation, Lecture Notes in Computer Science, vol. 9076, pp.
110–121. Springer International Publishing (2015)

How to Implement a Random Bisection Cut

13

15. Stiglic, A.: Computations with a deck of cards. Theoretical Computer Science259(1–2), 671–678 (2001)