Keywords

1 Introduction

Card-based cryptographic protocols [6, 13, 28] were proposed in which physical cards are used instead of computers to securely calculate values. They can be used when computers cannot be used or users cannot trust the software on the computer. Also, the protocols are easy to understand, thus the protocols can be used to teach the basics of cryptography [4, 19, 23]. den Boer [2] first showed a five-card protocol to securely calculate logical AND of two inputs. Since then, many protocols have been proposed to realize primitives to calculate any logical functions [1, 12, 14, 16, 29, 33, 39, 40, 48, 49] and specific computations such as a specific class of logical functions [7, 24, 26, 34, 37, 41, 44, 47, 53], millionaires’ problem [20, 32, 38], voting [25, 31, 35, 54], random permutation [8, 10, 11], grouping [9], matching [19], ranking [51], proof of knowledge of a puzzle solution [3, 5, 18, 21, 22, 42, 43, 45], and so on. This paper considers calculations of logical functions and a copy operation under the malicious model since any logical function can be realized with a combination of these calculations.

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. Private operations are shown to be the most powerful primitives in card-based cryptographic protocols. They were first introduced to solve millionaires’ problem [32]. Using three private operations shown later, committed-input and committed-output logical AND, logical XOR, and copy protocols can be achieved with the minimum number of cards [40]. Another class of private operations is private input operations that are used when a player inputs a private value [17, 38, 50]. These operations are not discussed in this paper since it is impossible to prevent false input from a malicious player. If the input values are honestly given, the players can use the protocols shown in this paper.

The biggest problem of protocols using private operations is malicious actions. Most of the card-based protocols assume the semi-honest model, in which the players obey the rule of the protocols but try to obtain private information. However, there are many cases when we must consider the malicious model. When we allow malicious actions, protocols using private operations are not secure. Since private operations are executed where the other player cannot see, any malicious operation is possible during the private operations, for example, watching the marks of face-down cards or changing the positions of cards.

One countermeasure to malicious actions is setting a watch person. When the protocols are executed by more than two players, it is possible to detect malicious actions by the following rule: whenever a player executes a private operation, another player watches the execution and reports incorrect behavior. The XOR, AND, and copy protocols can be executed securely against a malicious player when the protocols are executed by more than two players [40]. However, when the protocols are executed by two players, it is impossible to use the above method. If Bob watches Alice’s private operations, Bob knows all operations, thus the relation between input data and output data is known to Bob. When the output card is opened, the secure input data are known to Bob using the relation between the input data and the output data.

Thus we need new protocols for the two-player case. Since Bob cannot watch Alice’s private operations, some additional mechanism to prevent illegally watching the marks of face-down cards during private operations is necessary. This paper introduces envelopes to prevent illegally watching the marks of face-down cards. Cards that must not be seen are publicly put into an envelope. If the envelope is opened, it can be detected by anyone. Envelopes are used in [30] to realize cryptographic protocols that do not use physical cards. In card-based cryptographic protocols, envelopes are used in [8, 36, 44, 49] to realize some kind of shuffles that are not easy to execute by people.

This paper shows new card-based cryptographic protocols that are secure against malicious players using envelopes as an additional tool. The malicious actions during private operations are prevented by adding error-correction cards. We show logical XOR, logical AND, and copy protocols since any logical functions can be obtained with a combination of these protocols.

As related works, protocols that use additional cards and prevent active attacks while a player executes a shuffle were shown [15]. Another type of active attack is inputting a false value that is not 0 or 1. A protocol to detect such injection attacks was discussed in [27]. Protocols that prevent revealing face-down cards were discussed in [52]. The protocol uses the technique of secret-sharing to prevent information leakage by opening some numbers of cards. The protocol cannot be applied to the problem discussed in this paper since a malicious player might reveal all cards. Another usage of private operations is realizing a public shuffle by multiple private shuffles [29]. Using the method, logical XOR, logical AND, and copy can be executed since there are no malicious actions in these private shuffles. Though the protocols are very simple, the private primitives used in the protocols is private shuffles. Preventing malicious actions for the new protocols that use private random bisection cuts and private reveals are not considered.

