Der Artikel taucht in den Bereich der kartenbasierten Kryptographie ein und konzentriert sich auf die Verwendung eines Standardkartenspiels im privaten Modell. Es führt effiziente Protokolle für grundlegende Logikgatter wie AND, OR und XOR ein, die weniger Karten erfordern als herkömmliche Methoden. Bemerkenswert ist, dass die Verfasser ein bahnbrechendes Abstimmungsprotokoll mit drei Mehrheiten präsentieren, bei dem nur drei Karten verwendet werden, was eine deutliche Verbesserung gegenüber bestehenden Methoden darstellt. Die Protokolle sind so konzipiert, dass sie robust sind, keine Zufälligkeit der Spieler erfordern und daher sowohl praktisch als auch sicher sind. Der Artikel bietet eine umfassende Untersuchung dieser Protokolle, ihrer Konstruktion und ihrer Sicherheitsnachweise und liefert wertvolle Erkenntnisse für Experten auf dem Gebiet der Kryptographie und sicheren Berechnung.
KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
Abstract
Card-based cryptography is a secure computation protocol realized by using physical cards. There are two models on card-based cryptography: public and private models. We adopt private one that allows players to handle cards privately. While much of the existing works for card-based cryptography use two-colored cards, it is also a vital task to construct an efficient protocol with playing cards. In the public model, 2n cards are necessary for any n-bit input protocol since at least two cards are required to express a Boolean value. It holds true for both two-colored and playing-card settings. On the other hand, the private model enables us to construct a protocol with fewer than 2n cards. However, all existing protocols that achieve such properties are only in the two-colored setting. This paper shows that the private model enables us to construct a protocol with fewer than 2n cards using the playing cards. We first show two-bit input protocols with fewer than four cards for logical operations, AND, OR, and XOR. Furthermore, we show a three-input majority voting protocol using only three cards, which is constructed by combining our AND and OR protocols. Notably, our proposed protocols require no randomness. All operations are deterministic and depend only on players’ private inputs.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
1.1 Backgrounds
Secure computation is a cryptographic protocol that enables mutually distrustful parties to compute a function jointly while keeping their inputs secret [6, 29]. While general cryptographic protocols are supposed to be implemented on computers, there is a line of work to realize it using physical objects with manual operations. Such protocols are suitable as educational and recreational tools since they allow for hands-on and visual understanding of the procedures.
Card-based cryptography is a variant of secure computation, which is realized with physical cards [4, 5, 17]. Most of the existing works for card-based cryptography are based on two-colored cards, e.g., [5, 8, 16, 18, 19, 23, 28]. They use two types of cards such that the faces have different colors, black and red , and the same type of cards are indistinguishable. Their backsides have the same suit . Besides, some works use a standard deck of cards (or playing cards), such as typically used to play the poker game [7, 9, 15, 24]. Unlike two-colored cards, each playing card in a deck is identifiable since every card has a unique face pattern. Hence, it requires different techniques to construct a protocol using playing cards than two-colored ones.
Anzeige
In addition to the card types, we can classify card-based protocols with operating models. There are two types of operating models in card-based cryptography: public and private models. The public model supposes that all operations are done publicly. The shuffle is a key operation to achieve the privacy of players’ inputs under the condition that all operations are made public. It enables players to generate a random number that no players can identify in a public area. In this model, using face-down cards is the only way to express players’ inputs in a secret state. Since at least two cards are necessary for an arbitrary representation of a binary value, an n-bit input protocol must use at least 2n cards.
The private model allows players to operate cards privately [13, 22], such as by hiding cards behind their backs. Precisely, instead of the shuffle, this model uses a private permutation, an operation to permute a card order privately, and a communication, an operation to pass cards to another player. It is known that this model allows us to break the lower bound regarding the number of cards in the public model. This is thanks to the fact that players can express their inputs secretly by using private permutations depending on the values. Indeed, several works showed n-bit input protocols with less than 2n cards [2, 3, 20, 21, 25]. These results, however, are only for the two-colored card setting. Hence, it is non-trivial whether the private model can break the lower bound in the playing card setting.
1.2 Our Contribution
This paper is devoted to showing that the private model can break the lower bound of the public model in the playing card setting. For some specific functions, we demonstrate that an n-bit input protocol can be realized with less than 2n playing cards: We first show that a two-bit input AND protocol can be realized with three cards (see Table 1). Note that the public model requires at least four cards to implement the protocol. Afterwards, we show that a two-bit input OR protocol can be realized by applying the De Morgan’s law to this protocol. Furthermore, we present a two-bit input XOR protocol using two cards. Based on the above AND and OR protocols, we construct a three-input majority voting protocol using only three cards (see Table 2). This is the first work to realize a three-input majority voting protocol using playing cards in the private model.
Notably, none of our proposed protocols depend on players’ private randomness. That is, there is no operation that generates a random number. This is the preferable property since a random generation is generally a very costly operation.
Table 1
An efficiency comparison among secure AND protocols with playing cards. PPs and Rand. Gens. stand for private permutations and randomness generations, respectively
We consider an honest-but-curious adversary that exactly follows a protocol but is curious to learn anything more from rightfully obtained information. A protocol fulfills privacy if an arbitrary player cannot learn any additional information than the output from his/her view of the protocol.
Two-colored cards. Card-based cryptography based on two-colored cards uses black and red cards. (For simplicity, we sometimes omit the frame and write them as \(\clubsuit \) and \(\heartsuit \).) Their back sides have the same pattern and indistinguishable, described as .
Playing cards. Excluding the joker, playing cards consist of 52 distinct cards. To represent a card deck of playing cards, we use the following notation:
As in the two-colored card setting, all cards have the same pattern on their backs.
2.2 Operating Models
2.2.1 Public Model
In the public model, players perform all card operations in a public area, such as on the table. A protocol based on this model consists of three operations: permutation, reverse, and shuffle. The permutation is to change a card order deterministically. The reverse is an operation to change the face of a card. The shuffle is a probabilistic permutation to a card order, which is a key ingredient to achieve privacy under the setting that all operations are run publicly. While a shuffle is performed in a public area, it assumes that the permutation result cannot be identified for all players, including the player who runs it. A known method of implementing a shuffle is repeating permutation with sufficient times. Thus, the shuffle is the most costly operation. The computational cost of a protocol is evaluated with the number of shuffles.
In the public model, using face-down cards is the only way to express a player’s input value privately. Also, a party must use at least two cards to express an arbitrary Boolean value, such as the following encoding:
where \(1 \le i<j \le 52\). We call a face-down cards expressing a Boolean value a commitment. Note that, even if we encode a bit using a single card, such as \(\clubsuit =0,\,\heartsuit =1\), a player must hold two cards to represent an arbitrary Boolean value. Thus, 2n cards are necessary to realize an n-bit input protocol.
2.2.2 Private Model
This model allows players to permute cards secretly, such as by hiding them behind their backs. It consists of the following operations.
Public permutation: permuting a card order publicly.
Private permutation (PP): permuting a card order privately.
Public reverse: changing the face of a card publicly.
Communication: handing over cards to another player.
The computational cost is evaluated by the number of PPs and communications. Although the PP allows players to permute a card order depending on their randomness, generating a random number puts a burden on the player. From this viewpoint, we further add the number of random generation processes to the efficiency evaluation.
We can realize a shuffle with the combination of PPs and communications [22]. Thus, a protocol based on the public model can be executed on the private model by converting each shuffle to a combination of PPs and communications. On the other hand, since a PP enables players’ malicious behaviors, the private model needs to assume the semi-honest model that deals with only honest-but-curious adversaries.1
The private model allows a player to express his/her input using PP instead of the commitment. Thanks to this fact, the private model can break the lower bounds 2n regarding the number of cards in the public model. As an example, we show Marcedone et al.’s work [13] for secure AND protocol. Protocol 1 shows the procedure. Since a secure AND protocol is 2-bit inputs, four cards are necessary to realize the protocol in the public model. On the other hand, Protocol 1 breaks the lower bound and uses only three cards by using a PP-based input. See steps 1 and 3. Although Alice uses a commitment to express her input, Bob expresses his input by a PP and does not use any additional cards. It is known that the lower bound can be broken for various protocols other than secure AND protocol using PPs [2, 3, 20, 21, 25].
×
3 Proposed Protocols for Logic Gates with Playing Cards
This section shows three protocols based on playing cards; three-card AND, three-card OR, and two-card XOR protocols. In this section, let Alice and Bob hold \(a,b \in \{0,1\}\), respectively.
3.1 Three-Card AND Protocol
We first show our three-card AND protocol, which is based on Protocol 1. Before presenting our construction, we observe the problems that arise when the cards in Protocol 1 are simply replaced by playing cards.
By replacing two club cards with and a heart card with , the first step becomes as follows:
×
Suppose that we thereafter apply the same steps as Protocol 1. In other words, Alice and Bob perform steps 2–4 in Protocol 1 after the above step 1.
Table 3 is the card order at step 4. See the left card of each row, which is the revealed card at the step. Since the card is only if \(a \wedge b =1\), the protocol fulfills the correctness. However, the protocol does not achieve the privacy. It is due to the fact that the reveal card has two patterns, i.e., and , when \(a\wedge b=0\). For instance, if the revealed card is , players can identify the inputs as \((a,b)=(0,1)\). To resolve this issue, we modify the protocol so that the revealed card is the same for the three cases regarding \(a \wedge b =0\).
We here observe the card order of the output phase, i.e., step 4, from Alice’s view, and realize the modification. Since Bob does not touch the right card, Alice can identify it as follows:
If \(a=0\), the right card is .
If \(a=1\), the right card is .
Note that, if \(a=0\), Alice knows that the output always becomes zero regardless of Bob’s input. We utilize this fact and modify the protocol so that Alice chooses as the output when \(a=0\), i.e., she chooses the right card as the output if \(a=0\). That is, the modified protocol applies to the output card representing \(a \wedge b=0\).
See Table 3, the card orders corresponding to \(a=1\) are as follows:
If \(b=0\), the card order is .
If \(b=1\), the card order is .
Since we assigned as the output card to express \(a \wedge b=0\), it must be the output also when \((a,b)=(1,0)\). Thus, Alice chooses the center card as the output if \(a=1\) in our modification. As a result, is always revealed when \(a \wedge b =0\). Also, only when \(a \wedge b =1\), becomes the output card. In summary, our three-card AND protocol proceeds as in Protocol 2. Note that step 5 corresponds to additional Alice’s process discussed above.
Security Proof of Protocol2. We first note that, in an AND protocol, a player who inputs 1 can uniquely identify the other player’s input from the output. For achieving the privacy, it is necessary to guarantee that a player whose input is 0 cannot identify the other player’s input. See Table 4 that shows the card order at step 6 of Protocol 2. The output card corresponding to \(a \wedge b=0\) is always . That is, it is the same for the three cases, \((a,b)=(0,0),(0,1),(1,0)\). (Note that the output card is only card that is revealed in the protocol.) Hence, in the case of \(a=0\), Alice cannot tell whether \(b=0\) or not since she cannot distinguish between the two cases, \((a,b)=(0,0),(0,1)\). This is also true for Bob. In the case of \(b=0\), Bob cannot identify whether \((a,b)=(0,0)\) or \((a,b)=(1,0)\), and cannot learn anything about Alice’s input. Moreover, all operations depending on players’ inputs are hidden to the other players by the assumption of PP. Hence, no information beyond the output leaks from the process, and thus the protocol fulfills privacy. \(\square \)
Table 3
The card order at step 4 of naïve construction for AND protocol
This subsection presents our three-card OR protocol, which is constructed based on the AND protocol. We aim to construct it such that the output format is the same as the AND protocol. That is, and represent \(a \vee b=0\) and \(a \vee b =1\), respectively. The format match is helpful to construct a three-input majority voting protocol, described in Sect. 4.
To derive from the AND protocol to an OR protocol, we use the De Morgan’s law, \(a \vee b = \lnot (\lnot a \wedge \lnot b)\). From the equation, we can construct an OR protocol by making the following two changes to the AND protocol.
I.
Negating the input values.
II.
Negating the output value.
Change I can be easily realized by which Alice and Bob inputs \(\lnot a\) and \(\lnot b\), respectively. (See Table 5 that shows the result of applying change I to Protocol 2.)
Table 5
The card order at step 6 of Protocol 2 applied change I
Regarding change II, note that it is non-trivial to apply the negation operation to the output since we use a single card to express a bit.2 We realize the negation by interchanging the positions of and in the output phase. To realize the interchange, we swap and in Alice’s first card arrangement. By this swapping, the positions of and in the output phase are reversed, and we obtain the negation.
Protocol 3 shows our three-card OR protocol that is achieved by applying changes I and II to our three-card AND protocol. See step 1 that corresponds to change II. Compared to step 1 of Protocol 2, we can see that the placements of and are reversed. (Note that change I reverses the sequences of cards \(a=0\) and \(a=1\) in the step.)
See Table 6 that shows the card order at step 6. We can see the correctness from the table. Since we can confirm the privacy by the same way as Protocol 2, we omit the proof here.
3.3 Two-Card XOR Protocol
Nakai et al. [21] showed a two-card XOR protocol in the two-colored setting. Note that for protocols consisting of two cards, there is no difference between the two-colored and the playing-card settings. That is, by mapping cards as and , we can convert a protocol with two-colored cards into a protocol with the playing cards that achieves the same functionality. Protocol 4 presents the two-card XOR protocol realized by mapping cards of Nakai et al.’s protocol as the above.
4 Three-input Majority Voting Protocol with Three Playing Cards
This section shows our three-input majority voting protocol with three cards. In this section, let Alice, Bob, and Carol hold \(a,b,c \in \{0,1\}\), respectively. The function for three-input majority voting is formally described as:
Following Nakai et al.’s work [21], to construct a three-input majority voting protocol, we use the following equation:
$$\begin{aligned} \textsf{maj}(a,b,c) = \left\{ \begin{array}{lcl} a\wedge b &{} \,\,\,\,\textrm{if}&{} c=0, \\ a\vee b &{} \,\,\,\,\textrm{if}&{} c=1. \end{array} \right. \end{aligned}$$
(2)
That is, we obtain the protocol by constructing a protocol that outputs \(a \wedge b\) for \(c=0\) and \(a \vee b\) for \(c=1\).
Recall changes I and II used to convert the AND protocol into the OR protocol, described in Sect. 3.2. In our three-input majority voting protocol, Alice and Bob perform the same procedure as the AND protocol. Intuitively, Carol takes on the role of deciding whether or not to apply changes I and II to their protocol. That is, if \(c=0\), she does virtually nothing, and Alice and Bob run the AND protocol as is. Otherwise, Carol applies changes I and II to the AND protocol secretly, Alice and Bob run the OR protocol without realizing this fact. As a result, they can obtain \(a \wedge b\) or \(a \vee b\) according to Carol’s input as described in Eq. (2) without revealing Carol’s input.
As an important point, players can obtain \(a \wedge b\) and \(a \vee b\) as the same encoding, i.e., and express zero and one, respectively, for both cases. Thanks to this, Alice and Bob cannot tell whether the output corresponds to the AND or OR operation and do not learn Carol’s input from patterns of the output card.
4.2 Three-input Majority Voting Protocol
Protocol 5 shows our three-input majority voting protocol based on the idea, shown in the previous subsection. See step 1 that corresponds to change II. Indeed, in the case of \(c=0\), the card order at the end of step 3 is if \(a=0\) and otherwise. That is the same result as Alice’s first arrangement of Protocol 2. Similarly, in the case of \(c=1\), the card order at the end of step 3 is if \(a=0\) and otherwise, which is the same result as Alice’s first arrangement of Protocol 3.
Step 9 corresponds to change I. That is, Carol’s permutation in step 9 with \(c=1\) realizes negations for Alice and Bob’s inputs in steps 5 and 7. Table 7 shows the card order at step 10 of Protocol 5. From the table, we can see that the card order for \(c=0\) (resp. \(c=1\)) is the same as the AND (resp. OR) protocol (see also Tables 4 and 6).
Security Proof of Protocol 5. The output card corresponding to \(\textsf{maj}(a,b,c)=0\) and \(\textsf{maj}(a,b,c)=1\) is always and , respectively. Hence, players cannot get more information than the output from the revealed card at step 10. Moreover, all operations depending on players’ inputs are kept secret by the assumption of PP. Hence, no information beyond the output leaks from the process, and thus the protocol fulfills privacy. \(\square \)
5 Conclusion
This paper focused on card-based cryptography using a standard deck of cards in the private model. Using two-colored cards, it is known that the private model can break the lower bound regarding the number of cards in the public model. Our motivation was to show that we can break the lower bound based also on a deck of cards.
We first showed efficient protocols for two-input AND, OR, and XOR operations. Note that four cards are necessary to construct these protocols in the public model. Based on Marcedone et al.’s work [13], we constructed a three-card AND protocol. By applying De Morgan’s law to this protocol, we realized a three-card OR protocol. Also, we presented a two-card XOR protocol based on Nakai et al.’s work [21]. Furthermore, we proposed three-input majority voting protocols using only three cards. Based on Eq. (2), this protocol was constructed by the composition of our AND and OR protocols. As a notable feature, our protocols rely on no players’ randomness, i.e., there is no need to generate a random number in an arbitrary process.
Acknowledgements
This work was supported by JSPS KAKENHI Grant Numbers JP23H00468, JP23H00479, JP23K16880, JP23K17455, JP23K24846, JP23K21644, JP23K21668, JP22H03590, JP22KJ1362, JP21H03441, JP21H03395, and JP18H05289, JST CREST JPMJCR23M2, and MEXT Leading Initiative for Excellent Young Researchers.
Declarations
Conflict of interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
and red
, and the same type of cards are indistinguishable. Their backsides have the same suit
. Besides, some works use a standard deck of cards (or playing cards), such as typically used to play the poker game [7, 9, 15, 24]. Unlike two-colored cards, each playing card in a deck is identifiable since every card has a unique face pattern. Hence, it requires different techniques to construct a protocol using playing cards than two-colored ones.
and red
cards. (For simplicity, we sometimes omit the frame and write them as \(\clubsuit \) and \(\heartsuit \).) Their back sides have the same pattern and indistinguishable, described as
.
As in the two-colored card setting, all cards have the same pattern
on their backs.
where \(1 \le i<j \le 52\). We call a face-down cards expressing a Boolean value a commitment. Note that, even if we encode a bit using a single card, such as \(\clubsuit =0,\,\heartsuit =1\), a player must hold two cards to represent an arbitrary Boolean value. Thus, 2n cards are necessary to realize an n-bit input protocol.
and a heart card with
, the first step becomes as follows: 
only if \(a \wedge b =1\), the protocol fulfills the correctness. However, the protocol does not achieve the privacy. It is due to the fact that the reveal card has two patterns, i.e.,
and
, when \(a\wedge b=0\). For instance, if the revealed card is
, players can identify the inputs as \((a,b)=(0,1)\). To resolve this issue, we modify the protocol so that the revealed card is the same for the three cases regarding \(a \wedge b =0\).
as the output when \(a=0\), i.e., she chooses the right card as the output if \(a=0\). That is, the modified protocol applies
to the output card representing \(a \wedge b=0\).
.
.
as the output card to express \(a \wedge b=0\), it must be the output also when \((a,b)=(1,0)\). Thus, Alice chooses the center card as the output if \(a=1\) in our modification. As a result,
is always revealed when \(a \wedge b =0\). Also, only when \(a \wedge b =1\),
becomes the output card. In summary, our three-card AND protocol proceeds as in Protocol 2. Note that step 5 corresponds to additional Alice’s process discussed above.
.
.
. That is, it is the same for the three cases, \((a,b)=(0,0),(0,1),(1,0)\). (Note that the output card is only card that is revealed in the protocol.) Hence, in the case of \(a=0\), Alice cannot tell whether \(b=0\) or not since she cannot distinguish between the two cases, \((a,b)=(0,0),(0,1)\). This is also true for Bob. In the case of \(b=0\), Bob cannot identify whether \((a,b)=(0,0)\) or \((a,b)=(1,0)\), and cannot learn anything about Alice’s input. Moreover, all operations depending on players’ inputs are hidden to the other players by the assumption of PP. Hence, no information beyond the output leaks from the process, and thus the protocol fulfills privacy. \(\square \)
and
represent \(a \vee b=0\) and \(a \vee b =1\), respectively. The format match is helpful to construct a three-input majority voting protocol, described in Sect. 4.
and
in the output phase. To realize the interchange, we swap
and
in Alice’s first card arrangement. By this swapping, the positions of
and
in the output phase are reversed, and we obtain the negation.
and
are reversed. (Note that change I reverses the sequences of cards \(a=0\) and \(a=1\) in the step.)
and
, we can convert a protocol with two-colored cards into a protocol with the playing cards that achieves the same functionality. Protocol 4 presents the two-card XOR protocol realized by mapping cards of Nakai et al.’s protocol as the above.
and
express zero and one, respectively, for both cases. Thanks to this, Alice and Bob cannot tell whether the output corresponds to the AND or OR operation and do not learn Carol’s input from patterns of the output card.
if \(a=0\) and
otherwise. That is the same result as Alice’s first arrangement of Protocol 2. Similarly, in the case of \(c=1\), the card order at the end of step 3 is
if \(a=0\) and
otherwise, which is the same result as Alice’s first arrangement of Protocol 3.
and
, respectively. Hence, players cannot get more information than the output from the revealed card at step 10. Moreover, all operations depending on players’ inputs are kept secret by the assumption of PP. Hence, no information beyond the output leaks from the process, and thus the protocol fulfills privacy. \(\square \)
