Minimum Round Card-Based Cryptographic Protocols Using Private Operations ^†

Abstract

This paper shows new card-based cryptographic protocols with the minimum number of rounds, using private operations under the semi-honest model. Physical cards are used in card-based cryptographic protocols instead of computers to achieve secure multiparty computation. Operations that a player executes in a place where the other players cannot see are called private operations. Using three private operations—private random bisection cuts, private reverse cuts, and private reveals—the calculations of two variable Boolean functions and copy operations were realized with the minimum number of cards. Though the number of cards has been discussed, the efficiency of these protocols has not been discussed. This paper defines the number of rounds to evaluate the efficiency of the protocols, using private operations. Most of the meaningful calculations using private operations need at least two rounds. This paper presents a new two-round committed-input, committed-output logical XOR protocol, using four cards. Then, we show new two-round committed-input, committed-output logical AND and copy protocols, using six cards. Even if private reveal operations are not used, logical XOR, logical AND, and copy operations can be executed with the minimum number of rounds. Protocols for general n-variable Boolean functions and protocols that preserve an input are also shown. Lastly, protocols with asymmetric cards are shown.

1. Introduction

1.1. Motivation

Card-based cryptographic protocols [1,2,3] have been proposed in which physical cards are used instead of computers to securely calculate values. They can be used when computers cannot be used or when users cannot trust cryptograhic software in the computers. The protocols can be used to teach the basics of cryptography [4,5]. den Boer [6] first showed a five-card protocol to securely calculate the logical AND of two inputs. Since then, many protocols have been proposed to calculate Boolean functions [7,8,9] and specific computations, such as the millionaires’ problem [10,11,12], realizing Turing machines [13,14], voting [15,16,17,18], random permutation [19,20,21,22], grouping [23], ranking [24], lottery [25], proof of knowledge of a puzzle solution [26,27,28,29,30,31,32,33,34], and so on. This paper considers calculations of Boolean functions and the copy operation under the semi-honest model.

There are several types of protocols with regard to the inputs and outputs of the computations. The first type is committed inputs [7], where the inputs are given as committed values. The players do not know the input values. The other type is non-committed inputs [35,36], where players give their private inputs to the protocol, using private input operations. The private input operations were also used in the millionaires’ problem [11]. Protocols with committed inputs are desirable since they can be used for non-committed inputs: each player can give their private input value as a committed value.

Some protocols output their computation results as committed values [7]. The result is unknown to the players unless the players open the output cards. The other type of protocols [6,37] output the result as a non-committed value, that is, the final result is obtained only by opening cards. Protocols with committed outputs are desirable since the committed output result can be used as an input to another computation. If further calculations are unnecessary, the players just open the committed outputs and obtain the result. Thus, this paper discusses protocols with committed inputs and committed outputs.

An example of a calculation with committed inputs is a matching service between men and women. The matching service provider does not allow direct communication between the clients until the matching is over. A client, Anne, receives information about a candidate, Bruce, from her agent, Alice. Anne sends the reply of acceptance/rejection to Alice, but Anne does not want the matching service provider agents to know the reply. Bruce also receives information about Anne from his agent Bob. Bruce sends his reply of acceptance/rejection to Bob, but Bruce does not want the matching service provider agents to know the reply. Alice and Bob must calculate whether the matching is successful or not without knowing the inputs. In this case, a calculation with committed inputs is necessary. To prevent malicious activities by the players, Anne observes all the actions executed by Alice. Bruce observes all the actions executed by Bob. If a player executes some action that is not allowed, the observing person can point out the misbehavior. Thus, Alice and Bob become semi-honest players. Note that Anne (Bruce) cannot observe Bob’s (Alice’s) actions. If a person observes both players’ actions, the person can know a secret value.

Operations that a player executes in a place where the other players cannot see are called private operations. These operations are considered to be executed under the table or in the back so that the operations cannot be seen by the other players. Private operations are shown to be the most powerful primitives in card-based cryptographic protocols. They were first introduced to solve the millionaires’ problem [10]. Using private operations, committed-input and committed-output logical AND, logical XOR, and copy protocols can be achieved with the minimum number of cards [9]. Thus, this paper considers protocols using private operations.

The number of cards is the space complexity of the card-based protocols. Thus, the time complexity must also be evaluated. Some studies have been done for protocols that do not use private operations [38]. As for the protocols using private operations, the number of rounds, defined in Section 2, is the most appropriate criterion to evaluate the time complexity. Roughly speaking, the number of rounds counts the number of sending cards between players. Since each private operation is relatively simple, sending cards between players and setting up so that the cards are not seen by the other players is the dominating time to execute private operations. Thus, this paper discusses the number of rounds of card-based protocols, using private operations.

This paper shows logical XOR, logical AND, and copy protocols with the minimum number of rounds. The summary of results are shown in

Table 1. Comparison of XOR protocols, using private operations.

Article	# of Rounds	# of Cards	Preserving an Input	Private Reveal
[9]	3	4	No	Use
[9]	3	4	Yes	Use
[7]	2	4	No	Does not use
Protocol 2	2	4	No	Use
Protocol 6	2	4	No	Does not use
Protocol 12	3	4	Yes	Use
Protocol 13	3	4	Yes	Does not use

,

Table 2. Comparison of AND protocols, using private operations.

Article	# of Rounds	# of Cards	Preserving an Input	Private Reveal
[9]	3	4	No	Use
[9]	3	6	Yes	Use
[9]	5	4	Yes	Use
[7]	2	6	No	Does not use
[39]	3	6	Yes	Does not use
Protocol 3	2	6	No	Use
Protocol 7	3	4	No	Does not use
Protocol 8	2	6	No	Does not use
Protocol 14	3	6	Yes	Use
Protocol 15	3	6	Yes	Does not use
Protocol 16	5	4	Yes	Does not use

and

Table 3. Comparison of copy protocols ($m=2$), using private operations.

Article	# of Rounds	# of Cards	Private Reveal
[9]	3	4	Use
[7]	2	6	Does not use
Protocol 4	2	6	Use
Protocol 9	3	4	Does not use
Protocol 10	2	6	Does not use

. Note that the protocols in [7] need one shuffle by each player; thus, the actual execution time is larger than that in this paper, though the number of rounds is the same.

This paper then shows variations of the protocols that do not use private reveals. Since a private reveal obtains private values, mistakes of private reveals are fatal for security. Thus, it would be better if every reveal operation is publicly executed and verified by multiple players. Thus, we consider protocols that do not use private reveal operations. We show that we can obtain protocols without increasing the number of rounds or cards, even if we cannot use private reveals.

Next, we show protocols that preserve an input. In usual logical AND protocols, the input bits are lost. If one of the inputs is not lost, the input bit can be used for further computations [39]. This paper shows the number of rounds of protocols that preserve an input. Lastly, this paper shows that the protocols can be executed using asymmetric cards.

In Section 2, basic notations, the private operations introduced in [9], and the definition of the rounds are shown. Section 3 shows two-round XOR, AND, and copy protocols. Section 4 shows the protocols that do not use private reveals. Section 5 shows protocols that preserve an input. Section 6 shows parallel execution of the protocols. Section 7 shows protocols with asymmetric cards. Section 8 concludes the paper.

1.2. Related Works

Many studies have been done for calculating Boolean functions without private operations; den Boer [6] first showed a five-card protocol to securely calculate logical AND of two inputs. Since then, several protocols to calculate logical AND of two committed inputs have been shown [40,41,42], but they use more than six cards. Mizuki et al. [7] showed a logical AND protocol that uses six cards. It was proved that it is impossible to calculate logical AND with less than six cards when we use closed and uniform shuffles [43]. When it is allowed to use a special kind of shuffle that is not closed or uniform, the minimum number of cards of logical AND protocols is decreased to five [8,44,45]. In addition, when Las Vegas protocols are allowed, logical AND protocols with five or four cards were shown [2,37,46].

For making copies of an input bit, Mizuki et al. showed a protocol with six cards [7]. A five-card protocol was shown that uses non-uniform shuffles [47].

Mizuki et al. [7] showed a logical XOR protocol that uses four cards, which is the minimum. An XOR protocol that uses random cuts was shown [48].

Several other protocols, such as computations of many inputs [49,50,51,52,53], computing any Boolean functions [13,14,39,54], and two-bit output functions [55], were shown. Protocols using other types of cards were also shown [56,57,58,59,60,61,62,63].

2. Preliminaries

2.1. Basic Notations

This section gives the notations and basic definitions of card-based protocols. Most of this paper is based on a standard two-color card model.

In the two-color card model, there are two kinds of marks: and . Cards of the same marks cannot be distinguished. In addition, the back of both types of cards is . It is impossible to determine the mark in the back of a given card of .

One bit data are represented by two cards as follows: = 0 and = 1.