A protocol to detect malicious actions by executing two instances of a protocol and comparing the results was shown [46]. The protocol uses cases to prevent revealing face-down cards. The functionality of cases is just the same as the one of envelopes in this paper. The protocol uses twice as many cards as the original protocols and it is impossible to correct the malicious actions. This paper’s protocols use fewer cards and can correct the result by malicious actions.

In Sect. 2, basic notations and the private operations introduced in [40] are shown. Section 3 shows XOR, AND, and copy protocols. Section 4 concludes the paper.

2 Preliminaries

2.1 Basic Notations

This section gives the notations and basic definitions of card-based protocols. This paper is based on a 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 is 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(x). It is written as . Note that when these two cards are swapped, \(commit(\bar{x})\) 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, \ldots , s_{n}\), where \(s_i\) is i-th card of the sequence. . A sequence whose length is even is called an even sequence. \(S_1 || S_2 \) is a concatenation of sequence \(S_1\) and \(S_2\).

All protocols are executed by two players, Alice and Bob. The players might be malicious, that is, they might not obey the rule of the protocols. There is no collusion between Alice and Bob, otherwise private input data can be easily revealed.

2.2 Private Operations

We show three private operations introduced in [40]: 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, \ldots , s_{2m}\). A player selects a random bit \(b\in \{0,1\}\) and outputs

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(x)\), given , the player’s output , which is or .

We sometimes write the result of the random bisection cut using bit b to a sequence \(S_1 ||S_2\)(where \(|S_1|=|S_2|\)) as \(swap(b, S_1||S_2)\). \(swap(0, S_1||S_2)=S_1 ||S_2 \) and \(swap(1, S_1||S_2)=S_2 ||S_1 \) are satisfied.

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, \ldots , s_{2m}\) and a bit \(b \in \{0,1\}\). A player outputs

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 Primitive 1, where a random bit must be newly selected by the player.

Note that in some 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, \ldots , s_{2m}\) and a bit \(b \in \{0,1\}\). A player outputs

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(x) and Bob executes a private reveal on the bit. Since the committed bit is randomized by the bit b selected by Alice, the opened bit is \(x \oplus b\). Even if Bob privately opens the cards, 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 Space and Time Complexities

The space complexity of card-based protocols is evaluated by the number of cards. Minimizing the number of cards is discussed in many works.

The number of rounds was proposed as a criterion to evaluate the time complexity of card-based protocols using private operations[39]. 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 whose result is unknown to the player himself 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 its space complexity and time complexity.

Protocol 1

(AND protocol in [40])

