Keywords

1 Introduction

Card-based protocols perform cryptographic tasks such as secure multiparty computation using a deck of physical cards. Most existing studies in this line of research use a two-colored deck consisting of indistinguishable red and black cards, whose backs have the same pattern . The Boolean values are usually encoded as follows:

figure d

If two face-down cards represent a bit \(x\in \{0,1\}\) according to the above encoding rule, then we call them a commitment to x and write it as follows:

figure e

Previous research has proposed many card-based protocols that are capable of securely computing Boolean functions such as the logical AND function. As mentioned above, most prior studies have used a two-colored deck of cards (e.g., [1, 2, 4, 5, 7, 16, 24]); however, there are a few protocols that use a standard deck of playing cards, as introduced below.Footnote 1

1.1 Card-Based Protocols with a Standard Deck of Cards

In 1999, Niemi and Renvall [18] proposed card-based protocols for secure two-input computations (such as computations of the logical AND and XOR) using a commonly available standard deck of playing cards for the first time. Since then, several protocols using such a standard deck have been proposed [6, 9, 10].

A typical deck of playing cards consists of 52 distinct cards excluding jokers; hence, we assume the following deck of 52 numbered cards:

figure f

where all their backs are identical  .

Niemi and Renvall [18] considered, based on two cards and , an encoding scheme such that

(1)

That is, two cards can be represented as 0 if the left number is smaller than the right one; otherwise, they are represented as 1. In this way, similar to the two-colored case, we can consider a commitment to a bit \(x\in \{0,1\}\) with two numbered cards and  , denoted by

figure l

Here, the set \(\{i,j\}\) is called a base of the commitment. We sometimes write

figure m

without the description of a base if it is clear from context or there are multiple possibilities for the base. Note that, swapping the two face-down cards of a given commitment to \(x\in \{0,1\}\) converts it into a commitment to the negation \(\bar{x}\) while keeping the value of x secret; thus, a secure NOT computation is easy.

Based on this encoding, Niemi and Renvall [18] designed card-based protocols. They were followed by a couple of research groups [6, 10], whose advancements will be detailed in the next subsection.

1.2 Existing Protocols

Table 1 presents the existing protocols for the secure computation of the two-input AND function with a standard deck of cards. A protocol that terminates in a finite number of steps is said to be finite, while a protocol with a runtime that is finite in expectation is said to be Las Vegas; the fourth column of Table 1 indicates this.

Niemi and Renvall [18] proposed a Las Vegas two-input AND protocol using five cards; four cards are used to represent input commitments and the remaining card is an auxiliary one.Footnote 2 In other words, given two commitments to bits \(a,b\in \{0,1\}\) along with one additional card, their protocol produces a commitment to \(a\wedge b\) without leaking (revealing) any information about a and b:

figure n

In the (original) Niemi–Renvall protocol [18], the base of the output commitment is always \(\{1,2\}\) and the expected number of required shuffles is 9.5; however, Koch, Schrempp, and Kirsten [6] demonstrated that the expected number of shuffles can be reduced to 7.5 if we allow the base of the output commitment to be either \(\{1,4\}\), \(\{1,5\}\), or \(\{4,5\}\). In this paper, we refer this modified version as to the Niemi–Renvall protocol. As will be seen in Sect. 2.4, this protocol uses only a simple shuffle called a random cut (which is described in Sect. 2.2).

Later, Mizuki [10] proposed a finite two-input AND protocol with eight cards.Footnote 3 This protocol uses only a shuffle action called a random bisection cut (which is described in Sect. 2.3), and the number of required shuffles is four.

In 2021, Koch, Schrempp, and Kirsten [6] proposed a Las Vegas two-input AND protocol with four cards. This protocol uses only a random cut, and its expected number of shuffles is six.

Table 1. The existing two-input AND protocols with a standard deck of cards
Full size table
Table 2. Three-input AND computations with a standard deck of cards
Full size table

1.3 Contribution

Let us consider how to securely compute the three-input AND function:

figure o