One pair of cards that represents one bit $x\in \{0,1\}$, whose face is down, is called a commitment of x, and denoted as $commit\left(x\right)$. It is written as follows: Note that when these two cards are swapped, $commit\left(\overline{x}\right)$ can be obtained. Thus, logical negation can be calculated without private operations.

A set of cards placed in a row is called a sequence of cards. A sequence of cards S whose length is n is denoted as $S=s_1,s_2,\dots ,s_n$, where $s_i$ is the i-th card of the sequence. A sequence whose length is even is called an even sequence. $S_1\left|\right|S_2$ is a concatenation of sequence $S_1$ and $S_2$.

All protocols are executed by multiple players. Throughout this paper, all players are semi-honest, that is, they obey the rule of the protocols but try to obtain information x of $commit\left(x\right)$. There is no collusion among players executing one protocol together. No player wants any other player to obtain information on committed values. Since the private operations are executed in a place where the other players cannot see, malicious actions might be easily executed, hence the semi-honest model might not be inappropriate in some cases. To consider malicious actions, two techniques are considered. The first technique executes more than two players [9]. For example, three players—Alice, Bob, and Carol—execute one protocol together. Alice watches Bob’s private operations, Bob watches Carol’s private operations, and Carol watches Alice’s private operations. If a player executes a malicious action, it is detected by the corresponding watching player. The method can be easily introduced to the protocols shown in this paper.

The second technique uses envelopes as an additional tool [64]. The technique is used when the number of players is two. The cards are put into envelopes and sealed in a public place. When the seals are illegally opened during a private operation, they can be detected by the other player. Using the envelopes, all malicious private actions during AND, XOR, and copy protocols are detected or automatically corrected [64]. The technique can also be applied to this paper’s protocols. Thus, this paper assumes the semi-honest model to show the fundamental protocols.

In Section 7, protocols with asymmetric cards are written. When we use cards whose face is not symmetric, such as and , but the back is symmetric, one-bit data can be represented by one card as = 0 and = 1. Protocols with this type of card are first considered in [56] and then several protocols are shown in [9,36,60]. This paper shows minimum round protocols using private operations.

2.2. Private Operations

We show three private operations introduced in [9] for the two-color model: private random bisection cuts, private reverse cuts, and private reveals.

Primitive 1.

(Private random bisection cut)

A private random bisection cut is the following operation on an even sequence $S_0=s_1,s_2,\dots ,$$s_{2m}$. A player selects a random bit $b\in \{0,1\}$ and outputs the following:

$$S_1=\left\{\begin{array}{cc}{S}_0\hfill & \mathrm{if}b=0\hfill \\ s_{m+1},s_{m+2},\dots ,s_{2m},s_1,s_2,\dots ,s_m\hfill & \mathrm{if}b=1\hfill \end{array}\right.$$

The player executes this operation in a place where the other players cannot see. The player must not disclose the bit b.

Note that if the private random cut is executed when $m=1$ and $S_0=commit\left(x\right)$, given $S_0=$ the player’s output $S_1=$ , which is or .

Primitive 2.

(Private reverse cut, private reverse selection)

A private reverse cut is the following operation on an even sequence $S_2=s_1,s_2,\dots ,s_{2m}$ and a bit $b\in \{0,1\}$. A player outputs the following:

$$S_3=\left\{\begin{array}{cc}{S}_2\hfill & \mathrm{if}b=0\hfill \\ s_{m+1},s_{m+2},\dots ,s_{2m},s_1,s_2,\dots ,s_m\hfill & \mathrm{if}b=1\hfill \end{array}\right.$$

The player executes this operation in a place where the other players cannot see. The player must not disclose b.

Note that the bit b is not newly selected by the player. This is the difference between the primitive in Definition 1, where a random bit must be newly selected by the player.

Note that in many protocols below, selecting left m cards is executed after a private reverse cut. The sequence of these two operations is called a private reverse selection. A private reverse selection is the following procedure on an even sequence $S_2=s_1,s_2,\dots ,s_{2m}$ and a bit $b\in \{0,1\}$. A player outputs the following:

$$S_3=\left\{\begin{array}{cc}{s}_1,s_2,\dots ,s_m\hfill & \mathrm{if}b=0\hfill \\ s_{m+1},s_{m+2},\dots ,s_{2m}\hfill & \mathrm{if}b=1\hfill \end{array}\right.$$

Primitive 3.

(Private reveal) A player privately opens a given committed bit. The player must not disclose the obtained value.

Using the obtained value, the player privately sets a sequence of cards.

Consider the case when Alice executes a private random bisection cut on $commit\left(x\right)$ and Bob executes a private reveal on the bit. Since the committed bit is randomized by the bit b selected by Alice, the revealed bit is $x\oplus b$. Bob obtains no information about x if b is randomly selected and not disclosed by Alice. Bob must not disclose the obtained value. If Bob discloses the obtained value to Alice, Alice knows the value of the committed bit.

2.3. Definition of Round

The space complexity of card-based protocols is evaluated by the number of cards. We define the number of rounds as a criterion to evaluate the time complexity of card-based protocols, using private operations. The first round begins from the initial state. The first round is (possibly parallel) local executions by each player, using the cards initially given to each player. It ends at the instant when no further local execution is possible without receiving cards from another player. The local executions in each round include sending cards to some other players but do not include receiving cards. The result of every private execution is known to the player. For example, shuffling for which the result is unknown to the player themselves is not executed. Since the private operations are executed in a place where the other players cannot see, it is hard to force the player to execute such operations whose result is unknown to the player. The i(>1)-th round begins with receiving all the cards sent during the $(i-1)$-th round. Each player executes local executions using the received cards and the cards left to the player at the end of the $(i-1)$-th round. Each player executes local executions until no further local execution is possible without receiving cards from another player. The number of rounds of a protocol is the maximum number of rounds necessary to output the result among all possible inputs and random values.

Let us show an example of a protocol execution and the number of rounds.

Protocol 1.

(AND protocol in [9])

Input: $commit\left(x\right)$ and $commit\left(y\right)$

Output: $commit(x\wedge y)$

1. 

Alice executes a private random bisection cut on $commit\left(x\right)$. Let the output be $commit\left(x^{\prime }\right)$. Alice sends $commit\left(x^{\prime }\right)$ and $commit\left(y\right)$ to Bob.

2. 

Bob executes a private reveal on $commit\left(x^{\prime }\right)$. Bob privately sets the following:

$$S_2=\left\{\begin{array}{cc}commit\left(y\right)\left|\right|commit\left(0\right)\hfill & \mathrm{if}{x}^{\prime }=1\hfill \\ commit\left(0\right)\left|\right|commit\left(y\right)\hfill & \mathrm{if}{x}^{\prime }=0\hfill \end{array}\right.$$

and sends $S_2$ to Alice.

3. 

Alice executes a private reverse selection on $S_2$ using the bit b generated in the private random bisection cut. Let the obtained sequence be $S_3$. Alice outputs $S_3$.

The first round ends at the instant when Alice sends $commit\left(x^{\prime }\right)$ and $commit\left(y\right)$ to Bob. The second round begins at receiving the cards by Bob. The second round ends at the instant when Bob sends $S_2$ to Alice. The third round begins upon receiving the cards by Alice. The number of rounds of this protocol is three.

Since each operation is relatively simple, the dominating time to execute protocols with private operations is the time to send cards between players and set up so that the cards are not seen by the other players. Thus, the number of rounds is the criterion to evaluate the time complexity of card-based protocols with private operations.

The minimum number of rounds of most protocols is two. Suppose that the number of rounds is one. Suppose that a player, for example, Alice, has some (or all) of the final outputs of the protocol. Since the number of rounds is one, sending cards between players is not executed. Thus, all the operations to obtain Alice’s outputs are executed by Alice. Thus, Alice knows the relation between the committed inputs and Alice’s outputs. If the output cards are faced up to know the results, Alice knows the private input values. Therefore, most protocols need at least two rounds for the privacy of the committed inputs.

2.4. Our Results

The protocols in [9] are three rounds and use four cards. We show a two-round logical XOR protocol, using four cards. Then, we show two-round logical AND and copy protocols, using six cards. Though the number of cards is increased, the number of rounds is minimal. Another advantage of these two-round protocols is that each player does not need to remember the random bit. In the protocols in [9], a player needs to remember the random bit until the player receives the cards again to execute a private reverse cut. If a player replies late, the other player must remember the random bit for a very long time. If a player executes many instances of the protocols with many players in parallel, it is hard for the player to remember so many random values. In the two-round protocols, the first player can exit from the protocol after she sends the cards to the other player. Note that Alice obtains the final result by the three-round protocols in [9] but Bob obtains the final result by the two-round protocols in this paper. These protocols can be used only if this change is acceptable by both players. Note that the two-round protocols with the four card logical XOR, six card logical AND, and copy with private operations are implicitly shown by [7] since one public shuffle used in the paper can be realized by two private shuffles by the two players. This paper shows another type of protocol with fewer shuffles.

The above two-round protocols do not use private reverse cuts, using a remembered bit. Thus, there is a question of whether we can obtain protocols without another type of private operation. This paper also answers this question. We show protocols that do not use private reveals. There is a concern in using this primitive: a player might make the mistake of opening cards that are not allowed and obtaining private values. Since no other player sees the operation, it is hard to detect or prevent such a mistake. If private reveals are not executed at all, protections, such as putting each card in an envelope, can be put in place to prove that incorrectly opening cards is not executed during the private operations. Thus, it would be better if all reveals are publicly executed. Even if we do not use private reveals, the number of rounds is unchanged for logical XOR and copy protocols. For AND and copy, both the (1) two-round and six card protocol and (2) three-round and four card protocol can be obtained, even without private reveals.

Next, we show protocols that preserve an input. In most protocols, input values are lost at the end of the protocol. If an input is not lost, the input can be used for further computations, using the same input value. Thus, protocols that preserve an input are considered [39]. Protocols that preserve an input are shown.

Last, we show protocols with asymmetric cards. By using asymmetric cards, the numbers of cards are halved for all protocols.

3. XOR, AND, and Copy with the Minimum Number of Rounds

This section shows our new two-round protocols for XOR, AND, and copy.

These protocols do not use private reverse cuts, using the remembered random bit. Thus, the first player, Alice, does not need to remember the random bit b after she sends the cards to the other player.

3.1. XOR Protocol

Protocol 2.

(XOR protocol with the minimum number of rounds)

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\oplus y)$.

1. 

Alice executes a private random bisection cut on input $S_0=commit\left(x\right)$ and $S_0^{\prime }=commit\left(y\right)$, using the same random bit b. Let the output be $S_1=commit\left(x^{\prime }\right)$ and $S_1^{\prime }=commit\left(y^{\prime }\right)$, respectively. Note that $x^{\prime }=x\oplus b$ and $y^{\prime }=y\oplus b$. Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private reveal on $S_1=commit\left(x^{\prime }\right)$. Bob executes a private reverse cut on $S_1^{\prime }$ using $x^{\prime }$. Let the result be $S_2$. Bob outputs $S_2$.

The protocol is two rounds.

Theorem 1.

The XOR protocol is correct and secure. It uses the minimum number of cards.

Proof. 

Correctness: Alice sends $commit(x\oplus b)$ and $commit(y\oplus b)$ to Bob. Bob swaps the pair of $commit(y\oplus b)$ if $x\oplus b=1$. Thus, the output $S_2$ is $(y\oplus b)\oplus (x\oplus b)=x\oplus y$. Therefore, the output is correct.

Alice and Bob’s security: Alice sees no open cards. Thus, Alice obtains no information. Bob sees $x\oplus b$. Since b is a random value that Bob does not know, Bob obtains no information about x.

The number of cards: At least four cards are necessary for any protocol to input x and y. This protocol uses no additional cards other than the input cards. □

Note that though the same bit b is used to randomize x and y, it is not a security problem because $y\oplus b$ is not opened.

The number of rounds is the minimum. Mizuki et al. showed a four-card protocol with one public shuffle [7]. Since one public shuffle can be changed to two private shuffles by each player, the minimum number of rounds is also achieved by their protocol. However, the protocol needs two shuffles; thus, our new protocol is more simple. A comparison of committed-input, committed-output XOR protocols using private operations is shown in Table 1.

3.2. AND Protocol

Protocol 3.

(AND protocol with the minimum number of rounds)

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\wedge y)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$ and $S_0^{\prime }=commit\left(0\right)\left|\right|$$commit\left(y\right)$ using the same random bit b. Two new cards are used to set $commit\left(0\right)$. Let the output be $S_1=commit\left(x^{\prime }\right)$ and $S_1^{\prime }$, respectively. Note the following:

$$S_1^{\prime }=\left\{\begin{array}{cc}commit\left(y\right)\left|\right|commit\left(0\right)\hfill & \mathrm{if}b=1\hfill \\ commit\left(0\right)\left|\right|commit\left(y\right)\hfill & \mathrm{if}b=0\hfill \end{array}\right.$$

Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private reveal on $S_1$. Bob executes a private reverse selection on $S_1^{\prime }$ using $x^{\prime }$. Let the selected cards be $S_2$. Bob outputs $S_2$ as the result.

The protocol is two rounds. The protocol uses six cards since two new cards are used to set $commit\left(0\right)$.

Theorem 2.

The AND protocol is correct and secure.

Proof. 

Correctness: The desired output can be represented as follows.

$$x\wedge y=\left\{\begin{array}{cc}y\hfill & \mathrm{if}x=1\hfill \\ 0\hfill & \mathrm{if}x=0\hfill \end{array}\right.$$

(1)

Bob outputs $commit\left(y\right)$ as $S_2$ when $(x^{\prime },b)=(0,1)$ or $(1,0)$. Since $x^{\prime }=x\oplus b$, these cases equal to $x=1$. Bob outputs $commit\left(0\right)$ as $S_2$ when $(x^{\prime },b)=(0,0)$ or $(1,1)$. Since $x^{\prime }=x\oplus b$, these cases equal to $x=0$. Thus, the output is correct.

Alice and Bob’s security is the same as in the XOR protocol. □

The number of rounds is the minimum. Mizuki et al. showed a six-card protocol with one public shuffle [7]. Since one public shuffle can be changed to two private shuffles by each player, the minimum number of rounds is also achieved by their protocol. However, the protocol needs two shuffles, thus our new protocol is simple. Comparison of committed-input, committed-output logical AND protocols using private operations are shown in Table 2.

3.3. Copy Protocol

Next, we show a new copy protocol with the minimum number of rounds.

Protocol 4.

(Copy protocol with the minimum number of rounds)

Input: $commit\left(x\right)$.

Output: m copies of $commit\left(x\right)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$. Let the output be $S_1=commit\left(x^{\prime }\right)$. Alice sets $S_1^{\prime }$ as m copies of $commit\left(b\right)$, where b is the bit selected in the random bisection cut. Note that $x^{\prime }=x\oplus b$. Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private reveal on $S_1$ and obtains $x^{\prime }$. Bob executes a private reverse cut on each pair of $S_1^{\prime }$ using $x^{\prime }$. Let the result be $S_2$. Bob outputs $S_2$.

The protocol is two rounds. The protocol uses $2m+2$ cards.

Theorem 3.

The copy protocol is correct and secure.

Proof. 

Correctness: Since Bob obtains $x^{\prime }=x\oplus b$, the output is $b\oplus (x\oplus b)=x$.

Alice and Bob’s security is the same as in the XOR protocol. □

Though the number of cards is increased, the number of rounds is the minimum. A comparison of the copy protocols (when $m=2$) is shown in Table 3. Mizuki et al. showed a six-card protocol with one public shuffle [7]. Since one public shuffle can be changed to two private shuffles by each player, the minimum number of rounds is also achieved by their protocol. However, the protocol needs two shuffles; thus, our new protocol is more simple.

3.4. Any Two-Variable Boolean Functions

Though this paper shows logical AND and logical XOR, any two-variable Boolean functions can also be calculated by a similar protocol. Though the protocol differs, the idea of the construction is similar to the one for the three-round protocol in [9].

Theorem 4.

Any two-variable Boolean function can be securely calculated in two rounds and at most six cards.

Proof. 

Any two-variable Boolean function $f(x,y)$ can be written as follows:

$$f(x,y)=\left\{\begin{array}{cc}f(1,y)\hfill & \mathrm{if}x=1\hfill \\ f(0,y)\hfill & \mathrm{if}x=0\hfill \end{array}\right.$$

where $f(1,y)$ and $f(0,y)$ are y, $\overline{y}$, 0, or 1. However, we need to consider the case when one of $f(1,y)$ and $f(0,y)$ is y or $\overline{y}$ and the other is 0, or 1. The reason, written in [9] is as follows. First, consider the case when both of $f(1,y)$ and $f(0,y)$ are 0 or 1. $\left(f\right(1,y),$ $f(0,y))=(0,0)$ (or $(1,1)$) means that $f(x,y)=0$ (or $f(x,y)=1$), thus we do not need to calculate f. $\left(f\right(1,y),f(0,y\left)\right)=(1,0)$ (or $(0,1)$) means the $f(x,y)=x$ (or $f(x,y)=\overline{x}$); thus, we do not need to calculate f by a two player protocol.

Next, consider the case when both of $\left(f\right(1,y),f(0,y\left)\right)$ are y (or $\overline{y}$). This case is when $f(x,y)=y$ (or $f(x,y)=\overline{y}$); thus, we do not need to calculate f by a two-player protocol.

The next case is when $\left(f\right(1,y),f(0,y\left)\right)$ is (y, $\overline{y}$) or ($\overline{y}$, y). $\left(f\right(1,y),f(0,y\left)\right)$ $=(\overline{y},y)$ is $x\oplus y$ (XOR). $(f(1,y),f(0,y))=(y,\overline{y})$ is $\overline{x\oplus y}$; thus, this function can be calculated as follows: execute the XOR protocol and NOT is taken to the output. Thus, this function can also be calculated.

The remaining case is when one of $\left(f\right(1,y),f(0,y\left)\right)$ is y or $\overline{y}$ and the other is 0 or 1. We can modify the first step of the AND protocol and Alice sets as follows:

$$S_1^{\prime }=\left\{\begin{array}{cc}commit\left(f\right(1,y\left)\right)\left|\right|commit\left(f\right(0,y\left)\right)\hfill & \mathrm{if}b=1\hfill \\ commit\left(f\right(0,y\left)\right)\left|\right|commit\left(f\right(1,y\left)\right)\hfill & \mathrm{if}b=0\hfill \end{array}\right.$$

using one $commit\left(y\right)$ and two new cards, since one of $\left(f\right(1,y),$ $f(0,y))$ is y or $\overline{y}$ and the other is 0 or 1. Bob executes a private reveal on $S_1=commit\left(x^{\prime }\right)$ and selects the left(right) pair if $x^{\prime }=0$ ($x^{\prime }=1$). Thus, Bob selects $commit\left(f\right(1,y\left)\right)$ if $x=1$. Bob selects $commit\left(f\right(0,y\left)\right)$ if $x=0$.

Thus, any two-variable Boolean function can be calculated with, at most, six cards and in two rounds. □

3.5. n-Variable Boolean Functions

Since two-variable Boolean functions, logical negation, and a copy can be executed, any n-variable Boolean function can be calculated by the combination of the above protocols.

As another implementation with more cards, we show that any n-variable Boolean function can be calculated by the following protocol in two rounds, whose technique is similar to the one in [35]. Let f be any n-variable logical function.

Protocol 5.

(Protocol for any Boolean function with two rounds)

Input: $commit\left(x_i\right)(i=1,2,\dots ,n)$.

Output: $commit\left(f(x_1,x_2,\dots ,x_n)\right)$.

1. 

Alice executes a private random bisection cut on $commit\left(x_i\right)$ $(i=1,2,\dots ,n)$. Let the results be $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$. $x_i^{\prime }=x_i\oplus b_i(i=1,2,\dots ,n)$. Note that one random bit $b_i$ is selected for each $x_i(i=1,2,\dots ,n)$. Alice generates $2^n$ commitment $S_{a_1,a_2,\dots ,a_n}$ $(a_i\in \{0,1\},i=1,2,\dots ,n)$ as $S_{a_1,a_2,\dots ,a_n}=$ $commit\left(f(a_1\oplus b_1,a_2\oplus b_2,\dots ,a_n\oplus b_n)\right)$.Alice sends $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$ and $S_{a_1,a_2,\dots ,a_n}$ $(a_i\in \{0,1\},i=1,2,\dots ,n)$ to Bob.

2. 

Bob executes a private reveal on $commit\left(x_i^{\prime }\right)$ $(i=1,2,\dots ,n)$. Bob outputs $S_{x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime }}$.

The protocol is two-round. The number of cards is $2^{n+1}+2n$.

Theorem 5.

Protocol 5 is correct and secure.

Proof. 

Correctness: Since $S_{x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime }}=commit\left(f(b_1\oplus x_1^{\prime },b_2\oplus x_2^{\prime },\dots ,b_n\oplus x_n^{\prime })\right)=$

$commit\left(f(x_1,x_2,\dots ,x_n)\right)$, the output is correct.

Alice and Bob’s security is the same as in the XOR protocol. □

4. Protocols without Private Reveals

This section shows that the above protocols can be executed without the private reveal operations. Since it is hard to prevent mistakes of privately revealing cards that are not allowed, it would be better for all reveal operations to be publicly executed. The general conversion rule is as follows: When Bob executes a private reveal and set a sequence S in the original protocol, Bob executes a private random bisection cut to $commit(x\oplus b)$ instead. Let $b^{\prime }$ be the random bit selected by Bob. Then, Bob publicly opens the committed bit and publicly sets a sequence S by the original rule. Bob (and Alice) then executes private reverse cuts to undo the randomization by b and $b^{\prime }$.

4.1. XOR Protocol without Private Reveals

Protocol 6.

(XOR protocol without private reveals)

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\oplus y)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$ and $S_0^{\prime }=commit\left(y\right)$ using the same random bit b. Let the output be $S_1=commit\left(x^{\prime }\right)$ and $S_1^{\prime }=commit\left(y^{\prime }\right)$, respectively. Note that $x^{\prime }=x\oplus b$ and $y^{\prime }=y\oplus b$. Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private random bisection cut on $S_1$ and $S_1^{\prime }$ using a private bit $b^{\prime }$. Let the output be $S_2=commit\left(x^{\prime \prime }\right)$ and $S_2^{\prime }=commit\left(y^{\prime \prime }\right)$, respectively. $x^{\prime \prime }=x\oplus b\oplus b^{\prime }$ and $y^{\prime \prime }=y\oplus b\oplus b^{\prime }$ hold. Bob publicly opens $S_2$ and obtains $x^{\prime \prime }$. Alice can see $x^{\prime \prime }$. Bob publicly sets the following:

$$S_3=\left\{\begin{array}{cc}commit\left(\overline{y^{\prime \prime }}\right)\hfill & \mathrm{if}{x}^{\prime \prime }=1\hfill \\ commit\left(y^{\prime \prime }\right)\hfill & \mathrm{if}{x}^{\prime \prime }=0\hfill \end{array}\right.$$

$S_3$ is the final result.

The protocol is two rounds.

Theorem 6.

The XOR protocol is correct and secure. It uses the minimum number of cards.

Proof. 

Correctness: Bob obtains $commit(x\oplus b\oplus b^{\prime })$ and $commit(y\oplus b\oplus b^{\prime })$. Bob sets $S_3$ as $y^{\prime \prime }\oplus x^{\prime \prime }=y\oplus b\oplus b^{\prime }\oplus x\oplus b\oplus b^{\prime }=x\oplus y$. Thus, the result is correct.

Alice and Bob’s security: After Bob executes a private random bisection cut on $S_1$, the obtained value $commit\left(x^{\prime \prime }\right)=commit(x\oplus b\oplus b^{\prime })$. Even if this value is opened, no player can obtain the value of x since Alice knows b and $x\oplus b\oplus b^{\prime }$ and Bob knows $b^{\prime }$ and $x\oplus b\oplus b^{\prime }$.

At least four cards are necessary for any protocol to input x and y. This protocol uses no additional cards other than the input cards. □

4.2. AND Protocol without Private Reveals

We can consider two kinds of protocols: (1) three rounds and four cards (the minimum number of cards); and (2) two rounds (the minimum number of rounds) and six cards.

Protocol 7.

(AND protocol without private reveals (1))

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\wedge y)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$. Let the result be $S_1=commit\left(x^{\prime }\right)$. Alice sends $S_1$ and $S_0^{\prime }=commit\left(y\right)$ to Bob.

2. 

Bob executes a private random bisection cut on $S_1$, using a private bit $b^{\prime }$. Let the result be $S_1^{\prime }=commit\left(x^{\prime \prime }\right)$. $x^{\prime \prime }=x\oplus b\oplus b^{\prime }$ holds. Bob publicly opens $S_1^{\prime }$ and obtains value $x^{\prime \prime }$. Alice can see $x^{\prime \prime }$. Bob publicly sets the following:

$$S_2=\left\{\begin{array}{cc}commit\left(y\right)\left|\right|commit\left(0\right)\hfill & \mathrm{if}{x}^{\prime \prime }=1\hfill \\ commit\left(0\right)\left|\right|commit\left(y\right)\hfill & \mathrm{if}{x}^{\prime \prime }=0\hfill \end{array}\right.$$

Bob then executes a private reverse cut on $S_2$ using the bit $b^{\prime }$ generated in the private random bisection cut. Let the result be $S_3$. Bob sends $S_3$ to Alice.

3. 

Alice executes a private reverse selection on $S_3$ using the bit b generated in the private random bisection cut. Let the result be $S_4$. Alice outputs $S_4$.

The number of rounds is three.

Theorem 7.

Protocol 7 is correct, secure, and uses the minimum number of cards.

Proof. 

Correctness: The desired output can be represented by Equation (1). When Bob obtains $x^{\prime \prime }=1$, $commit\left(y\right)\left|\right|commit\left(0\right)$ is set as $S_2$. When Bob obtains $x^{\prime \prime }=0$, $commit\left(0\right)\left|\right|$$commit\left(y\right)$ is set as $S_2$. Since Bob executes a private reverse cut on $S_2$, $commit\left(y\right)\left|\right|commit\left(0\right)$ is given to Alice when $(x^{\prime \prime },b^{\prime })=(1,0)$ or $(0,1)$. Since $x^{\prime \prime }=x\oplus b\oplus b^{\prime }$, these cases equal to $x\oplus b=1$. $commit\left(0\right)\left|\right|commit\left(y\right)$ is given to Alice when $(x^{\prime \prime },b^{\prime })=(1,1)$ or $(0,0)$. These cases equal to $x\oplus b=0$.

Thus Alice’s output is $commit\left(y\right)$ if $(x\oplus b,b)=(1,0)$ or $(0,1)$. These cases equal to $x=1$. Alice’s output is $commit\left(0\right)$ if $(x\oplus b,b)=(1,1)$ or $(0,0)$. These cases equal to $x=0$. Therefore, the output is correct.

Alice and Bob’s security is the same as the XOR protocol without private reveals.

The number of cards: Any committed input protocol needs at least four cards to input. When Bob sets $S_2$, the cards used for $commit\left(x^{\prime \prime }\right)$ can be re-used to set $commit\left(0\right)$. Thus, the total number of cards is four and the minimum. □

Protocol 8.

(AND protocol without private reveals (2))

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\wedge y)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$ and $S_0^{\prime }=commit\left(0\right)\left|\right|$ $commit\left(y\right)$ using the same random bit b. Two new cards are used to set $commit\left(0\right)$. Let the output be $S_1=commit\left(x^{\prime }\right)$ and $S_1^{\prime }$, respectively. Note the following:

$$S_1^{\prime }=\left\{\begin{array}{cc}commit\left(y\right)\left|\right|commit\left(0\right)\hfill & \mathrm{if}b=1\hfill \\ commit\left(0\right)\left|\right|commit\left(y\right)\hfill & \mathrm{if}b=0\hfill \end{array}\right.$$

Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private random bisection cut on $S_1$ and $S_1^{\prime }$ using the same random bit $b^{\prime }$. Let the result be $S_2$ and $S_2^{\prime }$, respectively. Note that $S_2=commit(x\oplus b\oplus b^{\prime })$. Bob publicly opens cards of $S_2$ and obtains $x^{\prime \prime }=x\oplus b\oplus b^{\prime }$. Alice can see $x^{\prime \prime }$. Bob publicly selects the left pair of $S_2^{\prime }$ if $x^{\prime \prime }=0$, otherwise selects the right pair of $S_2^{\prime }$. Bob outputs the pair as the result.

The protocol is two rounds. The protocol uses six cards since two new cards are used to set $commit\left(0\right)$.

Theorem 8.

Protocol 8 is correct and secure.

Proof. 

$$S_2^{\prime }=\left\{\begin{array}{cc}commit\left(y\right)\left|\right|commit\left(0\right)\hfill & \mathrm{if}b\oplus b^{\prime }=1\hfill \\ commit\left(0\right)\left|\right|commit\left(y\right)\hfill & \mathrm{if}b\oplus b^{\prime }=0\hfill \end{array}\right.$$

Thus Bob outputs $commit\left(y\right)$ if $(b\oplus b^{\prime },x\oplus b\oplus b^{\prime })=(1,0)$ or $(0,1)$. These cases equal to $x=1$. Bob outputs $commit\left(0\right)$ if $(b\oplus b^{\prime },x\oplus b\oplus b^{\prime })=(1,1)$ or $(0,0)$. These cases equal to $x=0$. Therefore, the output is correct.

Alice and Bob’s security is the same as the XOR protocol without private reveals. □

Using the argument in Section 3.4, any two-variable Boolean function can also be calculated without private reveals by (1) three rounds and four cards, and (2) two rounds and six cards.

4.3. Copy Protocol without Private Reveals

Similar to the AND protocol, we can consider two kinds of copy protocols: (1) three rounds and $2m$ cards (the minimum number of cards); and (2) two rounds (the minimum number of rounds) and $2m+2$ cards.

Protocol 9.

(Copy protocol without private reveals (1))

Input: $commit\left(x\right)$.

Output: m copies of $commit\left(x\right)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$. Let the result be $S_1=commit\left(x^{\prime }\right)$. Note that $x^{\prime }=x\oplus b$. Alice sends $S_1$ to Bob.

2. 

Bob executes a private random bisection cut on $S_1$ using a private random bit $b^{\prime }$. Let the result be $S_2=commit\left(x^{\prime \prime }\right)$. Note that $x^{\prime \prime }=x\oplus b\oplus b^{\prime }$.Bob publicly opens $S_2$ and obtains $x^{\prime \prime }$. Alice can see $x^{\prime \prime }$. Bob publicly sets m pairs of cards of $x^{\prime \prime }$. Bob faces down the cards. Let the cards be $S_3$. Bob executes a private reverse cut on each pair of $S_3$ using $b^{\prime }$. Let the result be $S_3^{\prime }$. Bob sends $S_3^{\prime }$ to Alice.

3. 

Alice executes a private reverse cut on each pair of $S_3^{\prime }$ using b. Alice outputs the pairs.

The protocol is three rounds. The protocol uses $2m$ cards since the cards of $S_2$ are reused to set $S_3$.

Theorem 9.

Protocol 9 is correct and secure.

Proof. 

Correctness: Bob makes copies of $commit\left(x^{\prime \prime }\right)$. Since $x^{\prime \prime }=x\oplus b\oplus b^{\prime }$, after the private reverse cuts by Bob and Alice, the cards are $commit(x^{\prime \prime }\oplus b^{\prime }\oplus b)=commit(x\oplus b\oplus b^{\prime }\oplus b^{\prime }\oplus b)=commit\left(x\right)$. Thus, the result is correct.

Alice and Bob’s security is the same as the XOR protocol without private reveals. □

Protocol 10.

(COPY protocol without private reveals (2))

Input: $commit\left(x\right)$.

Output: m copies of $commit\left(x\right)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$. Let the result be $S_1=commit\left(x^{\prime }\right)$. Note that $x^{\prime }=x\oplus b$. Alice privately sets $S_1^{\prime }$ as m copies of $commit\left(b\right)$. Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private random bisection cut on $S_1$ and each pair of $S_1^{\prime }$ using a private random bit $b^{\prime }$. Let the output be $S_2=commit\left(x^{\prime \prime }\right)$ and $S_2^{\prime }$, respectively.Bob publicly opens $S_2$ and obtains $x^{\prime \prime }$. Alice can see $x^{\prime \prime }$. Bob publicly swaps each pair of $S_2^{\prime }$ if $x^{\prime \prime }=1$. Otherwise, Bob does nothing. Let the result be $S_3$. Bob outputs $S_3$.

The protocol is two rounds. The protocol uses $2m+2$ cards.

Theorem 10.

Protocol 10 is correct and secure.

Proof. 

Correctness: Bob obtains $commit\left(x^{\prime \prime }\right)$ and $commit(b\oplus b^{\prime })$, where $x^{\prime \prime }=x\oplus b\oplus b^{\prime }$. Bob sets $S_3$ as $commit(b\oplus b^{\prime }\oplus x^{\prime \prime })=commit(b\oplus b^{\prime }\oplus x\oplus b\oplus b^{\prime })=commit\left(x\right)$. Thus, the result is correct.

Alice and Bob’s security is the same as the XOR protocol without private reveals. □

4.4. n-Variable Boolean Functions without Private Reveals

Let f be an n-variable Boolean function.

Protocol 11.

(Protocol for n-variable Boolean function without private reveal)

Input: $commit\left(x_i\right)(i=1,2,\dots ,n)$.

Output: $commit\left(f(x_1,x_2,\dots ,x_n)\right)$.

1. 

Alice executes a private random bisection cut on $commit\left(x_i\right)$ $(i=1,2,\dots ,n)$. Let the results be $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$. $x_i^{\prime }=x_i\oplus b_i(i=1,2,\dots ,n)$. Note that one random bit $b_i$ is selected for each $x_i(i=1,2,\dots ,n)$. Alice generates $2^n$ commitment $S_{a_1,a_2,\dots ,a_n}$ $(a_i\in \{0,1\},i=1,2,\dots ,n)$ as $S_{a_1,a_2,\dots ,a_n}=$ $commit\left(f(a_1\oplus b_1,a_2\oplus b_2,\dots ,a_n\oplus b_n)\right)$.Alice sends $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$ and $S_{a_1,a_2,\dots ,a_n}$ $(a_i\in \{0,1\},i=1,2,\dots ,n)$ to Bob.

2. 

Bob executes a private random bisection cut on $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$. Note that one random bit $b_i^{\prime }$ is selected for each $x_i^{\prime }(i=1,2,\dots ,n)$. Let $commit\left(x_i^{\prime \prime }\right)$ $(i=1,2,\dots ,n)$ be the obtained value. $x_i^{\prime \prime }=x_i\oplus b_i\oplus b_i^{\prime }(i=1,2,\dots ,n)$ is satisfied. Bob privately relocates $S_{a_1,a_2,\dots ,a_n}(a_i\in \{0,1\},i=1,2,\dots ,n)$ so that $S_{a_1,a_2,\dots ,a_n}^{\prime }=S_{a_1\oplus b_1^{\prime },a_2\oplus b_2^{\prime },\dots ,a_n\oplus b_n^{\prime }}(a_i\in \{0,1\},$ $i=1,2,\dots ,n)$. The cards satisfy $S_{a_1,a_2,\dots ,a_n}^{\prime }=$ $commit\left(f(a_1\oplus b_1\oplus b_1^{\prime },a_2\oplus b_2\oplus b_2^{\prime },\dots ,a_n\oplus b_n\oplus b_n^{\prime })\right)$.Bob publicly reveals $commit\left(x_i^{\prime \prime }\right)$ and obtains $x_i^{\prime \prime }(i=1,2,\dots ,n)$. Alice can see $x_i^{\prime \prime }(i=1,2,\dots ,n)$. Bob publicly selects $S_{x_1^{\prime \prime },x_2^{\prime \prime },\dots ,x_n^{\prime \prime }}^{\prime }$.

The protocol is two rounds. The number of cards is $2^{n+1}+2n$.

Theorem 11.

Protocol 11 is correct and secure.

Proof. 

Correctness: Since $S_{x_1^{\prime \prime },x_2^{\prime \prime },\dots ,x_n^{\prime \prime }}^{\prime }=commit\left(f(x_1\oplus b_1\oplus b_1^{\prime }\oplus b_1\oplus b_1^{\prime },x_2\oplus b_2\oplus b_2^{\prime }\oplus b_2\oplus b_2^{\prime },\dots ,x_n\oplus b_n\oplus b_n^{\prime }\oplus b_n\oplus b_n^{\prime })\right)=$ $commit\left(f(x_1,x_2,\dots ,x_n)\right)$, the output is correct.

The security of Alice and Bob is the same as the XOR protocol without private reveals. □

5. Protocols That Preserve an Input

In the above protocols to calculate Boolean functions, the input commitment values are lost. If an input is not lost, the input commitment can be used as an input to another calculation. Thus, protocols that preserve an input are discussed [39]. For the three-round XOR and AND protocols in [9], protocols that preserve an input were shown [9].

First, consider XOR protocols in Section 3 and Section 4.

Protocol 12.

(XOR protocol that preserves an input)

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\oplus y)$ and $commit\left(x\right)$.

1. 

Alice executes a private random bisection cut on input $S_0=commit\left(x\right)$ and $S_0^{\prime }=commit\left(y\right)$ using the same random bit b. Let the output be $S_1=commit\left(x^{\prime }\right)$ and $S_1^{\prime }=commit\left(y^{\prime }\right)$, respectively. Note that $x^{\prime }=x\oplus b$ and $y^{\prime }=y\oplus b$. Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private reveal on $S_1=commit\left(x^{\prime }\right)$. Bob executes a private reverse cut on $S_1^{\prime }$, using $x^{\prime }$. Let the result be $S_2$. Bob outputs $S_2$. Bob sends back $S_1=commit\left(x^{\prime }\right)$ to Alice.

3. 

Alice executes a private reverse cut on $S_1$ using b and obtains $commit\left(x\right)$.

In Protocol 2, since $commit\left(x^{\prime }\right)$ is unnecessary after Bob’s private reveal, the cards can be sent back to Alice. Alice can recover $commit\left(x\right)$. The number of rounds is increased to three.

Theorem 12.

Protocol 12 is correct and secure.

Proof. 

Correctness: From the correctness of Protocol 2, $commit(x\oplus y)$ is obtained. $commit\left(x\right)$ can be obtained since $x\oplus b\oplus b=x$.

The security of Alice and Bob is the same as the XOR protocol without input preserving. □

Protocol 13.

(XOR protocol that preserves an input without private reveals)

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\oplus y)$ and $commit\left(x\right)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$ and $S_0^{\prime }=commit\left(y\right)$ using the same random bit b. Let the output be $S_1=commit\left(x^{\prime }\right)$ and $S_1^{\prime }=commit\left(y^{\prime }\right)$, respectively. Note that $x^{\prime }=x\oplus b$ and $y^{\prime }=y\oplus b$. Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private random bisection cut on $S_1$ and $S_1^{\prime }$ using a private bit $b^{\prime }$. Let the output be $S_2=commit\left(x^{\prime \prime }\right)$ and $S_2^{\prime }=commit\left(y^{\prime \prime }\right)$, respectively. $x^{\prime \prime }=x\oplus b\oplus b^{\prime }$ and $y^{\prime \prime }=y\oplus b\oplus b^{\prime }$ hold. Bob publicly opens $S_2$ and obtains $x^{\prime \prime }$. Alice can see $x^{\prime \prime }$. Bob publicly sets the following:

$$S_3=\left\{\begin{array}{cc}commit\left(\overline{y^{\prime \prime }}\right)\hfill & \mathrm{if}{x}^{\prime \prime }=1\hfill \\ commit\left(y^{\prime \prime }\right)\hfill & \mathrm{if}{x}^{\prime \prime }=0\hfill \end{array}\right.$$

$S_3$ is the output. Bob sends back $S_1=commit\left(x^{\prime }\right)$ to Alice.

3. 

Alice executes a private reverse cut on $S_1$ using b and obtains $commit\left(x\right)$.

Theorem 13.

Protocol 13 is correct and secure.

Proof. 

Correctness: From the correctness of Protocol 6, $commit(x\oplus y)$ is obtained. After Bob publicly reveals $S_2$ and obtains $x\oplus b\oplus b^{\prime }$, he can privately recover $commit\left(x^{\prime }\right)$ since he knows $b^{\prime }$. Thus, Bob can send back $commit\left(x^{\prime }\right)$ to Alice. $commit\left(x\right)$ can be obtained since $x\oplus b\oplus b=x$.

The security of Alice and Bob is the same as the XOR protocol without input preserving. □

The protocol is three rounds and uses four cards.

Similarly, the AND protocols in Section 3 and Section 4 can be modified to a three-round protocol to preserve an input.

Protocol 14.

(AND protocol that preserves an input)

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\wedge y)$ and $commit\left(x\right)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$ and $S_0^{\prime }=commit\left(0\right)\left|\right|$$commit\left(y\right)$ using the same random bit b. Two new cards are used to set $commit\left(0\right)$. Let the output be $S_1=commit\left(x^{\prime }\right)$ and $S_1^{\prime }$, respectively. Note the following:

$$S_1^{\prime }=\left\{\begin{array}{cc}commit\left(y\right)\left|\right|commit\left(0\right)\hfill & \mathrm{if}b=1\hfill \\ commit\left(0\right)\left|\right|commit\left(y\right)\hfill & \mathrm{if}b=0\hfill \end{array}\right.$$

Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private reveal on $S_1$. Bob executes a private reverse selection on $S_1^{\prime }$ using $x^{\prime }$. Let the selected cards be $S_2$. Bob outputs $S_2$ as the result. Bob sends back $S_1=commit\left(x^{\prime }\right)$ to Alice.

3. 

Alice executes a private reverse cut on $S_1$ using b and obtains $commit\left(x\right)$.

The number of rounds is three and the number of cards is six. Note that though the characteristics of the Protocol 14 are the same as the protocol in [9], the steps differ: for example, Alice obtains the output in [9] and Bob obtains the output in Protocol 14.

Theorem 14.

Protocol 14 is correct and secure.

Proof. 

Correctness: From the correctness of Protocol 3, $commit(x\wedge y)$ is obtained. After Bob privately reveals $S_1=commit\left(x^{\prime }\right)$, he can send back $commit\left(x^{\prime }\right)$ to Alice. $commit\left(x\right)$ can be obtained since $x\oplus b\oplus b=x$.

The security of Alice and Bob is the same as the AND protocol without input preserving. □

Protocol 15.

(AND protocol that preserves an input without private reveals)

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\wedge y)$ and $commit\left(x\right)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$. Let the result be $S_1=commit\left(x^{\prime }\right)$. Alice sends $S_1$ and $S_0^{\prime }=commit\left(y\right)$ to Bob.

2. 

Bob executes a private random bisection cut on $S_1$ using a private bit $b^{\prime }$. Let the result be $S_1^{\prime }=commit\left(x^{\prime \prime }\right)$. $x^{\prime \prime }=x\oplus b\oplus b^{\prime }$ holds. Bob publicly opens $S_1^{\prime }$ and obtains value $x^{\prime \prime }$. Alice can see $x^{\prime \prime }$. Bob publicly sets the following:

$$S_2=\left\{\begin{array}{cc}commit\left(y\right)\left|\right|commit\left(0\right)\hfill & \mathrm{if}{x}^{\prime \prime }=1\hfill \\ commit\left(0\right)\left|\right|commit\left(y\right)\hfill & \mathrm{if}{x}^{\prime \prime }=0\hfill \end{array}\right.$$

Bob then executes a private reverse cut on $S_2$ using the bit $b^{\prime }$ generated in the private random bisection cut. Let the result be $S_3$. Bob sends $S_3$ and $S_1$ to Alice.

3. 

Alice executes a private reverse selection on $S_3$ using the bit b generated in the private random bisection cut. Let the result be $S_4$. Alice outputs $S_4$. Alice executes a private reverse cut on $S_1$ using b and obtains $commit\left(x\right)$.

The number of rounds is three and the number of cards is six.

Theorem 15.

Protocol 15 is correct and secure.

Proof. 

Correctness: From the correctness of Protocol 7, $commit(x\wedge y)$ is obtained. After Bob publicly reveals $S_1^{\prime }$ and obtains $x\oplus b\oplus b^{\prime }$, he can privately recover $commit\left(x^{\prime }\right)$ since he knows $b^{\prime }$. Thus, Bob can send back $commit\left(x^{\prime }\right)$ to Alice. $commit\left(x\right)$ can be obtained since $x\oplus b\oplus b=x$.

The security of Alice and Bob is the same as the AND protocol without input preserving. □

As for the AND type protocol, to calculate $f(x,y)$, another protocol that preserves an input without additional cards can be obtained, using the technique in [39]. Note that the function f satisfies that one of $\left(f\right(0,y),f(1,y\left)\right)$ is y or $\overline{y}$ and the other is 0 or 1. Otherwise, we do not need to calculate f by the AND type two player protocol. When we execute the four-card AND type protocol without private reveals, two cards are selected by Alice at the final step. The remaining two cards are not used, but they also output some values. The unused two cards’ value is the following:

$$\left\{\begin{array}{cc}f(0,y)\hfill & \mathrm{if}x=1\hfill \\ f(1,y)\hfill & \mathrm{if}x=0\hfill \end{array}\right.$$

Thus, the output value is $commit(\overline{x}\wedge f(1,y)\oplus x\wedge f(0,y))$. The output $f(x,y)$ can be written as $x\wedge f(1,y)\oplus \overline{x}\wedge f(0,y)$. We execute the above XOR protocol that preserves an input without private reveal for these two output values so that $f(x,y)$ is preserved. The output of XOR protocol is $\overline{x}\wedge f(1,y)\oplus x\wedge f(0,y)\oplus x\wedge f(1,y)\oplus \overline{x}\wedge f(0,y)=f(1,y)\oplus f(0,y)$. Since one of $\left(f\right(0,y),f(1,y\left)\right)$ is y or $\overline{y}$ and the other is 0 or 1, the output is y or $\overline{y}$ (depending on f). Thus, input y can be recovered without additional cards.

Protocol 16.

(AND type protocol that preserves an input without private reveals)

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit\left(f\right(x,y\left)\right)$ and $commit\left(y\right)$.

1. 

Alice executes a private random bisection cut on $S_0=commit\left(x\right)$. Let the result be $S_1=commit\left(x^{\prime }\right)$. Alice sends $S_1$ and $S_0^{\prime }=commit\left(y\right)$ to Bob.

2. 

Bob executes a private random bisection cut on $S_1$, using a private bit $b^{\prime }$. Let the result be $S_1^{\prime }=commit\left(x^{\prime \prime }\right)$. $x^{\prime \prime }=x\oplus b\oplus b^{\prime }$ holds. Bob publicly opens $S_1^{\prime }$ and obtains value $x^{\prime \prime }$. Alice can see $x^{\prime \prime }$. Bob publicly sets the following:

$$S_2=\left\{\begin{array}{cc}commit\left(f\right(1,y\left)\right)\left|\right|commit\left(f\right(0,y\left)\right)\hfill & \mathrm{if}{x}^{\prime \prime }=1\hfill \\ commit\left(f\right(0,y\left)\right)\left|\right|commit\left(f\right(1,y\left)\right)\hfill & \mathrm{if}{x}^{\prime \prime }=0\hfill \end{array}\right.$$

Bob then executes a private reverse cut on $S_2$ using the bit $b^{\prime }$ generated in the private random bisection cut. Let the result be $S_3$. Bob sends $S_3$ to Alice.

3. 

Alice executes a private reverse selection on $S_3$ using the bit b generated in the private random bisection cut. Let the result be $S_4$. Alice outputs $S_4$. Let $S_4^{\prime }$ be the cards that are not selected.

4. 

Alice and Bob execute the XOR protocol that preserves an input without private reveals (Protocol 12) for $S_4$ and $S_4^{\prime }$. Let the preserved input, $S_4$, be the result. We obtain $commit\left(y\right)$ from the XOR result.

Thus, the protocol achieves preserving an input by four cards. The protocol does not use private reveals. The AND type protocol needs three rounds and the XOR protocol that preserves an input needs three rounds. The last round of the AND type protocol and the first round of the XOR protocol are executed by Alice, thus they can be done in one round. Therefore, the total number of rounds is five.

Theorem 16.

Protocol 16 is correct and secure.

Proof. 

Correctness: From the correctness of Protocol 7, $commit\left(f\right(x,y\left)\right)$ is obtained as $S_4$. Since $S_4^{\prime }=commit(\overline{x}\wedge f(1,y)\oplus x\wedge f(0,y))$, the output of the input preserving XOR is $f(x,y)\oplus \overline{x}\wedge f(1,y)\oplus x\wedge f(0,y)=f(0,y)\oplus f(1,y)$, which is y or $\overline{y}$. The input $f(x,y)$ is preserved, thus the output can be $commit\left(y\right)$ and $commit\left(f\right(x,y\left)\right)$

The security of Alice and Bob comes from the security of the AND protocol and the XOR protocol with input preserving. □

Lastly, we show n-variable Boolean function protocols that preserve inputs.

Protocol 17.

(Protocol for n-variable Boolean function that preserve inputs)

Input: $commit\left(x_i\right)(i=1,2,\dots ,n)$.

Output: $commit\left(f(x_1,x_2,\dots ,x_n)\right)$ and $commit\left(x_i\right)(i=1,2,\dots ,n)$.

1. 

Alice executes a private random bisection cut on $commit\left(x_i\right)$ $(i=1,2,\dots ,n)$. Let the results be $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$. $x_i^{\prime }=x_i\oplus b_i(i=1,2,\dots ,n)$. Note that one random bit $b_i$ is selected for each $x_i(i=1,2,\dots ,n)$. Alice generates $2^n$ commitment $S_{a_1,a_2,\dots ,a_n}$ $(a_i\in \{0,1\},i=1,2,\dots ,n)$ as $S_{a_1,a_2,\dots ,a_n}=$ $commit\left(f(a_1\oplus b_1,a_2\oplus b_2,\dots ,a_n\oplus b_n)\right)$.Alice sends $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$ and $S_{a_1,a_2,\dots ,a_n}$ $(a_i\in \{0,1\},i=1,2,\dots ,n)$ to Bob.

2. 

Bob executes a private reveal on $commit\left(x_i^{\prime }\right)$ $(i=1,2,\dots ,n)$. Bob outputs $S_{x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime }}$. Bob sends back $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$ to Alice.

3. 

Alice executes a private reverse cut on $commit\left(x_i^{\prime }\right)$ using $b_i(i=1,2,\dots ,n)$. Alice obtains $commit\left(x_i\right)(i=1,2,\dots ,n)$.

The protocol is three rounds.

Theorem 17.

Protocol 17 is correct and secure.

Proof. 

Correctness: From the correctness of Protocol 5, $commit\left(f(x_1,x_2,\dots ,x_n)\right)$ is obtained. After Bob privately reveals $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$, he can send back $commit\left(x_i^{\prime }\right)$$(i=1,2,\dots ,n)$ to Alice. $commit\left(x_i\right)(i=1,2,\dots ,n)$ can be obtained since $x_i\oplus b_i\oplus b_i=x_i(i=1,2,\dots ,n)$.

The security of Alice and Bob is the same as the n-variable Boolean function protocol without input preserving. □

Protocol 18.

(Protocol for n-variable Boolean function that preserves inputs without private reveals)

Input: $commit\left(x_i\right)(i=1,2,\dots ,n)$.

Output: $commit\left(f(x_1,x_2,\dots ,x_n)\right)$ and $commit\left(x_i\right)(i=1,2,\dots ,n)$.

1. 

Alice executes a private random bisection cut on $commit\left(x_i\right)$ $(i=1,2,\dots ,n)$. Let the results be $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$. $x_i^{\prime }=x_i\oplus b_i(i=1,2,\dots ,n)$. Note that one random bit $b_i$ is selected for each $x_i(i=1,2,\dots ,n)$. Alice generates $2^n$ commitment $S_{a_1,a_2,\dots ,a_n}$ $(a_i\in \{0,1\},i=1,2,\dots ,n)$ as $S_{a_1,a_2,\dots ,a_n}=$ $commit\left(f(a_1\oplus b_1,a_2\oplus b_2,\dots ,a_n\oplus b_n)\right)$.Alice sends $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$ and $S_{a_1,a_2,\dots ,a_n}$ $(a_i\in \{0,1\},i=1,2,\dots ,n)$ to Bob.

2. 

Bob executes a private random bisection cut on $commit\left(x_i^{\prime }\right)(i=1,2,\dots ,n)$. Note that one random bit $b_i^{\prime }$ is selected for each $x_i^{\prime }(i=1,2,\dots ,n)$. Let $commit\left(x_i^{\prime \prime }\right)$ $(i=1,2,\dots ,n)$ be the obtained value. $x_i^{\prime \prime }=x_i\oplus b_i\oplus b_i^{\prime }(i=1,2,\dots ,n)$ is satisfied. Bob privately relocates $S_{a_1,a_2,\dots ,a_n}(a_i\in \{0,1\},i=1,2,\dots ,n)$ so that $S_{a_1,a_2,\dots ,a_n}^{\prime }=S_{a_1\oplus b_1^{\prime },a_2\oplus b_2^{\prime },\dots ,a_n\oplus b_n^{\prime }}(a_i\in \{0,1\},$ $i=1,2,\dots ,n)$. The cards satisfy that $S_{a_1,a_2,\dots ,a_n}^{\prime }=$ $commit\left(f(a_1\oplus b_1\oplus b_1^{\prime },a_2\oplus b_2\oplus b_2^{\prime },\dots ,a_n\oplus b_n\oplus b_n^{\prime })\right)$.Bob publicly reveals $commit\left(x_i^{\prime \prime }\right)$ and obtains $x_i^{\prime \prime }(i=1,2,\dots ,n)$. Alice can see $x_i^{\prime \prime }(i=1,2,\dots ,n)$. Bob publicly selects $S_{x_1^{\prime \prime },x_2^{\prime \prime },\dots ,x_n^{\prime \prime }}^{\prime }$. Bob privately sets $commit(x_i^{\prime \prime }\oplus b_i^{\prime })(i=1,2,\dots ,n)$. Note that $x_i^{\prime \prime }\oplus b_i^{\prime }=x_i\oplus b_i(i=1,2,\dots ,n)$. Bob sends these pairs to Alice.

3. 

Alice privately executes a private reverse cut on $commit(x_i\oplus b_i)$ using $b_i$ for each $i(i=1,2,\dots ,n)$. Alice obtains $commit\left(x_i\right)(i=1,2,\dots ,n)$.

The protocol is three rounds.

Theorem 18.

Protocol 18 is correct and secure.

Proof. 

Correctness: From the correctness of Protocol 11, $commit\left(f(x_1,x_2,\dots ,x_n)\right)$ is obtained. After Bob publicly reveals $commit\left(x_i^{\prime \prime }\right)(i=1,2,\dots ,n)$, he can send back $commit\left(x_i^{\prime }\right)$$(i=1,2,\dots ,n)$ to Alice. $commit\left(x_i\right)(i=1,2,\dots ,n)$ can be obtained since $x_i\oplus b_i\oplus b_i=x_i(i=1,2,\dots ,n)$.

The security of Alice and Bob is the same as the n-variable Boolean function protocol without input preserving. □

6. Parallel Computations

The XOR protocol and AND-type protocol shown above can be executed in parallel, using the technique in [9]. Consider the case when $commit\left(x\right)$ and $commit\left(y_i\right)(i=1,2,\dots ,n)$ are given and $commit\left(f_i(x,y_i)\right)(i=1,2,\dots ,n)$ need to be calculated.

For example, we show the case of the minimum round protocols in Protocol 2 and 3. Alice executes a private random bisection cut on $S_0=commit\left(x\right)$ and $S_i=commit\left(f_i(0,y)\right)\left|\right|$$commit\left(f_i(1,y)\right)(i=1,2,\dots ,n)$ (Note that if $f_i(x,y_i)=x\oplus y_i$, $S_i=commit\left(y_i\right)$) using the same random bit b. Let the results be $S_i^{\prime }(i=0,1,2,\dots ,n)$. Alice sends $S_i^{\prime }(i=0,1,2,\dots ,n)$ to Bob. Bob executes a private reveal on $S_0^{\prime }$ and obtains $x^{\prime }=x\oplus b$. Bob executes a private reverse selection (or a private reverse cut) on $S_i^{\prime }$ using $x^{\prime }$ and obtains $commit\left(f_i(x,y_i)\right)(i=1,2,\dots ,n)$.

By the procedure, $commit\left(f_i(x,y_i)\right)(i=1,2,\dots ,n)$ are simultaneously obtained in two rounds. Parallel computations can also be considered for the other protocols.

7. Asymmetric Card Protocols

This section shows protocols when we use asymmetric cards shown in Section 2. one bit data can be represented by one card as = 0 and = 1.

For such an encoding method, a private random bisection cut on a committed bit is changed to turning the card upside-down, according to the random bit. A private reverse cut and a private reverse selection on an even sequence are unchanged. A private reverse cut and a private reverse selection on a single card are changed to turning the card upside down, according to the given bit. Using these private operations, all protocols shown above work for the asymmetric cards. The numbers of cards used by these protocols are half of the two-color card protocols. For example, XOR, AND, and copy protocols with the minimum number of rounds are shown below.

Protocol 19.

(asymmetric card XOR protocol with the minimum number of rounds)

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\oplus y)$.

1. 

Alice randomly selects bit b. If b=1, Alice turns $commit\left(x\right)$ and $commit\left(y\right)$ upside down, otherwise does nothing. Let the result be $S_1$ and $S_1^{\prime }$, respectively. Note that $S_1=commit\left(x^{\prime }\right)$ and $S_1^{\prime }=commit\left(y^{\prime }\right)$, where $x^{\prime }=x\oplus b$ and $y^{\prime }=y\oplus b$. Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private reveal on $S_1$ and obtains $x^{\prime }$. If $x^{\prime }=1$, Bob privately turns $S_1^{\prime }$ upside down and otherwise does nothing. Let the result be $S_2$. Bob outputs $S_2$.

The protocol is two rounds. The protocol uses two cards.

Protocol 20.

(asymmetric card AND protocol with the minimum number of rounds)

Input: $commit\left(x\right)$ and $commit\left(y\right)$.

Output: $commit(x\wedge y)$.

1. 

Alice executes a private random bisection cut on $commit\left(0\right)\left|\right|commit\left(y\right)$ using a random bit b. Let the result be $S_1^{\prime }$. If b=1, Alice turns $commit\left(x\right)$ upside down, and otherwise does nothing. Let the output be $S_1=commit\left(x^{\prime }\right)$. Note that $x^{\prime }=x\oplus b$. Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private reveal on $S_1$. Bob executes a private reverse selection on $S_1^{\prime }$, using $x^{\prime }$. Let the selected card be $S_2$. Bob outputs $S_2$ as the result.

The protocol is two rounds. The protocol uses three cards.

Protocol 21.

(asymmetric card copy protocol with the minimum number of rounds)

Input: $commit\left(x\right)$.

Output: m copies of $commit\left(x\right)$.

1. 

Alice randomly selects bit b. If b=1, Alice privately turns $commit\left(x\right)$ upside down, otherwise does nothing. Let the result be $S_1=commit\left(x^{\prime }\right)$. Note that $x^{\prime }=x\oplus b$. Alice privately sets $S_1^{\prime }$ as m copies of $commit\left(b\right)$. Alice sends $S_1$ and $S_1^{\prime }$ to Bob.

2. 

Bob executes a private reveal on $S_1$ and obtains $x^{\prime }$. Bob privately upside down all cards of $S_1^{\prime }$ if $x^{\prime }=1$, otherwise does nothing. Let the results be $S_2$. Bob outputs $S_2$.

The protocol is two rounds. The protocol uses $m+1$ cards.

Theorem 19.

Using asymmetric cards, XOR, AND, and a copy can be realized in two rounds.

Proof. 

The correctness and security proofs are the same as those for the two-color card protocols. □

8. Conclusions

This paper proposes round optimal card-based cryptographic protocols, using private operations. We showed protocols without private reveal operations and several variant protocols. This paper contributes the following new results, compared to the conference version: (1) new XOR and copy protocols without private reveals; (2) correctness and security proofs, given to all protocols; (3) parallel computation of the AND/XOR type protocols; and (4) protocols with asymmetric cards.

Further study will include round optimal protocols for the other fundamental problems.