Another Use of the Five-Card Trick: Card-Minimal Secure Three-Input Majority Function Evaluation

Starting from the five-card trick proposed by Den Boer (EUROCRYPT’ 89), many card-based protocols performing secure multiparty computations with a deck of physical cards have been devised. However, the five-card trick is considered to be still the most elegant, easy-to-understand and practical protocol, which enables two players to securely evaluate the AND value of their private inputs using five cards. In other words, for more than thirty years, in the research area of card-based cryptography, we have not discovered any protocols that are as simple and beautiful as the five-card trick.

In this study, making use of the five-card trick, we design a novel easy-to-understand protocol which securely evaluates the three-input majority function using six cards. That is, by applying a simple shuffle, we reduce a secure three-input majority computation to evaluating the AND value. By virtue of a direct application of the five-card trick, our proposed majority protocol is extremely simple enough for lay-people to execute. In addition, one advantage is that ordinary people such as high school students will be able to learn the concept of logical AND/OR operations and the majority function as well as their relationship through our majority protocol, providing a nice tool of pedagogical significance. Thus, we believe that our new protocol is no less practical and beautiful than the five-card trick.

1. 1.

   Malicious behaviors during the private operations have been discussed in [2, 11, 18, 19].

We thank the anonymous referees, whose comments have helped us improve the presentation of the paper. We would like to thank Hideaki Sone for his cooperation in preparing a Japanese draft version at an earlier stage of this work. This work was supported in part by JSPS KAKENHI Grant Numbers JP19J21153 and JP21K11881.

Authors and Affiliations

1. Tohoku University, Sendai, Japan

   Kodai Toyoda & Takaaki Mizuki

2. The University of Electro-Communications, Tokyo, Japan

   Daiki Miyahara

3. National Institute of Advanced Industrial Science and Technology, Tokyo, Japan

   Daiki Miyahara & Takaaki Mizuki

Corresponding authors

Correspondence to Kodai Toyoda , Daiki Miyahara or Takaaki Mizuki .

Editors and Affiliations

1. Presidency University, Kolkata, India

   Avishek Adhikari

2. University of Stuttgart, Stuttgart, Germany

   Ralf Küsters

3. University of Leuven and imec, Leuven, Belgium

   Bart Preneel

A Transformation to Committed Format

In this section, we show how to transform our non-committed-format protocol proposed in Sect. 2 to a committed-format one. Subsequently, we give the description of the derived committed-format majority protocol.

1.1 A.1 How to Transform

The transformation is inspired by the five-card Las Vegas AND protocol proposed by Abe et al. [3]. Briefly, their protocol realizes to output a commitment to \(x \wedge y \,\), by adding further manipulations to the five-card trick. Since the output in our proposed protocol is derived by using (the four variants of) the five-card trick, it is possible to obtain a commitment to \(\mathsf {maj}(a,b,c)\) in a similar way to their protocol.

Here is the idea behind their protocol [3].

1. 1.

   Perform Steps 1 to 3 of the five-card trick shown in Sect. 1.1:

   
2. 2.

   Turn over the center card; suppose that appears:

   

   At this time, the resulting sequence of cards is one of the following four cases:

   

3. 3.

   Turn the center card face down. For the sake of illustration, let us represent the sequence as follows:

   

   Observe that, in the cases (ii) and (iv), if we let the first and second cards be a commitment to \(x \in \{0,1\}\) and the third and fourth ones be a commitment to \(y \in \{0,1\}\), we have \(x \,\oplus \, y = a \wedge b\). Therefore, by applying the committed-format XOR protocol [15] to them, one can obtain a commitment to \(x \oplus y = a \wedge b \,\):

   

   Note that, even if it is the case (i) or (iii), one can still continue to execute the protocol without leaking information, as seen below.

In the next subsection, we present the description of our committed-format protocol using this idea.

1.2 A.2 Description

The following is our committed-format three-input majority protocol.

1. 1.

   Perform Steps 1 to 3 of our non-committed-format protocol presented in Sect. 2.3:

   
2. 2.

   Reveal the first card. Assume that it is black, i.e., the result will be \(\heartsuit \)-based:

   

   (In the case where a red card is shown, it works by interchanging the black cards and the red cards.)

3. 3.

   Reveal the fourth card. If appears, turn it over and apply a random cut to the second through sixth cards; then, return to this step. If appears, turn it over and go to the next step.

4. 4.

   Apply the XOR protocol [15] to the second through fifth cards as follows.

   1. (a)

      Rearrange the order of the sequence as

      

   2. (b)

      Apply a random bisection cut to the second through fifth cards:

      
   3. (c)

      Rearrange the order of the sequence as

      

5. 5.

   Reveal the second and third cards.

   1. (a)

      If or appears, we obtain a commitment to \(\mathsf {maj}(a,b,c)\) as follows:

      

      In the latter case, by swapping the left and right cards, we obtain a commitment to \(\mathsf {maj}(a,b,c)\).

   2. (b)

      If appears, then turn them over:

      

      and rearrange the order of the sequence as

      

      Then, apply a random cut to the second through sixth cards and return to Step 3.

      

Let us find the number of required shuffles for this committed-format protocol. The AND protocol proposed by Abe et al. takes the average of seven shuffles to terminate [3]. Since we apply a random bisection cut first in our protocol, it terminates with the expected number of eight shuffles in total. (It should be noted that a recent technique presented in [4] will reduce the number of shuffles further).

1.3 A.3 Pseudocode

A pseudocode for our committed-format majority protocol is depicted in Algorithm 2.

1.4 A.4 Correctness and Security

To verify the correctness and security of our proposed committed-format majority protocol, we describe its KWH-tree in Fig. 2; it guarantees that our protocol is correct and secure.

The KWH-tree of our committed-format majority protocol

Full size image

Reprints and permissions

© 2021 Springer Nature Switzerland AG

Policies and ethics