Input: commit(x) and commit(y).

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

  1. 1.

    Alice executes a private random bisection cut on commit(x). Let the output be \(commit(x')\). Alice hands \(commit(x')\) and commit(y) to Bob.

  2. 2.

    Bob executes a private reveal on \(commit(x')\). Bob sets

    and hands \(S_2\) to Alice.

  3. 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 correctness of the protocol is shown in [40]. The number of cards is four, since the cards of \(commit(x')\) is re-used to set commit(0).

The first round ends at the instant when Alice sends \(commit(x')\) and commit(y) 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 at 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 handing cards between players and setting 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.

2.4 Malicious Actions During Private Operations

We show examples of cheats by a malicious player for the AND protocol shown in Protocol 1. In the first round, Alice may open the cards of commit(x) and read the secret input value x. Alice might swap the two cards of commit(x) and use \(\bar{x}\) as the input value. In the second round, Bob might open the cards of commit(y). Bob might set the cards incorrectly, for example, set

then the result becomes \(x \vee y\) instead of \(x \wedge y\). Bob can set any other card sequences to obtain other incorrect results. In the third round, Alice might execute a private reverse selection using a value \(b'(\not =b)\). To make the protocol secure against malicious players, all of the above cheats must be prohibited or detected.

3 XOR, and and Copy Under Malicious Model

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

3.1 Additional Assumptions for Preventing Malicious Actions

Throughout this paper, we assume that each input is given as a committed value. The output must also be given as a committed value so that the output can be used as an input to further computations. Though some multi-party secure calculation protocols assume that each player knows his/her private input, there are some cases when we cannot assume that. For example, suppose that \(x_1,x_2\) are Alice’s private input values and \(y_1, y_2\) are Bob’s private input values and they want to securely calculate \((x_1 \vee y_1) \wedge (x_2 \vee y_2)\). After \(commit(x_1 \vee y_1)\) and \(commit(x_2 \vee y_2)\) are calculated, they need to calculate logical AND of two secret values. Thus, we need to calculate the logical functions of two committed inputs. If Alice knows an input value, she first commits her input and a committed input protocol can be used.

We add an assumption that for at least one input, say, x multiple copies of commit(x) are given as input. The reason for this assumption is as follows. When a player, say, Alice is given commit(x) and executes a private operation, there is no way for the other player to detect whether Alice maliciously executed swapping two cards of commit(x) and made \(commit(\bar{x})\). Since Bob does not know x, Bob cannot claim that \(\bar{x}\) is used instead of x. To detect this type of malicious operation, another copy of commit(x) must be given. Using the copy of commit(x), Bob can detect that Alice used \(commit(\bar{x})\) instead of commit(x), as shown in the protocols in this paper. Note that a method to obtain multiple copies of inputs using envelopes is shown in Sect. 3.4.

Next, we need to prevent malicious reveal of committed input values. In the following protocols, we use envelopes as an additional tool. The cards can be put into an envelope and sealed. Opening the envelope can be easily detected by anyone. Thus a malicious player cannot irregularly open envelopes during private operations because it is detected by the other player. It is impossible to distinguish two envelopes. No player can prepare the same envelopes in his/her pocket and exchange them for the envelopes used in the protocol. Such envelopes are used in some card-based protocols [8, 36, 44, 49].

We show some basic operations and notations related to the envelopes. The order of the cards put into an envelope is preserved when the cards are removed. For example, a card sequence S is put into an envelope, the output card sequence from the envelope must also be S. In the following protocols, two envelopes, the left and the right envelope are used and the following two types of insertions are applied. The first one is putting each card of commitments to the left and right envelope. For example, put the left cards of commit(x) and commit(y) into the left envelope and put the right cards of commit(x) and commit(y) into the right envelope. When the players remove the cards from the envelopes, commit(x) and commit(y) are obtained. We write the state of the two envelopes as [commit(x), commit(y)]. When we swap the left and right envelopes, the output cards become \(commit(\bar{x})\) and \(commit(\bar{y})\). Thus we write the state of the swapped envelopes as \([commit(\bar{x}), commit(\bar{y})]\).

The second one is putting the left card of commit(x) and the two cards of commit(y) to the left envelope, and putting the right card of commit(x) and the two cards of commit(z) to the right envelope. We write the state of the two envelopes as [commit(x), commit(y) ||commit(z)]. When we swap the two envelopes, we can obtain \([commit(\bar{x}), commit(z) || commit(y)]\).

In this paper, private random bisection cuts are executed to these two envelopes. When Alice executes a private random bisection cut to the two envelopes that have [commit(x), commit(y)], \([commit(x \oplus b), commit(y \oplus b)]\) is obtained. When Alice executes a private random bisection cut to the two envelopes that have [commit(x), commit(y) ||commit(z)],

\([commit(x \oplus b), swap(b, commit(y) || commit(z))]\) is obtained.

With the envelopes, the activities by a malicious player are as follows when the private primitives are private random bisection cuts, private reverse cuts, and private reveals on the envelopes.

Assumption 1

(Operations by malicious players)

  • When a malicious player executes a private operation, he/she can swap some envelopes even if it is not allowed in the protocol.

  • When a malicious player executes a private random bisection cut to two sets of envelopes A and B using the same random bit, he/she can use different bits to A and B.

  • When a malicious player executes a private reveal on envelope A, he/she can open another envelope B if it cannot be detected by the other player (for example, the number of cards in A and B are the same). Also, he/she might not place envelopes according to the opened cards.

  • When a malicious player executes a private reverse cut using bit b, he/she might use \(\bar{b}\) instead of b.

3.2 XOR Protocol

Protocol 2

(XOR protocol)

Input: two copies of commit(x) and one copy of commit(y).

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

  1. 1.

    Alice and Bob publicly put cards of one commit(x) and commit(y) into two envelopes. The left(right) cards of commit(x) and commit(y) are put into the left(right) envelope. The two envelopes have [commit(x), commit(y)]. The remaining two cards of commit(x) are put into two new envelopes so that the left(right) card is put into the left(right) envelope. The two envelopes have [commit(x)].

    The envelopes that have [commit(x)] and [commit(x), commit(y)] are handed to Alice.

  2. 2.

    Alice executes a private random bisection cut on [commit(x)] and

    [commit(x), commit(y)] using the same random bit b. Let the output be \([S_1]\) and \([S_1', S_1'']\). \(S_1=commit(x \oplus b)\), \(S_1'=commit(x \oplus b)\), and \(S_1''=commit(y \oplus b)\). Alice hands \([S_1]\) and \([S_1', S_1'']\) to Bob.

  3. 3.

    Bob first verifies that the envelopes are not opened. Then, Bob executes a private reveal on \([S_1=commit(x')]\). Bob verifies that the numbers of cards in the envelopes are 1, otherwise Alice incorrectly handed envelopes. Bob privately swaps the two envelopes of \([S_1', S_1'']\) if \(x'=1\), otherwise, does nothing. Bob makes the two envelopes public, which are denoted \([S_2', S_2'']\).

  4. 4.

    Alice verifies that the envelopes are not opened. Alice and Bob open the envelopes together and obtain \(S_2'\) and \(S_2''\). They turns (that is, face-up) \(S_2'\). If \(S_2'=0\), \(S_2''\) is the output of the protocol. If \(S_2'=1\), swap the two cards of \(S_2''\) and the result is the output of the protocol.

The protocol is three rounds. The first round is the public execution by Alice and Bob. The second round is executed by Alice. The third round is executed by Bob. The last execution by Alice and Bob does not need handing cards or envelopes. Bob just makes the envelopes public and Bob can execute the operations in front of Alice. Thus no overhead is necessary for the public execution. Therefore, the number of rounds is considered to be three. The number of cards used in the protocol is six.

Theorem 1

The output of the XOR protocol is correct even if Alice or Bob is malicious. The protocol does not reveal the input values to the players if no prohibited opening is executed.

Proof

First, we show the correctness when both Alice and Bob are honest.

Alice hands \([S_1]=[commit(x \oplus b)] \) and \([S_1', S_1'']=[commit(x \oplus b), commit(y \oplus b)]\) to Bob. Bob swaps the pair of \([S_1', S_1'']\) if \(x \oplus b=1\). Thus \([S_2', S_2'']=[commit((x \oplus b) \oplus (x \oplus b)), commit((y \oplus b) \oplus (x \oplus b))]=[commit(0), commit(x \oplus y)]\). Since \(S_2'=commit(0)\), \(S_2''\) is not swapped and the output is \(commit(x \oplus y)\). Therefore, the output is correct. The protocol is secure since Alice sees \(S_2'=0\) and Bob sees \(S_2'=0\) and \(S_1=x \oplus b\) but b is an unknown random value for Bob.

Next, consider the case when Alice is malicious and Bob is honest. If Alice opens an envelope during the private operation, Bob can detect the misbehavior. Next, consider the case when Alice does not execute the private random bisection cut correctly. Since the numbers of cards in \([S_1]\) and \([S_1', S_1'']\) differs, the only cheat that cannot be detected by Bob is incorrectly swapping envelopes. Let b and \(b'\) be the random bits selected to swap the envelopes that have [commit(x)] and [commit(x), commit(y)], respectively. The output by Alice is \([S_1]=[commit(x \oplus b)]\) and \([S_1', S_1'']=[commit(x \oplus b'), commit(y \oplus b')]\). After Bob opens \([S_1]=[commit(x \oplus b)]\), Bob swaps the envelopes if \(x \oplus b=1\), thus the result \([S_2', S_2''] =[commit(x \oplus b' \oplus x \oplus b), commit(y \oplus b' \oplus x \oplus b)]= [commit(b \oplus b'), commit(y \oplus b' \oplus x \oplus b)]\). When the players open \(S_2'\), they obtain no information about x since \(S_2'=commit(b \oplus b')\). In addition, if \(b \oplus b'=1\), the cards of \(S_2''\) are swapped, thus the output is \(commit( y \oplus b' \oplus x \oplus b \oplus (b \oplus b'))=commit(y \oplus x)\). The result is correct regardless of the selection of b and \(b'\).

Next, consider the case Bob is also malicious. When Bob opens the envelopes of \([S_1', S_1'']\), the cheat can be detected by Alice. Next, consider the case when Bob does not set the envelopes correctly. When Bob sees \(x \oplus b\), Bob does not swap the envelopes correctly, that is, Bob selects some value \(b''(\not = x \oplus b) \in \{0,1\}\) and swaps the envelopes of \([S_1', S_1'']\) using \(b''\). If \(b''=x \oplus b\), the result is correct as shown above. Thus the only cheat selection of \(b''\) is \(b''=\overline{x \oplus b}=x \oplus b \oplus 1\).

In this case, the result is \([S_2', S_2''] =[commit(x \oplus b' \oplus b''), commit(y \oplus b' \oplus b'')] =[commit(b' \oplus b \oplus 1), commit(y \oplus b' \oplus x \oplus b \oplus 1)]\). When Alice and Bob open \(S_2'\), they do not obtain information about x since the value is independent of x. If \(b' \oplus b \oplus 1=1\), the two envelopes of \(S_2''\) is swapped. The result is correct since the output is \(commit(y \oplus b' \oplus x \oplus b \oplus 1 \oplus (b' \oplus b \oplus 1))=commit(y \oplus x)\).    \(\square \)

Note that the protocol achieves an error-correction. Even if Alice and/or Bob make mistakes in swapping envelopes, the mistakes are automatically corrected as shown above.

3.3 And Protocol

Protocol 3

(AND protocol)

Input: two copies of commit(x) and one copy of commit(y).

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

  1. 1.

    Alice and Bob publicly put cards into two envelopes. The left card of commit(x) and two new cards of commit(0) are put into the left envelope. The right card of commit(x) and the two cards of commit(y) are put into the right envelope. The envelopes have [commit(x), commit(0)||commit(y)]. The remaining two cards of commit(x) are put into two envelopes so that the left(right) card is put into the left(right) envelope. The envelopes have [commit(x)].

    The envelopes that have [commit(x)] and [commit(x), commit(0)||commit(y)] are handed to Alice.

  2. 2.

    Alice executes a private random bisection cut on [commit(x)] and

    [commit(x), commit(0)||commit(y)] using the same random bit b. Let the output be \([S_1]\) and \([S_1', S_1'']\). \(S_1=commit(x')\), where \(x'=x \oplus b\). \(S_1'=commit(x')\) and \(S_1''=swap(b, commit(0)|| commit(y))\). Alice hands \([S_1]\) and \([S_1', S_1'']\) to Bob.

  3. 3.

    Bob first verifies that the envelopes are not opened. Bob executes a private reveal on \([S_1=commit(x')]\). Bob verifies that the numbers of cards in the envelopes are 1, otherwise Alice incorrectly handed the envelopes. Bob privately swaps two envelopes of \([S_1', S_1'']\) if \(x'=1\), otherwise, does nothing. Bob makes the two envelopes public, which are denoted \([S_2', S_2'']\).

  4. 4.

    Alice verifies that the envelopes that have \([S_2', S_2'']\) are not opened. Alice and Bob open the envelopes together and obtains \(S_2'\) and \(S_2''\). They turn (that is, face-up) \(S_2'\). If \(S_2'=0\), the left two cards of \(S_2''\) is the output of the protocol. If \(S_2'=1\), the right two cards of \(S_2''\) is the output of the protocol.

The protocol is three rounds. The protocol uses eight cards since two new cards are used to set commit(0).

Theorem 2

The output of the AND protocol is correct even if Alice or Bob is malicious. The protocol does not reveal the input values to the players if no prohibited opening is executed.

Proof

The desired output can be represented as follows.

First, we show the correctness when both Alice and Bob are honest.

Alice hands \([S_1]=[commit(x \oplus b)]\) and \([S_1',S_1'']=[commit(x \oplus b),\)

swap(b, commit(0)||commit(y))] to Bob. Bob swaps the pair of \([S_1', S_1'']\) if \(x \oplus b=1\). Thus \([S_2', S_2'']=[commit((x \oplus b) \oplus (x \oplus b)), swap(x \oplus b, swap(b, commit(0)||\)

\( commit(y))]=[commit(0), swap(x, commit(0)|| commit(y))]\). Thus the players select the left two cards of swap(x, commit(0)||commit(y)). The selected cards are commit(y) if \(x=1\) and commit(0) if \(x=0\). Thus, the output is correct.

The protocol is secure since Alice sees \(S_2'=0\) and Bob sees \(S_2'=0\) and \(S_1=x \oplus b\) but b is an unknown random value for Bob.

Next, consider the case when Alice is malicious and Bob is honest. If Alice opens an envelope during the private operation, Bob can detect the misbehavior. Next, consider the case when Alice does not execute the private random bisection cut correctly. Since the numbers of cards in the envelopes for \([S_1]\) and \([S_1', S_1'']\) differs, the only cheat that cannot be detected by Bob is incorrectly swapping envelopes. Let b and \(b'\) be the random bits selected to swap the envelopes that have [commit(x)] and [commit(x), commit(0)||commit(y)], respectively. The output by Alice is \([commit(x \oplus b)]\) and \([commit(x \oplus b'), swap(b', commit(0)|| commit(y))]\). After Bob opens \([commit(x \oplus b)]\), Bob swaps the envelopes if \(x \oplus b=1\), thus the result \([S_2', S_2''] =[commit(x \oplus b' \oplus x \oplus b), swap(x \oplus b, swap(b', commit(0)||commit(y)))]= [commit(b \oplus b'), swap(x \oplus b \oplus b', commit(0)|| commit(y))]\). When the players open \(S_2'\), they obtain no information about x since \(S_2'=commit(b \oplus b')\). In addition, if \(b \not =b'\), the right two cards of \(S_2''\) are used as the output otherwise, the left two cards of \(S_2''\) are used as the output. This is equivalent to execute \(swap(b \oplus b', S_2'')\) and select the left two cards. Since \(swap( b \oplus b', S_2'')=swap(b \oplus b', swap(x \oplus b \oplus b', commit(0)|| commit(y)))= swap(x, commit(0)|| commit(y))\), the output is commit(0) if \(x=0\), otherwise the output is commit(y). Therefore, the output is correct regardless of the selection of b and \(b'\).

Next, consider the case Bob is also malicious. When Bob opens the envelopes of \([S_1', S_1'']\), the cheat can be detected by Alice. Next, consider the case when Bob does not set the envelopes correctly. When Bob sees \(x \oplus b\), Bob does not swap the envelopes correctly, that is, Bob selects some value \(b''(\not = x \oplus b) \in \{0,1\}\) and swaps the envelopes of \([S_1', S_1'']\) using \(b''\). When \(b''=x \oplus b\), the output is correct since it is the correct value. Thus the only cheat selection of \(b''\) is \(b''=\overline{x \oplus b}=x \oplus b \oplus 1\).

In this case, the result is \([S_2', S_2''] =[commit(x \oplus b' \oplus b''), swap(b'', swap(b,\)

\( commit(0)|| commit(y)))]=[ commit(b \oplus b' \oplus 1), swap(x \oplus b \oplus b' \oplus 1, commit(0)|| \)

commit(y))]. When Alice and Bob open \(S_2'\), they do not obtain information about x since the value is independent of x.

In addition, if \(b \oplus b' \oplus 1=1\), the right two cards of \(S_2''\) are used as the output otherwise, the left two cards of \(S_2''\) are used as the output. This is equivalent to execute \(swap(b \oplus b' \oplus 1, S_2'')\) and select the left two cards. Since \(swap(b \oplus b' \oplus 1, S_2'')= swap(b \oplus b' \oplus 1, swap (x \oplus b \oplus b' \oplus 1, commit(0)|| commit(y)))= swap(x, commit(0)|| commit(y))\), the output is commit(0) if \(x=0\), otherwise the output is commit(y). Therefore, the output is correct regardless of the selection of b and \(b'\).    \(\square \)

Note that even if Alice and/or Bob make mistakes in swapping envelopes, the mistakes are automatically corrected as shown above.

3.4 COPY Protocol

Next, we show a copy protocol. Multiple copies of output data of computation might be needed in some cases, for example, use the output result to a further computation. A method to obtain \(m(>1)\) copies of the output is preparing m copies of commit(y).

In the XOR protocol, at the first step of the protocol, they put cards into two envelopes so that \([commit(x), commit(y), commit(y), \ldots , commit(y)]\) is obtained. At the last step, \(S_2''\) is m pairs of cards. When they need to swap the cards, each pair of \(S_2''\) is swapped. Then we can obtain m copies of \(commit(x \oplus y)\).

In the AND protocol, at the first step of the protocol, they put cards into two envelopes so that \([commit(x), (commit(0), \ldots , commit(0))|| (commit(y), \ldots , \)

commit(y))] is obtained, that is, put m copies of commit(0)(commit(y)) to the left(right) envelope. At the last step, if \(S_2'=0\), the output is the left m pairs of cards. Otherwise, the output is the right m pairs of cards.

We can obtain another protocol that directly increases the number of copies of input data using the XOR protocol. Two copies of commit(x) are given as input. Execute the XOR protocol with two copies of commit(x) and m copies of commit(0). Then the players obtain m copies of commit(x) as the output since \(x \oplus 0=x\).

Last, we show a method to obtain multiple copies of input x using two envelopes. For any number n, cards are publicly put into the left(right) envelope and the envelopes are sealed. The two envelopes are given to the input player. The input player privately sets the two envelopes according to the private input value x. Then all players publicly open the seals of the envelopes and two piles of cards are obtained. When the players select one card from each of the piles, a copy of commit(x) can be obtained, thus n copies of commit(x) can be obtained.

When we calculate general logical functions using the above primitives, we need to prepare two copies of each input. Any number of copies of a value can be obtained by using the copy protocol at any time, if there are two copies of the value. Obtaining two copies of an output value can be realized by the above protocols, thus any logical functions can be calculated securely using these protocols.

4 Conclusion

This paper proposed new protocols using private operations that are secure against malicious players. We show logical XOR, logical AND, and copy protocols that use envelopes for an additional tool. Since the envelopes are a very powerful tool to restrict shuffle executions, malicious executions are corrected in the protocols.

We can consider weak tools for preventing illegal opening face-down cards, for example, seals on the marks of the cards. They cannot restrict shuffle executions. One of the open problems is considering secure protocols with such tools.