Card-based cryptography, introduced by den Boer aims to realize multiparty computation (MPC) by using physical cards. We propose several efficient card-based protocols for the millionaires’ problem by introducing a new operation called Private Permutation (PP) instead of the shuffle used in most of existing card-based cryptography. Shuffle is a useful randomization technique by exploiting the property of card shuffling, but it requires a strong assumption from the viewpoint of arithmetic MPC because shuffle assumes that public randomization is possible. On the other hand, private randomness can be used in PPs, which enables us to design card-based protocols taking ideas of arithmetic MPCs into account. Actually, we show that Yao’s millionaires’ protocol can be easily transformed into a card-based protocol by using PPs, which is not straightforward by using shuffles because Yao’s protocol uses private randomness. Furthermore, we propose entirely novel and efficient card-based millionaire protocols based on PPs by securely updating bitwise comparisons between two numbers, which unveil a power of PPs. As another interest of these protocols, we point out they have a deep connection to the well-known logical puzzle known as “The fork in the road.”
Hinweise
A preliminary version of this article appears in proceedings of 15th International Conference on Cryptology and Network Security (CANS2016) [15].
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Introduction
Background and Motivation
Background Consider a scenario where n players \(P_1, P_2, \dots , P_n\) hold private data \(x_1, x_2, \dots ,x_n\) respectively, and they wish to compute a value of a function \(f(x_1, x_2, \dots ,x_n)\) without revealing their own data. In this scenario, it is impossible to hide all information of the players’ inputs, since the computed value \(f(x_1, x_2, \dots ,x_n)\) leaks certain information of their inputs. Hence, we require to hide the information of inputs other than the information of \(f(x_1, x_2, \dots ,x_n)\). The techniques for realizing such a requirement are called multiparty computation (MPC). MPC is one of the most important research topics in cryptography and information security. Actually, MPC has many cryptographic applications such as electronic auctions and electronic votings.
It is known that MPC can be realized by using several cards, and such a special implementation of MPC is called a card-based cryptography [4, 5]. Unlike general MPC protocols implemented on computers, the card-based cryptography is realized by manual operations. Obviously, manual operations take much longer time than the operations on computers. Hence, it is important to reduce the number of steps in the card-based cryptography. Based on a similar reason, smaller number of cards is desirable for an efficient implementation of card-based cryptography.
Anzeige
Much of the research related to card-based cryptography has been devoted to secure computation of logical gates such as AND and XOR,1 since any computation can be implemented by their combinations. The central issue when designing efficient card-based cryptography for logical gates is to minimize the number of cards required in the protocol. For instance, Mizuki–Sone [9] realized AND and XOR operations on two binary inputs with six and four cards, respectively, and recently, Koch–Walzer–Härtel [11] reduced the number of cards to five in AND.2 However, [11] assumes the existence of a special shuffle with non-uniform distribution, and hence, it is defficult to be implemented.3 Thus we adopt Mizuki–Sone protocols [9], which are easy to be implemented, as previous research in the efficiency evaluations.
The randomization is also important in order to realize card-based cryptography. In previous works, a randomization operation called shuffle is considered to be useful for card-based protocols with a smaller number of cards, and the usage of this operation has been extensively studied thus far.
We note that shuffles have two special features: The first feature is that a shuffle in a card-based cryptography specifies a certain permutation, whereas a shuffle in ordinary card games permutes the set of cards in a completely random manner. The second feature is that the result of a permutation must not be known to any players (including the player performing the shuffle). For instance, a random bisection cut [9] is a useful type of shuffles described as follows: an even number of cards are divided into two sets consisting of the same number of cards, and these two sets are permuted (in this case, exchanged) many times until none of the players can recognize how many times the two sets of cards are permuted.
Motivation and Our Idea We observe here that the following two problems exist in card-based protocols for logical gates utilizing shuffles:
1.
Constructing a protocol by using logical gates is a general technique, but it can be less efficient than protocols specially developed to perform a certain function.
2.
Shuffles are too card-oriented operations. From the viewpoint of arithmetic MPC, they cannot be realized by a single operation but can be realized by at least two players to communicate with each other.4
We discuss (1) and (2) in detail before we propose our idea:
Anzeige
(1): It is known that at least one shuffle is necessary for a randomize operation in realizing card-based cryptography. Actually, card-based protocols for logical gates, such as AND, OR and COPY [9], can be realized by using one random bisection cut. This fact implies that it is impossible to make the number of shuffles less than the number of logical gates as long as we construct card-based protocols by the combination of logical gates.5 For instance, consider the case of the millionaires’ problem initiated by Yao’s seminal work [2], which is a secure two-party computation involving a comparison of two numbers without making each millionaire’s wealth public. Comparing two numbers less than \(m\in {\mathbb {N}}\) by logical gates can be realized as in Algo. 1, which involves \(2 \lceil \log m \rceil -1\) AND and \(2 \lceil \log m \rceil -2\) OR times.6 When executing these logical gates, the COPY operation [9] is necessary for copy \(\lnot a_i\) and \(b_i\) in each comparison of bits. Summarizing, \(6 \lceil \log m \rceil -5\) random bisection cuts are necessary in total in order to implement Algo. 1.
We can expect this inefficiency to be resolved if we design a card-based cryptography specialized for the function computed in the protocol, although such improvement has not been studied intensively to date. Proceeding with this idea, it is natural to recall Yao’s solution to the millionaires’ problem [2] since it does not depend on logical gates but specializes in comparing two numbers privately. As we will see in Sect. 3.1, Yao’s protocol involves public key encryption, which is difficult to implement by logical gates, but is easy to realize by using face-down cards without public/private keys! Then, we can show a simple implementation of Yao’s protocol by cards if we get rid of restriction of using logical gates.
(2): When we construct a card-based protocol with shuffles, it would be hard to use arithmetic MPC protocols straightforwardly because arithmetic MPCs normally assume private randomness whereas all operations in a card-based protocol with shuffles must be executed in public. This hardness would be an obstacle to construct card-based protocol for millionaires’ problem based on Yao’s original ideas, and motivates us to also employ the private randomness in card-based cryptography. Hence, in this paper, we explicitly allow such a private operation in card-based cryptography.7 In most of previous works, all operations are performed in public so as to avoid cheating. On the other hand, since we adopt the operation of executing in player’s private area, our card-based protocols are realized under the semi-honest model.
×
In previous works, a shuffle is considered as a building block for randomization, but actually, it is not a single operation from the viewpoint of arithmetic MPC. For instance, a random bisection cut can be realized as follows: Alice first generates a random number \(r_A\) and permutes bisected cards \(r_A\) times behind her back, and sends the permuted cards to the other player, say Bob. Bob privately generates a random number \(r_B\) and permutes bisected cards \(r_B\) times behind his back. If \(r_A\) and \(r_B\) are kept private by Alice and Bob, respectively, this protocol shuffles bisected cards \(r_A+r_B\) times, and no one can know the number of permutations.
Note that such private randomness and private operations (\((r_A,r_B)\) and permutations in this example, respectively) are often used in arithmetic MPC. We call such a permutation behind one’s back Private Permutation (PP). The introduction of PPs makes it easy to see that shuffles, including a random bisection cut, generally consist of at least two PPs and one communication. Introducing PPs, evaluations of card-based protocols are almost parallel to those of arithmetic MPC. Concretely, the number of PPs and communications is considered as computational cost, and the number of cards is considered as memory cost.
As shown above, the concept of a PP is motivated by (1) and (2). We propose two essentially different protocols for Millionaires’ problem based on this concept, and call them proposed protocols I and II. The evaluations of our results presented in this paper are summarized in Table 1, where we use the number of communications, PPs, and cards as efficiency measures.
We first construct a card-based cryptographic protocol for the millionaires’ problem based on Yao’s solution for two numbers less than or equal to m (proposed protocol I), which does not include logical gates. In the implementation, shuffles are not used, and PPs play a key role instead of shuffles. Even though this protocol is naïve, only one communication and two PPs are sufficient, which is a considerable improvement of card-based cryptography based on logical gates. On the other hand, the number of cards required by the protocol is 2m, which is much worse than the protocol based on logical gates (\(4\lceil \log m \rceil +2\)).
Not only transforming Yao’s solution to card-based cryptography but also we propose an entirely new card-based cryptographic protocol based on PPs (proposed protocol II), which is specially developed to solve the millionaires’ problem. Proposed protocol II is more efficient in terms of the number of communications, PPs, and cards. This protocol succeeds in reducing the number of communications and PPs to almost 1/3 and 1/6, respectively, compared to the protocol for logical gates, whereas the number of cards remains the same (see Proposed protocol II in Table 1). The new protocol compares two numbers bit by bit, starting from the less significant bit, and the compared results are recorded on cards, called storage. The results recorded in the storage need to be kept secret from both Alice and Bob, to solve the millionaires’ problem securely. Hence, we show how to manipulate the storage privately by using PPs.
It is very interesting to note that the idea of proposed protocol II is the same as that of the well-known logical puzzle “The fork in the road”.8 This observation will be introduced when explaining the idea of the proposed protocol II in Sect. 4.1.
Unfortunately, proposed protocol II requires still the same number of cards with the previous work whereas the other measures are evidently improved. Hence, we discuss how to reduce the number of cards in Sect. 4.3. The main idea of this improvement is that inputs are not represented as the sequence of cards but are memorized in player’s mind. This improvement enables the proposed protocol II to realize with only six cards.
This paper is the full version of [15]. We extended the earlier version [15] by proposing a new protocol in Sect. 4.3 that solves the millionaires’ problem with only six cards. We also improved presentations, especially surveys are updated in Sect. 2.3.
Organization
The remaining part of this paper is organized as follows: We introduce several notations, basic operations of cards including PP, and the security notion for card-based cryptography in Sect. 2. In Sect. 3, the card-based cryptography for the millionaires’ problem based on Yao’s protocol is presented. Sect. 4 is devoted to the proposal of a new card-based cryptographic protocol with storage. We also show an improvement of the proposed protocol which reduces the number of cards. We summarize our results in Sect. 5.
Preliminaries
Notations and Basic Operations of Cards
In card-based cryptography, we normally use two types of cards such as
and
. We assume that two cards with the same mark are indistinguishable. We also assume that all cards have the same design on their reverse sides, and that they are indistinguishable and represented as
. The Boolean values 0 and 1 are encoded as
and
, respectively. Note that we regard the sequence of cards as a vector. In this paper, we use the following fundamental card operations [12]. Note that these operations are executed publicly.
Face up:
Face down:
Permutation: e.g.,
A pair of face-down cards for the Boolean value \(x \in \{0,1\}\), is called commitment. In particular, the permutation for a commitment is referred to as swap.
For simplicity,
and
are represented as \(\clubsuit \) and \(\heartsuit \), respectively.
Random Bisection Cut and Private Permutation
Random Bisection Cut This is a key technique to realize efficient card-based cryptography for logical gates, e.g., 6-card AND protocol [9], which is described as follows:
For a positive integer v, suppose that there is a sequence of 2v face-down cards. Denote the left and right halves by \(\mathbf{u} _1\) and \(\mathbf{u} _2\), respectively. Namely, we define
(1)
Then, \(\mathbf{u} _1\) and \(\mathbf{u} _2\) are interchanged or left unchanged with probability 1/2. Depicting this by using figures, one of either
(2)
is selected with a probability 1/2. This operation, called random bisection cut, is executed in public but it is assumed that no player knows whether one of the above is selected.
Shuffles such as random bisection cut are regarded as a convenient randomization technique for implementing card-based cryptography. However, the assumption of shuffle is card-oriented, as is pointed out in Sect1.1, so there is a gap from arithmetic MPC. Concretely, arithmetic MPC cannot accept the following assumptions:
All players cannot identify the random number even if it is generated in public area.
Every player cannot know the random number which is generated by him/herself.
Both assumptions are natural for real shuffles, e.g., in playing cards. It is not possible to assume in arithmetic MPC. However, we realize the same requirements shown in above under the same assumption in arithmetic MPC by allowing private randomness and communications. Concretely, a random bisection cut by Alice can be realized as follows: Alice first generates a random number \(r_A\) and permutes the bisected cards \(r_A\) times behind her back, and sends the permuted cards to the other player, say Bob. Bob privately generates a random number \(r_B\) and permutes the bisected cards \(r_B\) times behind his back. If \(r_A\) and \(r_B\) are kept private by Alice and Bob, respectively, this protocol permutes the bisected cards \(r_A + r_B\) times, and no one can know the number of permutations. As long as we implement card-based cryptography based on logical gates, at least one shuffle such as a random bisection cut is necessary for every logical gate except negation, which would have a highly adverse impact on the efficiency of the protocols.
Private Permutation. We resolve the above-mentioned drawbacks by decomposing the shuffle operation into the private permutations behind the player’s back and the communication between them. Hence, we introduce a new randomization operation called Private Permutation (PP), which can be formalized as follows:
For a positive integer t, let \(\mathbf{c} \in \{\clubsuit ,\heartsuit \}^t\) be a vector consisting of t face-down cards. For a set \({\mathcal {P}}_t\) of all permutations over9\([t]:=\{1,2,\ldots ,t\}\), let \({\mathcal {R}}_t \subset {\mathcal {P}}_t\) be a set of possible permutations. We also define \({\mathcal {R}}_t = \{\pi _0,\pi _1,\ldots , \pi _{|{\mathcal {R}}_t|-1}\}\), where \(\pi _i\) denotes a permutation over [t]. Then, for a positive integer t and a set of possible permutations \({\mathcal {R}}_t\), the private permutation is defined as follows:
Note that the same function was introduced in the previous works [11, 12] although we impose an additional assumption on this function. Namely, we assume that the player executing \(\mathsf {PP}^{[t]}_{{\mathcal {R}}_t}\) keeps s secret, whereas he/she makes the other parameters public, which is easy to realize by permuting the cards behind the player’s back. This requirement was firstly introduced in the conference version os this paper [15] explicitly. We note that, not only the random bisection cut, but also several different types of shuffles, e.g., in [6], can be realized by PPs by specifying \({\mathcal {R}}_t\) appropriately.
For instance, consider the set of permutations capable of randomly interchanging the first and the latter halves of a vector as follows: For a positive integer v, let \({\mathcal {R}}^{\mathsf {bc}}_{2v}:=\{\pi _0,\pi _1\} \subset {\mathcal {P}}_{2v}\) where
Eq. 4 means that \(\pi _0(\mathbf{c} )=(\mathbf{u} _1,\mathbf{u} _2)\) and \(\pi _1(\mathbf{c} )=(\mathbf{u} _2,\mathbf{u} _1)\) for \(\mathbf{c} :=(\mathbf{u} _1,\mathbf{u} _2)\) given by (1). Then, the random bisection cut for 2v cards is represented as \( \mathsf {PP}^{[2v]}_{{\mathcal {R}}^{\mathsf {bc}}_{2v}}(\mathbf{c} ,s)= \pi _s(\mathbf{c} ) \) where s is chosen from \(\{0,1\}\) uniformly at random and it is known only by the player executing this operation. In executing the random bisection cut, for the sequence of cards \(\mathbf{c} \), Alice executes \(\mathsf {PP}^{[2v]}_{{\mathcal {R}}^{\mathsf {bc}}_{2v}}(\mathbf{c} ,r_A)=:\mathbf{c}' \) by using her private randomness \(r_A\in \{0,1\}\), and \(\mathbf{c}' \) is sent to Bob. Bob also executes \( \mathsf {PP}^{[2v]}_{{\mathcal {R}}^{\mathsf {bc}}_{2v}}(\mathbf{c}' ,r_B)\) by using his private randomness \(r_B\in \{0,1\}\).
×
Efficiency Measures. Most of the previous works, e.g., [12, 13], considered the number of shuffles as the computational complexity since shuffle is the most time-consuming operation. On the other hand, in this paper we consider that the computational complexity is evaluated by the number of PPs and communications since such measures are suitable for arithmetic MPC. In this paper, successive PPs executed by one player without communication and/or face up is counted as one PP since the composition of permutations is also regarded as a permutation and the subsequent private permutation can be executed at once behind the player’s back.
Example: 6-card AND Protocol
In order to clarify the difference between shuffles and PPs, we show two kinds of implementations of 6-card AND protocol, namely, we show the protocol realized by using shuffles (Protocol 1) and PPs (Protocol 2) respectively. Note that, all operations in protocols 1 are executed in public. On the other hand, there are both private and public operations in protocol 2, so that it needs to be clearly distinguished whether the operation is private or public.
We assume that two players, Alice and Bob, hold secret bits \(a \in \{0,1\}\) and \(b \in \{0,1\}\), respectively, and they wish to calculate \(a \wedge b\) without revealing information of their inputs. We introduce the 6-card AND protocol [9] realizing this requirement.
Security Notion
Throughout this paper, we assume that both Alice and Bob are semi-honest players. Following [10], we introduce the security notion (perfect secrecy) of card-based cryptography for the millionaires’ problem.
×
In defining the security of card-based cryptography, view plays a key role. View is roughly defined to be a vector of random variables10 to the data that each player can obtain in the protocol. Specifically, view includes the randomvariables corresponding to the input of the player, the output of the protocol, public information all players can gain, and random values which are used when the player makes a random choice.
For a fixed integer \(m\in {\mathbb {N}}\), let \(a \in [m]\) and \(b \in [m]\) be positive integers representing the wealth of Alice and Bob, respectively, which are the input for protocol. The common output of the millionaires’ problem for Alice and Bob is represented as \(\chi ^{\mathsf {ge}}(a,b)\) where
The information obtained by Alice and Bob in the protocol can be classified into private information denoted by \(r_A\) and \(r_B\), and public information denoted by \(\lambda \). Hence, Alice’s (resp., Bob’s) view can be described as the sequence of random variables corresponding to her (resp., his) input a (resp., b), output of the protocol, private information \(r_A\) (resp., \(r_B\)) and public information \(\lambda \). The private information \(r_A\) (resp., \(r_B\)) is the random number generated by Alice (resp., Bob) for PPs. The public information is the cards that Alice and Bob made public by turning them face up. Note that, in arithmetic MPC, view includes information that each player receives via private channel, but in card-based cryptography, there is no private channel. Only face-up cards can reveal information, and hence, we can define the face-up cards are included in the view as public information. Let \(R_A\), \(R_B\), and \(\varLambda \) be random variables corresponding to the values \(r_A\), \(r_B\), and \(\lambda \), respectively. Then, the views of Alice and Bob are represented as \((A,\chi ^\mathsf{{ge}}(A,B),R_A,\varLambda )\) and \((B,\chi ^\mathsf{{ge}}(A,B),R_B,\varLambda )\), respectively.
Intuitively, if all Alice’s (resp., Bob’s) private and public information can be simulated from Alice’s (resp., Bob’s) input and output, we can say that no information is contained in the private and public information other than Alice’s (resp., Bob’s) input and output. Hence, we can formulate perfect secrecy of card-based cryptography for the millionaires’ problem as follows:
Definition 1
(Perfect secrecy) Consider the millionaires’ problem for Alice and Bob. We say that the card-based cryptography for the millionaires’ problem is perfectly secure if there exist simulators \({\mathsf {S}}_A\) and \({\mathsf {S}}_B\) such that for all possible inputs a and b, it holds that
where \(U\overset{\mathrm{perf}}{\equiv }V\) means that the (joint) probability distributions \(P_U\) and \(P_V\) corresponding to the random variables U and V, respectively, are perfectly the same.
Proposed Protocol I: Card-Based Cryptography for Millionaires’ Problem Based on Yao’s Solution
Our Idea Behind the Proposed Protocol I
We propose a card-based cryptography that resolves the millionaires’ problem by cards based on Yao’s original solution utilizing PPs.11 Before providing our protocol, we explain Yao’s public key based solution [2] as follows:
Yao’s Solution to the Millionaires’ Problem. For a fixed integer \(m\in {\mathbb {N}}\), assume that Alice and Bob have wealth represented by positive integers a and b, respectively, where \(a,b \in [m]\). Let \({\mathcal {X}}:=[2^N-1]\) be a set of N-bit integers where, \(2^{N/2} > 2m\) is necessary to hold \(|z_u - z_v| \ge 2\) in step \(\langle 4 \rangle \) for all distinct \(u,v \in [m]\). \((\mathsf {Enc}_A, {\mathsf {Dec}}_A)\) is a public-key encryption of Alice. That is, \(\mathsf {Enc}_A : {\mathcal {X}} \rightarrow {\mathcal {X}}\) is an encryption under Alice’s public-key, and \({\mathsf {Dec}}_A\) is a decryption under Alice’s private-key.
\(\langle 1 \rangle \)
Bob selects a random N-bit integer \(x\in {\mathcal {X}}\), and computes \(c:=\mathsf {Enc}_A(x)\) privately.
\(\langle 2 \rangle \)
Bob sends the number \(c-b+1\) in the mod \(2^N\) sense to Alice.
\(\langle 3 \rangle \)
For \(i = 1,2,\ldots ,m\), Alice computes privately the values of \(y_i = {\mathsf {Dec}}_A(c-b+i)\); each value \(c-b+i\) is in the mod \(2^N\) sense.
\(\langle 4 \rangle \)
Alice generates a random prime \(p \in [2^{N/2}-1]\), and computes the values \(z_i := y_i\) mod p, for \(i= 1,2,\ldots ,m\). If \(|z_u - z_v| \ge 2\) for all distinct \(u,v \in [m]\), then go to the next step; otherwise generate another random prime p and repeat the process until all \(z_u\) differ by at least 2.
\(\langle 5 \rangle \)
Alice makes \(z'=(z_1, z_2,\dots ,z_a,z_{a+1}+1,z_{a+2}+1,\dots ,z_m+1)\); each value is in the mod p sense.
\(\langle 6 \rangle \)
Alice sends p and the vector \(z'\) to Bob.
\(\langle 7 \rangle \)
Bob looks at the b-th number in \(z'\). If it is equal to x mod p, then \(a \ge b\), otherwise \(a<b\).
\(\langle 8 \rangle \)
Bob sends the result to Alice.
Our Idea Behind Proposed Protocol I. We first point out that the key steps of Yao’s protocol are \(\langle 5 \rangle \)–\(\langle 7 \rangle \), where Alice privately adds 1 to each of \(z_{a+1}, z_{a+2},\dots ,z_m\) in the m-dimensional vector, and sends the vector to Bob. He privately checks the b-th value in the vector, and outputs the result. This private operation can be implemented by PP in card-based cryptography, which corresponds to the step \(\langle 3 \rangle \) in the following proposed protocol I.
Note that, in Yao’s solution, \(\langle 1\rangle \)–\(\langle 4\rangle \) are necessary for realizing the key steps \(\langle 5\rangle \)–\(\langle 7\rangle \) securely, since they prevent the vector \(z'\) in \(\langle 5\rangle \) from leaking Alice’s wealth a to Bob. However, in a card-based cryptography, these steps can be replaced with single step since face down plays the role of encryption. Furthermore, the communication in \(\langle 8\rangle \) can be removed in the card-based protocol since face-up cards on the tabletop can immediately be recognized by both Alice and Bob.
Proposed Protocol I
Based on the ideas discussed in the previous section, we propose a card-based cryptography for the millionaires’ problem based on Yao’s solution (see Protocol 3). We refer to this protocol proposed protocol I. The definitions of a, b and m are the same as the previous section.
Note that steps 1) and 2) in the proposed protocol I correspond to steps \(\langle 1\rangle \)–\(\langle 5\rangle \), and the steps 3) and 4) correspond to steps \(\langle 6\rangle \) and \(\langle 7\rangle \), respectively, which show that the step 2) considerably simplifies Yao’s protocol. We omit the proof of correctness of the proposed protocol since it is almost obvious from Yao’s protocol.
Note that \((\mathsf {Enc}_A, {\mathsf {Dec}}_A)\) in Yao’s millionaires’ protocol must be public-key encryption since a is obtained by Bob in step \(\langle 6\rangle \) if \((\mathsf {Enc}_A, {\mathsf {Dec}}_A)\) is a private key encryption. On the other hand, in the proposed protocol I, such leakage of a to Bob is prevented by requiring that all cards except \(\mathbf{x} _b'\) are completely randomized in public by Alice or Bob at the end of the protocol.
Efficiency of the proposed protocol I In the proposed protocol, 2m cards are used. The number of PPs and communications is constant, i.e., it does not depend on the input length. We use two PPs in steps 2) and 4), and one communication in step 3), and this outperforms the protocol based on logical gates (see Algorithm 1). We note that the steps 4) and 5) are necessary so that Bob turns \(\mathbf{x} _b'\) face up publicly without making b public.12
Theorem 1
The proposed protocol I is perfectly secure; it satisfies (8) and (9) in Definition 1.
Proof
Consider the randomness used by Alice and Bob denoted by \(R_A\) and \(R_B\), respectively. In this protocol, no randomness is used by Alice since she only swaps the cards by using a and m. Hence, it is not necessary for the simulator \(\textsf {S}_A\) to simulate \(R_A\). We also find that Bob does not use his randomness, and \(R_B\) also need not be simulated by \(\textsf {S}_B\).
Regarding the public value \(\varLambda \), observe that it is only the cards \(\mathbf{x} _b'\) revealed in step 5), and the binary value represented by \(\mathbf{x} _b'\) is equal to the truth value of \(a\ge b\). Hence, \(\varLambda \) is uniquely determined from the output, and it can obviously be simulated, which completes the proof. \(\square \)
Remark
Thanks to the special operations of card-based cryptography, e.g., face up, face down, and swap, etc., proposed protocol I is not only a direct transformation of Yao’s protocol, but also is superior to the original one from several aspects. For instance, the proposed protocol I does not use any randomness, whereas randomness is necessary for generating public/private keys in the original solution by Yao. Furthermore, it is worth observing that both Alice and Bob can know the output result simultaneously in the proposed protocol I, whereas Bob is required to announce his result to Alice in Yao’s original protocol (see step \(\langle 8 \rangle \)).
Proposed Protocol II: Card-Based Cryptography for Millionaires’ Problem with Storage
Ideas Behind Proposed Protocol II
In order to reduce the number of cards to below 2m, it is natural to represent the wealth of Alice and Bob as binary number with \(\lceil \log m \rceil \) bits (i.e., \(2\lceil \log m \rceil \) cards). This approach enables us to consider the strategy by comparing the Alice’s and Bob’s wealth bit-by-bit starting from their least significant bits.
Let \((a_n, \dots ,a_1)\) and \((b_n ,\dots , b_1)\) be the binary representation of the positive integers a and b, respectively, where \(n:=\lceil \log m \rceil \) and \(a_i,b_i\in \{0,1\}\), \(i= 1,2,\ldots ,n\). For each \(i\in [n]\), assume that \(a_i\) and \(b_i\) are represented by pairs of cards \(\alpha _{i,l} \alpha _{i,r}\) and \(\beta _{i,l}\beta _{i,r}\), respectively, where \(\alpha _{i,l} \alpha _{i,r},\beta _{i,l}\beta _{i,r}\in \{\clubsuit \heartsuit ,\heartsuit \clubsuit \}\). For instance, \(a_i=1\) is represented by cards as \(\alpha _{i,l} \alpha _{i,r}=\heartsuit \clubsuit \).
Note that, however, such a two-card representation of binary number is redundant in a bit-by-bit comparison since we can represent 0 and 1 by \(\clubsuit \) and \(\heartsuit \), respectively.13 In this one-card representation, \(\alpha _{i,l}\) and \(\beta _{i,l}\) suffice to represent \(a_i\) and \(b_i\), respectively. Further, their negations, \(\lnot a_i\) and \(\lnot b_i\), are also represented by \(\alpha _{i,r}\) and \(\beta _{i,r}\), respectively. In the following, we consider a scenario in which Alice prepares \((a_n,\ldots ,a_1)\) by using a two-card representation, but here, Alice and Bob use a one-card representation for comparison.
We compare the bits of Alice and Bob by preparing a device (equipped by a card as well) called comparison storage, denoted by \(\textit{cs} \in \{\clubsuit ,\heartsuit \}\), that records the bit-by-bit comparison results. Our idea is roughly described as follows: We assume that Bob compares \(\beta _{i,l}\) (i.e., \(b_i\)) with Alice’s card \(\alpha _{i,l}\) (i.e., \(a_i\)) from \(i=1\) to n, and he overwrites cs with \(\beta _{i,l}\) (i.e., \(b_i\)) if \(\beta _{i,l} \ne \alpha _{i,l}\) (i.e., \(b_i \ne a_i\)) while cs remains untouched if this is not the case (i.e., \(b_i = a_i\)). Recalling that Bob overwrites the comparison storage with his bit, Bob is shown to be richer if the comparison storage is \(\heartsuit \) (i.e., 1) at the end of the protocol. Similarly, Alice is shown to be richer if the comparison storage is \(\clubsuit \) (i.e., 0) at the end of the protocol. As is easily understood, however, this rough idea has the following a problem:
P1)
If Bob were to directly compare his bits with those of Alice, such a comparison strategy would easily leaks Alice’s bits to Bob.
This problem can be avoided by considering the following modified randomized strategy: Since Alice prepares \((a_n,\ldots ,a_1)\) by two-card representations, she sends Bob \(\alpha _{i,l}\) (i.e., \(a_i\)) or \(\alpha _{i,r}\) (i.e., \(\lnot a_i\)) with probability 1/2. Such a randomization is effective for concealing the value of Alice’s bit from Bob, but we encounter another problem:
P2)
Since Alice sends \(\alpha _{i,w}\) to Bob \(w\in \{l,r\}\) with a probability of 1/2, he cannot tell from \(\alpha _{i,w}\) whether \(a_i \ne b_i\) or not.
Problem P2) is resolved by introducing another storage called dummy storage, denoted by \(\textit{ds} \in \{\clubsuit ,\heartsuit \}\), and communicating the pair of cs and ds between Alice and Bob.
Hereafter, we refer to the pair consisting of \(\textit{cs}\) and \(\textit{ds}\) as storage. Bob overwrites cs and ds corresponding to the result of \(a_i \ne b_i\) and \(a_i = b_i\). However, just adding a new storage is insufficient to resolve the problem that Bob cannot determine whether \(a_i \ne b_i\) or \(a_i = b_i\), i.e., he cannot determine which one of cs and ds should be overwritten.
Problem P2) can be rephrased using binary numbers as follows: Let \(a'_i \in \{0,1\}\) be a binary number that Bob receives, but he does not know whether \(a_i' = a_i\) (in the case of \(w=l\)) or \(a_i' = \lnot a_i\) (in the case of \(w=r\)). Our main object is to find \(a_i \ne b_i\) or \(a_i = b_i\) even if either one of \(a'_i=a_i\) or \(a'_i=\lnot a_i\) is sent.14
Basic idea for resolving P2) is that Bob uses the fact that what he knows is either \(\alpha _{i,w} \ne \beta _{i,l}\) (i.e., \(a_i' \ne b_i\)) or \(\alpha _{i,w} = \beta _{i,l}\) (i.e., \(a_i' = b_i\)). Making use of this fact, Alice and Bob treat cs and ds as an ordered pair of face-down cards, and assume that either \((\textit{cs},\textit{ds})\) or \((\textit{ds},\textit{cs})\) is determined by Alice’s private random choice \(w\in \{l,r\}\) as follows:
If Alice selects \(w=l\) and sends Bob \(\alpha _{i,l}\in \{\clubsuit ,\heartsuit \}\) (i.e., \(a_i\)), then she sends him \((\textit{cs},\textit{ds})\) with \(\alpha _{i,l}\).
If Alice selects \(w=r\) and sends Bob \(\alpha _{i,r}\in \{\clubsuit ,\heartsuit \}\) (i.e., \(\lnot a_i\)), then she sends him \((\textit{ds},\textit{cs})\) with \(\alpha _{i,r}\).
Note that \(\alpha _{i,w}\) is not necessary to be face-down when she sends it since no information on a leaks to Bob from \(\alpha _{i,w}\). We can see that the order of cs and ds is synchronized with \(w\in \{l,r\}\) (i.e., \(a_i\) and \(\lnot a_i\)) in Alice. Owing to this synchronization, Bob can correctly overwrite cs only when \(a_i \ne b_i\) by implementing the following strategy, even if he does not know which one of cs and ds should be overwritten. Let \((\sigma _l,\sigma _r)\) be the storage Bob receives from Alice. Then Bob’s behavior after receiving \(\alpha _{i,w}\) from Alice is shown below.
If \(\alpha _{i,w} \ne \beta _{i,l}\) (i.e., \(a'_i \ne b_i\)) holds, Bob overwrites the left element \(\sigma _l\) of the storage \((\sigma _l,\sigma _r)\) with \(\beta _{i,l}\) (i.e., \(b_i\)).
If \(\alpha _{i,w} = \beta _{i,l}\) (i.e., \(a'_i = b_i\)) holds, Bob overwrites the right element \(\sigma _r\) of the storage \((\sigma _l,\sigma _r)\) with \(\beta _{i,l}\) (i.e., \(b_i\)).
Let \((\sigma _l',\sigma _r')\) be the storage overwritten by Bob, and he returns \((\sigma _l',\sigma _r')\) to Alice. Then, by using \(w \in \{l,r\}\) that Alice generated, she privately rearranges \((\sigma _l',\sigma _r')\) so as to place cs and ds on the left and the right, respectively. After repeating these procedures from \(i=1\) to n, Bob is shown to be richer if \({cs}=\heartsuit \) (i.e., 1) whereas the contrary is true if \({cs}=\clubsuit \) (i.e., 0).
Table 2
Synchronization mechanism in the proposed protocol with storage
(cs, ds), \(w=l\)
(ds, cs), \(w=r\)
\(a_i\)\((\alpha _{i,l})\)
\(b_i\)\((\beta _{i,l})\)
\(a_i'\) (\(\alpha _{i,l}\))
\(a_i' \ne b_i\)
Overwrite
\(a_i'\) (\(\alpha _{i,r}\))
\(a_i' \ne b_i\)
Overwrite
0 (\(\clubsuit \))
1 (\(\heartsuit \))
0 (\(\clubsuit \))
True
\(\text {left} =\textit{cs}\)
1 (\(\heartsuit \))
False
\(\text {right} =\textit{cs}\)
1 (\(\heartsuit \))
0 (\(\clubsuit \))
1 (\(\heartsuit \))
True
\(\text {left} =\textit{cs}\)
0 (\(\clubsuit \))
False
\(\text {right} =\textit{cs}\)
0 (\(\clubsuit \))
0 (\(\clubsuit \))
0 (\(\clubsuit \))
False
\(\text {right} =\textit{ds}\)
1 (\(\heartsuit \))
True
\(\text {left} =\textit{ds}\)
1 (\(\heartsuit \))
1 (\(\heartsuit \))
1 (\(\heartsuit \))
False
\(\text {right} =\textit{ds}\)
0 (\(\clubsuit \))
True
\(\text {left} =\textit{ds}\)
It is easy to see from Table 2 that our synchronization strategy for storage works well. This is best clarified by discussing the proposed protocol by using binary numbers rather than cards. For instance, consider the case where Alice compares her bit \(a_i=1\) with Bob’s bit \(b_i=0\) (the second line in Table 2). If Alice selects \(w=l\), Bob receives a bit \(a'_i=a_i=1\) and compares it with Bob’s bit \(b_i=0\). Since \(a'_i \ne b_i\), the left-hand side element of the storage, i.e., cs, is overwritten by \(b_i =0\). On the other hand, if Alice selects \(w=r\), Bob receives a bit \(a'_i=\lnot a_i=0\) and compares it with his bit \(b_i=0\). Since \(a'_i = b_i=0\), the right-hand side element of the storage, i.e., cs, is overwritten by \(b_i =0\). Anyway, cs is correctly overwritten by \(b_i=0\)\((< a_i =1)\) as expected.
Remark
It is interesting to note that the logic of the above synchronization strategy is the same as that of the well-known logical puzzle “The fork in the road,” [1, p.25] (see footnote \(^{*}8\)). Note that the point of the “The fork in the road” is that we need to obtain the correct answer (correct branch) from “yes-no-questions,” regardless of whether the native bystander tells the truth. The one of the well-known answers to this puzzle is that the logician should ask “if I ask the right way goes to the village, then do you answer YES?.” This question consists of two propositions as follows:
Q1)
The right way goes to the village.
Q2)
The bystander answers YES.
Suppose that the right way goes to the village. If the native bystander is a truth-teller, then obviously the logician receives YES. On the other hand, the logician have the same answer (YES) even if the bystander is a liar because of the following double negation:
L1)
The liar wants to say NO to Q1) because Q1) is true.
L2)
The liar has to say YES because Q2) is false (due to L1)).
Namely, telling lies twice for Q1) and Q2), the liar says YES if the right way goes to the village; NO otherwise. Our synchronization strategy has the same structure with this puzzle. In proposed protocol II, Alice chooses whether she sends \(a_i\) (i.e., truth) or \(\lnot a_i\) (i.e., lie), which corresponds to L1). If she chooses the lie, then she reverses the order of storage cards cd and ds, which has the same effect with L2). Due to this structure of double negation, Bob can correctly record the comparison result regardless of Alice’s choice. Therefore, we can verify the correctness of proposed protocol II.
Proposed Protocol II
Based on the discussion in the previous section, we propose the card-based cryptography which uses storage and synchronization between the random selection \(w\in \{l,r\}\) and the order of cs and ds, for the Millionaires’ problem (see Protocol 4). For the upper bound \(m\in {\mathbb {N}}\) of the wealth of Alice and Bob, let \(n:=\lceil \log m\rceil \).15
Example of proposed protocol II. We show a simple example for understanding how the proposed protocol II works correctly. Consider the case where we compare \(a=0\) of Alice and \(b=2\) of Bob, which are represented by \((\alpha _{2,l}\alpha _{2,r}, \alpha _{1,l}\alpha _{1,r}):=(\clubsuit \heartsuit ,\clubsuit \heartsuit )\) and \((\beta _{2,l}\beta _{2,r}, \beta _{1,l}\beta _{1,r}):=(\heartsuit \clubsuit ,\clubsuit \heartsuit )\), respectively, since \((a_2,a_1)=(0,0)\) and \((b_2,b_1)=(1,0)\). We also set \((\textit{cs},\textit{ds})=(\clubsuit ,\heartsuit )\).
We first consider the case of \(i=1\). If Alice chooses \(w=l\) in step (2-i), (12) becomes \((\sigma _l,\sigma _r)=(\textit{cs},\textit{ds})=(\clubsuit ,\heartsuit )\) since \(\chi ^{\textsf {eq}}(w,r)=\chi ^{\textsf {eq}}(l,r)=0\). Then, she sends Bob \((\sigma _l,\sigma _r)=(\clubsuit ,\heartsuit )\) and \(\alpha _{1,l}=\clubsuit \) in step (2-ii). In step (2-iii), Bob compares \(\beta _{1,l}=\clubsuit \) with \(\alpha _{1,l}=\clubsuit \), which results in \(\overline{\chi ^{\mathsf {eq}}}(\beta _{1,l},\alpha _{1,l})=0\). Then, he outputs \((\sigma '_l, \sigma '_r)=(\sigma _l, \beta _{1,l})=(\clubsuit ,\clubsuit )\) by overwriting the right element of \((\sigma _l,\sigma _r)=(\clubsuit ,\heartsuit )\) with \(\beta _{1,l}=\clubsuit \)privately, since (13) becomes \((\sigma '_l, \sigma '_r, \eta )=(\sigma _l, \beta _{1,l},\sigma _r)\) due to \(\overline{\chi ^{\mathsf {eq}}}(\beta _{1,l},\alpha _{1,l})=0\). Bob discards \(\sigma _r\) without face up \(\sigma _r=\heartsuit \).
On the other hand, consider the case where Alice chooses \(w=r\) in step (2-i); Then, (12) in step (2-i) becomes \((\sigma _l,\sigma _r)=(ds,cs)=(\heartsuit ,\clubsuit )\) since \(\chi ^{\textsf {eq}}(w,r)=\chi ^{\textsf {eq}}(r,r)=1\). She sends Bob \((\sigma _l,\sigma _r)=(\heartsuit ,\clubsuit )\) and \(\alpha _{1,r}=\heartsuit \) in step (2-ii). Bob compares \(\beta _{1,l}=\clubsuit \) with \(\alpha _{1,r}=\heartsuit \), and outputs \((\sigma '_l, \sigma '_r)=(\clubsuit ,\clubsuit )\) by overwriting the left element of \((\sigma _l,\sigma _r)=(\heartsuit ,\clubsuit )\) with \(\beta _{1,l}=\clubsuit \) privately as a result of (13).
Summarizing the case of \(i=1\), regardless of the selection of \(w \in \{l,r\}\), storage becomes \((cs,ds)=(\clubsuit ,\clubsuit )\), which means that the dummy storage is overwritten by the Bob’s bit since \(a_1=b_1\). Then, Bob sends it to Alice in step (2-iv). In step (2-v), Alice sets \((\textit{cs},\textit{ds}):=(\clubsuit ,\clubsuit )\) due to (14) for the storage sent from Bob.
Next, consider the case of \(i=2\): If Alice selects \(w=l\) in step (2-i), she generates \((\sigma _l,\sigma _r)=(\textit{cs},\textit{ds})=(\clubsuit ,\clubsuit )\) from (12), and sends it with \(\alpha _{2,l}=\clubsuit \) to Bob in step (2-ii). Then, Bob compares \(\beta _{2,l}=\heartsuit \) with \(\alpha _{2,l}=\clubsuit \) in step (2-iii). Since \(\beta _{2,l}\ne \alpha _{2,l}\), he generates \((\sigma '_l, \sigma '_r)=(\beta _{2,l},\sigma _r)=(\heartsuit ,\clubsuit )\) by overwriting the left element of \((\sigma _l,\sigma _r)=(\clubsuit ,\clubsuit )\) with \(\beta _{2,l}=\heartsuit \) privately according to (13). Bob sends \((\sigma '_l, \sigma '_r)=(\heartsuit ,\clubsuit )\) to Alice, and she obtains \((\textit{cs},\textit{ds}):=(\heartsuit ,\clubsuit )\) due to (14).
On the other hand, consider the case where Alice chooses \(w=r\) in step (2-i); Then, she generates \((\sigma _l,\sigma _r)=(ds,cs)=(\clubsuit ,\clubsuit )\) from (12), and sends it with \(\alpha _{2,r}=\heartsuit \) in step (2-iii). Since \(\beta _{2,l} = \alpha _{2,r}\), he generates \((\sigma '_l, \sigma '_r)=(\sigma _l, \beta _{2,l})=(\clubsuit ,\heartsuit )\) by overwriting the right element of \((\sigma _l,\sigma _r)=(\clubsuit ,\clubsuit )\) with \(\beta _{2,l}=\heartsuit \) privately according to (13). Bob sends \((\sigma '_l, \sigma '_r)=(\clubsuit ,\heartsuit )\) to Alice, and she obtains \((\textit{cs},\textit{ds}):=(\heartsuit ,\clubsuit )\) due to (14).
Finally, the output value correctly becomes \(cs=\heartsuit \) as \(a<b\) regardless of random choices of Alice.
Efficiency of the proposed protocol II. This protocol requires two communications for every bit therefore it requires \(2 \lceil \log m \rceil \) communications. We note that steps (2-v) and (2-i), when i is incremented, can also be regarded as one PP. Hence, this protocol requires \(2 \lceil \log m \rceil +1\) PPs. The number of cards is \(4\lceil \log m \rceil +2\).
Theorem 2
The proposed protocol II is perfectly secure; it satisfies (8) and (9) in Definition 1.
Proof
Consider the randomness used by Alice and Bob denoted by \(R_A\) and \(R_B\), respectively. From step (2-i), the value of \(R_A=(W_1,W_2,\ldots ,W_n)\) where \(W_i\) is the random variable corresponding to w in the i-th loop in step 2). Each random variable \(W_i\), \(i=1,2,\ldots ,n\) takes the value in \(\{l,r\}\) with probability 1/2, and it is independent from the other random variables. Hence, \(R_A\) can obviously be simulated by \({\mathsf {S}}_A\) by using n independent uniform binary numbers. Similarly to the proposed protocol I, Bob does not use any randomness, and hence, \({\mathsf {S}}_B\) does not have to simulate \(R_B\).
Regarding the simulation of public information \(\varLambda \), observe that \(\varLambda \) is the n values represented by the face-up cards in step (2-iii), i.e., \( \varLambda = (\alpha _{1,{W_1}},\alpha _{2,{W_2}},\ldots ,\alpha _{n,{W_n}})\). Hence, \(\varLambda \) is easily simulated by \({\mathsf {S}}_A\) by a which is represented by her 2n cards, and the random variable \(R_A=(W_1,W_2,\ldots ,W_n)\). On the other hand, for Bob, \(\varLambda =(\alpha _{1,{W_1}},\alpha _{2,{W_2}},\ldots ,\alpha _{n,{W_n}})\) seems to be uniformly distributed over \(\{\heartsuit , \clubsuit \}^n\) since he does not know the value of \(W_i=w_i\), which is selected randomly by Alice. Hence, \(\varLambda \) is easily simulated by \(S_B\).
Since the simulators \({\mathsf {S}}_A\) and \({\mathsf {S}}_B\) can be explicitly constructed as above, we complete the proof of the theorem. \(\square \)
Millionaires’ Problem Can Be Solved with Only Six Cards
Although the proposed protocol II was improved in terms of the numbers of PPs and communications, as is shown in Table 1, it still requires the same number of cards with the previous work based on logical gates. However, we show that the proposed protocol II can be realized with only six cards in this section.
Our main idea is to reuse the card \(\eta \) discarded by Bob in step (2-iii) of Protocol 4.16 We note that, however, \(\eta \) cannot be simply reused. If \(\eta \) is reused simply and accessed by Alice and/or Bob, they can obtain information about \(\eta \) which holds information on their inputs. For instance, in Protocol 4, suppose that Bob could look at the front of \(\eta \) in step (2-iii) for \(i=1\). Noticing that \((cs,ds)=(\clubsuit ,\heartsuit )\) is public information when \(i=1\), \(a_1\) completely leaks to Bob since he can tell whether \(w=l\) or not. Inductively, \(\eta \) should not be simply reused when \(i \ge 1\) because \(\eta \) also holds information about Alice’s choice of w.
Therefore, we need to erase information about \(\eta \) for reusing it. However, it is impossible to erase the information about \(\eta \) as long as we adopt the one-card representation since a single card cannot be randomized as opposed to the case of two-card representation. Hence, we should employ two-card representation for the storage (and the input) in Protocol 4. Concretely, if \(\eta \) is in two-card representation, Bob returns randomized \(\eta \) to Alice instead of discarding it by Bob in Protocol 4. Then, she can reuse \(\eta \).
One may think that this modification makes the protocol inefficient since the number of storage cards increases. However, surprisingly, this modification allows Alice and Bob to use \(\eta \) as his/her inputs if they hold inputs in their mind! Namely, at the cost of using six cards for (cs, ds) and \(\eta \), Alice and Bob do not necessary to have their cards to represent their inputs (if they can remember the inputs). Therefore, six cards are sufficient to realize a card-based protocol for millionaires’ problem with efficient memory and communication cost. The improved protocol shown in Protocol 5. As shown in the step 1), the storage cards are represented by two-card representation. The steps (2-v) and (2-viii) are executed for erasing information of \(\eta \) by Bob and Alice.
Efficiency of the improvement of proposed protocol II. This protocol requires two communications for every bit therefore it requires \(2 \lceil \log m \rceil \) communications. We note that the sequence of PPs executed in steps (2-iv) and (2-v) can be regarded as one PP. Similarly, steps (2-vii) to (2-i), when i is incremented, can also be regarded as one PP. Hence, this protocol requires \(2 \lceil \log m \rceil + 1\) PPs.
Concluding Remarks
In this paper, we proposed two efficient card-based cryptography (called proposed protocols I and II) for the millionaires’ problem by introducing a new operation called private permutation (PP). Proposed protocol I is constructed based on Yao’s solution. This solution was realized by using public key encryption instead of logical gates, and hence, it could not be straightforwardly implemented to card-based cryptography based on logical gates. However, we show that Yao’s solution can be easily implemented by using cards if we do not restrict ourselves by logical gates and use PPs instead. This protocol could be realized with one communication and two PPs, and is therefore much more effective than the existing protocol (see Table 1). However, the number of cards increases. It is worth mentioning that proposed protocol I is not only a direct transformation of Yao’s protocol, but is also superior to the original protocol in the sense that randomness and the announcement of the result are not required as opposed to Yao’s original protocol.
Proposed protocol II is entirely novel. It consists of the communication of two types of storage for recording the compared result between two players. This proposed protocol is superior to the existing protocol based on logical gates with respect to the number of communications and PPs, whereas the number of cards is the same as the existing protocol. Furthermore, it is interesting to remark that proposed protocol II and the well-known logical puzzle known as “The fork in the road,” are deeply related. But this protocol is not made efficient from the view point of the number of cards (see Table 1). Hence we proposed a method to reduce the number of cards. The improved protocol works only six cards by memorizing the inputs in player’s mind without representing them using cards.
×
×
×
Acknowledgements
We are grateful to Prof. Takaaki Mizuki and Dr. Kazumasa Shinagawa for their valuable comments and discussion. We thank the anonymous reviewers, whose comments have helped us to improve the presentation of this paper. This work was supported by JSPS KAKENHI Grant numbers JP26420345, JP17H01752, JP18H05289, JP18K19780, JP18K11293, JP18H03238 and JP20J21248.
Open AccessThis 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.
We focus only on protocols for logical gates which can be used in combination with other protocols. Without considering the possibility of combination, it is shown in [11] that four cards are sufficient in AND.
Although this fact is mentioned in [11], the efficiency of the protocol based on this fact is not discussed by these authors, and hence, they use shuffles as building blocks.
After the earlier version of this paper [15] being published, a method was proposed to realize card-based cryptography for computing circuits with one shuffle [17]. Since this protocol utilized the techniques of garbled circuit [3], it requires distinct twenty four cards for each gate. Hence, instead of achieving the minimum number of shuffles, this protocol requires much more number of cards compared to the protocols obtained by simply combining the card-based protocols for logical gates.
This problem is summarized as follows: An logician finds himself on an island inhabited by two tribes: liars and truth-tellers. Members of the one tribe always tell the truth, whereas members of the other tribe always tell lies. The logician reaches a fork in a road and has to ask a native bystander which branch he should take to reach the village. He has no way of telling whether the native is a truth-teller or a liar. The logician only asks one question. From the reply he knows which road to take. What question does he ask? [1, p.25]
Throughout the paper, random variables are represented by capital letters. The probability that a random variable X takes a value x is represented by \(\mathsf {Pr}\{X=x\}\) which is also written as \(P_X(x)\) for short. Mathematically, a random variable is defined to be a map from probability space to the set of real numbers. However, for simplicity, we allow the cards \(\clubsuit , \heartsuit \) to be treated as the values of random variables.
However, we note that a one-card representation cannot express arbitrary binary numbers. Hence, \(4\lceil \log m \rceil \) (i.e., \(2\lceil \log m \rceil \) cards for Alice and Bob) cards are at least necessary when comparing arbitrary two binary numbers less than m.
In our setting, the randomization for reusing \(\eta \) is executed by participants, Alice and Bob. If we are allowed to outsource this randomization to a trusted third party, the number of cards can further reduced, which was pointed out in [16].
and
. We assume that two cards with the same mark are indistinguishable. We also assume that all cards have the same design on their reverse sides, and that they are indistinguishable and represented as
. The Boolean values 0 and 1 are encoded as
and
, respectively. Note that we regard the sequence of cards as a vector. In this paper, we use the following fundamental card operations [12]. Note that these operations are executed publicly.A pair of face-down cards for the Boolean value \(x \in \{0,1\}\), is called commitment. In particular, the permutation for a commitment is referred to as swap.
and
are represented as \(\clubsuit \) and \(\heartsuit \), respectively.
Then, \(\mathbf{u} _1\) and \(\mathbf{u} _2\) are interchanged or left unchanged with probability 1/2. Depicting this by using figures, one of either
is selected with a probability 1/2. This operation, called random bisection cut, is executed in public but it is assumed that no player knows whether one of the above is selected.