Computation of the three-input AND function can be performed by repeatedly applying one of the three existing protocols [6, 10, 18] twice: First, one must obtain a commitment to \(a\wedge b\) by applying a two-input protocol, and then apply the protocol to the commitments to \(a\wedge b\) and c. To perform this, the numbers of required cards and shuffles by Mizuki’s protocol [10] or Koch et al.’s protocol [6] are listed in Table 2.

In this study, we solicit a more efficient computation of the three-input AND. The main contribution of this paper is the novelty of our protocol that directly performs a secure three-input AND computation in a single application. Our protocol is partly based on Niemi and Renvall’s two-input AND protocol [18]. Our protocol uses only six cards, which are necessary for three input commitments; therefore, it uses the same number of cards as two runs of Koch et al.’s protocol [6]. The expected number of shuffles required for our protocol is 8.5, which is 3.5 fewer than the previous best six-card computation (see Table 2).

Overall, our proposed three-input AND protocol is “card-minimal” in the sense that only six cards are necessary under the encoding rule (1). Additionally, our protocol is simple because it uses only random cuts and random bisection cuts as shuffles.

1.4 Outline

This paper is organized as follows: Sect. 2 describes basic terminology in card-based cryptography and introduces the Niemi–Renvall protocol [18]. In Sect. 3, we describe our three-input AND protocol. We conclude this paper in Sect. 4.

2 Preliminaries

In this section, we introduce the actions involved in card-based protocols as well as practical shuffles, specifically the random cut and the random bisection cut, which will be used in our proposed protocol. Additionally, we explain the two-input AND protocol constructed by Niemi and Renvall [18].

2.1 Actions

In card-based protocols, as they have been formalized in [7, 13, 15], there are the following three main actions to be applied to a sequence of n cards.

  • Rearrangement. Apply some permutation \(\pi \in S_n\) to a sequence of n cards, where \(S_n\) denotes the symmetric group of degree n. We write this action as \((\mathsf {perm},{\pi })\):

    figure p

  • Turn. Turn over the t-th card (from the left) for \(t\in \{1,\ldots ,n\}\) in a sequence to check the number of the card. We write this action as \((\mathsf {turn},{\{t\}})\):

    figure q

    In this example, the numbered card displaying a 1 was revealed.

  • Shuffle. Apply a permutation \(\pi \in \varPi \) chosen uniformly randomly from a permutation set \(\varPi \subseteq S_n\). We write this action as \((\mathsf {shuf},{\varPi })\):

    figure r

    Note that it is not possible for an observer to know which permutation in \(\varPi \) was applied.

2.2 Random Cut

A random cut is a shuffling action (denoted by \(\langle \cdot \rangle \)) that shifts a sequence of cards cyclically and randomly. If a random cut is applied to a sequence of n cards, then the resulting sequence becomes one of the following n sequences, each of which occurs with a probability of 1/n:

figure s

This random cut can be written, using a cyclic permutation \(\sigma = (1\,2\,3\,\cdots \,n)\), as

$$ (\mathsf {shuf},{\{\mathsf {id}, \sigma , \sigma ^2\,,\ldots ,\sigma ^{n-1}\}}), $$

where \(\mathsf {id}\) denotes the identity permutation. Hereinafter, we use \(\mathsf {RC}_{1,2,\ldots ,n}\) to represent \(\{\mathsf {id}, \sigma , \sigma ^2\,,\ldots ,\sigma ^{n-1}\}\).

A random cut can be easily performed by human hands, and a secure implementation called the Hindu cut is well known [31, 32].

2.3 Random Bisection Cut

A random bisection cut is a shuffling action invented by Mizuki and Sone [16] in 2009. This shuffle (denoted by \(\left[ \, \cdot \, | \, \cdot \, \right] \)) bisects a sequence of 2n cards and randomly swaps the two halves; the resulting sequence becomes one of the following two sequences:

figure t

That is, the resulting sequence either remains the same as the original one or becomes a sequence where the two halves are swapped with a probability of 1/2. This random bisection cut can be written as follows:

$$ (\mathsf {shuf},{\{\mathsf {id}, (1 \ n\!+\!1)(2 \ n\!+\!2) \cdots (n \ 2n)\}}). $$

Secure implementations using familiar tools were shown in [31, 32]. The random bisection cut has brought many efficient protocols (e.g., [11, 12, 14, 19,20,21]).

2.4 The Niemi–Renvall Protocol

Given two commitments to \(a,b\in \{0,1\}\) along with an additional card, the Niemi–Renvall protocol [18] outputs a commitment to \(a\wedge b\). The procedure is as follows.

  1. 1.

    Place the two input commitments and an additional card and turn it over:

    figure v
  2. 2.

    Rearrange the third and fourth cards:

    figure w

    Now, let us consider the order of , , and in the rearranged sequence; the order is (apart from cyclic rotation) if and only if \((a,b)=(1,1)\), i.e., \(a\wedge b=1\) (whereas the order is if and only if \(a\wedge b =0\)). Therefore, we try to remove and in Steps 3 and 4.

  3. 3.

    Apply a random cut to the sequence of all cards:

    figure ae
  4. 4.

    Turn over the first card; if it is or , then remove it. Otherwise, turn it over. If there is still a or in the sequence, then return to Step 3.

  5. 5.

    The resulting sequence after removing and becomes one as presented in Table 3. Apply a random cut to the sequence and then reveal the first card to obtain the output commitment. (This step was developed by Koch et al. [6].)

    figure al

    If the first card is , then we obtain a commitment to the negation of \(a\wedge b\). In this case, we apply the NOT computation to obtain a commitment to \(a \wedge b\).

Table 3. The sequence after removing and
Full size table

Correctness of this protocol is clear from the above description. Regarding security, since a random cut is applied to the sequence in Step 3, the revealed card in Step 4 is chosen randomly from the sequence. Therefore, no information about the input is leaked. For example, if the number of cards in Step 3 is five, the revealed card in Step 4 should be one in with an equal probability regardless of the input values. In the same manner, no information about the input is leaked when the first card is revealed in Step 5. To summarize, this protocol is correct and secure.

3 Our Three-Input AND Protocol

In this section, we present a three-input AND protocol that requires no additional card, i.e., is card-minimal and uses fewer shuffles as compared to the applications of previous protocols:

figure aq

We begin by describing the idea behind our proposed protocol.

3.1 Idea

Observe the following simple fact about \(a\wedge b\wedge c\):

$$ a\wedge b\wedge c = {\left\{ \begin{array}{ll} 0\quad &{} \text {if c=0,}\\ a \wedge b\quad &{} \text {if c=1.} \end{array}\right. } $$

In other words, to construct a three-input AND protocol, it suffices to simulate a two-input AND protocol if \(c=1\) and to always output 0 if \(c=0\). For this, we borrow the idea behind the Niemi–Renvall protocol [18] introduced in Sect. 2.4.

Remember that their protocol swaps the third and fourth cards in Step 2; this action reverses the order of and if and only if \((a,b)=(1,1)\), i.e., the output is 1. That is, if we skip this step and perform the remaining steps, then the output should be always 0. From this observation, it suffices to swap the third and fourth cards if and only if \(c=1\) and then perform the remaining steps of the protocol. Therefore, in the next subsection, we will describe how to swap two cards according to the value of c (without knowing it).

3.2 Swapping by Value of Commitment

For a sequence of two cards along with a commitment to \(c\in \{0,1\}\) whose base is \(\{i,j\}\), we want to swap the cards if \(c=1\) and we want to keep them unchanged if \(c=0\), without leaking the value of c:

figure at

We call this the swap operation by the commitment to c. The swap operation proceeds as follows (whose procedure is similar to the Mizuki XOR protocol [10]).

  1. 1.

    Assume a target sequence of two cards and a commitment to c (with \(i<j\)):

    figure au
  2. 2.

    Rearrange the second and third cards:

    figure av
  3. 3.

    Apply a random bisection cut to the sequence of all cards:

    figure aw
  4. 4.

    Rearrange the second and third cards:

    figure ax

    Observe that, depending on the value of c, the current sequence satisfies the followings:

    figure ay
    figure az
  5. 5.

    Turn over the third and fourth cards; or should appear with a probability of 1/2.

    1. (a)

      If appear, then output the first and second cards.

    2. (b)

      If appear, then swap the first and second cards and then output them.

3.3 Description of Our Protocol

We now present our three-input AND protocol.

  1. 1.

    Assume three input commitments to \(a,b,c\in \{0,1\}\):

    figure be
  2. 2.

    Apply the swap operation by the commitment to c shown in Sect. 3.2 to the second and third cards, as follows.

    1. (a)

      Rearrange the sequence:

      figure bf
    2. (b)

      Apply a random bisection cut to the last four cards:

      figure bg
    3. (c)

      Apply the inverse rearrangement of Step 2(a):

      figure bh
    4. (d)

      Turn over the fifth and sixth cards: If appear, then do nothing. If appear, then swap the second and third cards.

  3. 3.

    Rearrange the sequence so that the first card becomes appeared in the previous step and then turn it over. Subsequently, apply Steps 3, 4, and 5 of the Niemi–Renvall protocol [18] to the first five cards.

3.4 Correctness and Security

Here, we prove the correctness and security of our three-input AND protocol. Observe that, in the sequence after Step 2 as listed in Table 4, the order of is if and only if \(a\wedge b\wedge c=1\) (whereas it is if and only if \(a\wedge b\wedge c=0\)). From this, it suffices to remove and in the same manner as the Niemi–Renvall protocol [18]. Therefore, our protocol can always output a commitment to \(a\wedge b\wedge c\) by applying Steps 3, 4, and 5 of the Niemi–Renvall protocol [18].

More formally, we prove this by using the KWH-tree [7] as in Figs. 1 and 2. The KWH-tree is a tree-like diagram that shows the transitions of possible sequences of cards along with their respective polynomials in a box, where actions to be applied to the sequence are appended to an edge. In the figure, the probability of \((a,b,c)=(x,y,z)\) is denoted by \(X_{xyz}\). A polynomial annotating a sequence in a box such as \(1/2X_{000}\) represents the conditional probability that the current sequence is the one next to the polynomial, given what can be observed so far on the table.

If the sum of all the polynomials in each box is equal to

$$ \sum _{x,y,z\in \{0,1\}}X_{xyz}, $$

then it is guaranteed that no information about the input is leaked. The KWH-tree of our protocol for Steps 1 and 2 is shown in Fig. 1. The KWH-tree for Step 3 is shown in Fig. 2. From the figures, it can be easily confirmed that the aforementioned condition is satisfied in each box, i.e., our protocol is secure.

Table 4. The possible sequences after Step 2 in our protocol
Full size table
Fig. 1.
figure 1

The KWH-tree for our three-input AND protocol (Steps 1 to 2)

Full size image
Fig. 2.
figure 2

The KWH-tree for our three-input AND protocol (Step 3), where \(X_0=X_{000}+X_{001}+X_{010}+X_{011}+X_{100}+X_{101}+X_{110}\) and \(X_1=X_{111}\). The \(\mathsf {result}\) action indicates the positions of the output commitment.

Full size image

4 Conclusion

In this study, we designed a simple three-input AND protocol using playing cards by only using six cards; in other words, we do not need any additional cards (aside from three input commitments). To the best of our knowledge, this is the first type of protocol that can be used for directly computing a three-input Boolean function with a standard deck of cards.

A natural open problem that presents itself from our research is the construction of efficient AND protocols for more than three inputs. It would also be interesting to investigate whether a finite AND protocol can be constructed using only random cuts even for two inputs. Making use of a standard deck in the “private permutation” setting (e.g., [8, 17, 22, 33]) would be another interesting topic. In addition, it would be worthwhile to construct zero-knowledge proof protocols working only on a standard deck for pencil puzzles, cf. [3, 23, 25, 26].