Public-PEZ Cryptography

Abstract

Secure multiparty computation (MPC) is a cryptographic technique that enables us to evaluate a predetermined function over players’ private inputs while hiding information about the inputs. MPC can be conducted using a “private PEZ protocol,” that uses PEZ candies and a dispenser. Specifically, in a private PEZ protocol, players first fill a predetermined sequence of candies in a dispenser. Then, each player in turn privately pops out a number of candies, wherein the number depends on their private input (without anybody else knowing how many candies pop out). The next candy to be popped out of the dispenser indicates the output value of the function. Thus, private PEZ protocols are fun and useful. One drawback would be that every player must pop out candies from the dispenser secretly, implying that a private PEZ protocol is vulnerable to dishonest players, for example, a player could peep the candies inside the dispenser. To overcome this drawback, we herein propose MPC protocols that do not need private actions such as secretly popping out candies after the setup (although each player rearranges the candies secretly in a setup phase, any illegal actions can be caught). That is, we construct a computational model of “public-PEZ cryptography,” where any protocol within the model can be publicly executed. Especially, the proposed public-PEZ AND protocol, which uses only five candies and two dispensers, is simple and easy for conducting a secure computation of the AND function.

1 Introduction

1.1 Background

Secure multiparty computation (MPC) is a cryptographic technique for evaluating a predetermined function over players’ private inputs while hiding information about the inputs. Interestingly, MPC can be performed using not only computers but also everyday objects. Some examples are private PEZ protocols using PEZ candies and a dispenser (as shown in Fig. 1) and card-based protocols using a deck of physical cards (as shown in Fig. 2). Using such physical cryptographic protocols, we can visually understand what MPC is and how secure the protocols are. Thus, they attract not only cryptographers but also non-experts, such as high school students, and they can be effectively used as educational tools.

Fig. 1.

PEZ candies, packages, and a dispenser.

Fig. 2.

A deck of cards.

Private PEZ protocols were first introduced in 2003 by Balogh et al.  [2], and their results were improved recently by Abe et al.  [1] in 2019. In a private PEZ protocol, players first fill in a dispenser with a predetermined sequence of candies whose order depends on the function that they want to securely compute. Subsequently, each player privately pops out a number of candies such that the number depends on their private input. Finally, the remaining topmost candy left in the dispenser becomes the output of the function. Thus, private PEZ protocols are fun and useful. One drawback is that every player must take out candies from the dispenser secretly, implying that a private PEZ protocol is vulnerable to dishonest players. For example, when a player pops out candies secretly, they could maliciously peep the candies inside the dispenser or replace them with another sequence of candies as per their preference.

1.2 Contributions

In this paper, to overcome the drawback of the above-mentioned private PEZ protocols, which require players’ private actions, we consider a new usage of PEZ candies and dispensers by borrowing the ideas behind card-based protocols. That is, we design novel PEZ protocols that can be publicly executed. Specifically, we first propose a secure AND protocol using five PEZ candies and two dispensers; it allows Alice and Bob to compute the AND value of their private inputs without revealing them. Carrying the idea behind this protocol further, we construct a computational model of public-PEZ cryptography. Following this model, we present the formal description of our AND protocol. We also discuss some implementation issues.

1.3 Related Work

As mentioned above, we borrow the ideas and techniques from card-based protocols. The first card-based protocol was proposed by den Boer  [3] in 1989; his famous protocol called the “five-card trick” performs a secure computation of the AND function. Our constructions are inspired by the card-based AND protocols  [16, 21] that use a shuffling operation called a “random bisection cut.” In card-based protocols, all players first place a pair of cards face-down on a table whose order depends on their private input. Subsequently, they perform MPC by publicly shuffling and turning over the sequence of cards to obtain the output. A formal computational model of card-based protocols was presented (and was then reviewed) in the literature  [11, 19, 20, 31]. Based on the computational model, Koch et al.  [11], Francis et al.  [7], Kastner et al.  [9], and Koch et al.  [10] provided tight lower bounds on the number of required cards. In addition to simple MPCs, there are card-based protocols for zero-knowledge proof  [4, 6, 12, 15, 28, 29] and secure comparison  [13, 14, 30]. Furthermore, there is another direction of card-based cryptography that relies on private actions  [24,25,26,27, 33]. Protocols using other everyday objects have been proposed, such as those using a dial lock  [17], the 15-puzzle  [18], envelopes  [8], tamper-evident seals  [23], and a visual secret sharing scheme  [5].

1.4 Outline

The remainder of this paper is organized as follows. In Sect. 2, we present a simple and easy-to-implement AND protocol using five PEZ candies and two dispensers. In Sect. 3, we define each operation appearing in public-PEZ protocols and obtain a computational model. In Sect. 4, we formally describe the AND protocol introduced in Sect. 2 based on the model shown in Sect. 3. In Sect. 5, we discuss the feasibility of implementing the shuffling operations of public-PEZ protocols. The concluding statements are presented in Sect. 6.

2 Public-PEZ AND Protocol

In this section, we present a simple and easy-to-implement AND protocol using five PEZ candies and two dispensers.

Assume that Alice and Bob hold private input bits $a\in \{0,1\}$ and $b\in \{0,1\}$, respectively. They want to learn $a\wedge b$, namely the AND value of their inputs, without revealing the input values more than necessary. They only require two packages of PEZ candies (of different flavors) and two identical dispensers¹. We assume that all candies are indistinguishable in terms of appearance, i.e., they have the same color and shape; the PEZ candies sold in Japan satisfy this condition, i.e., the lemon and orange candies appear identical, as shown in Fig. 3. We also assume that one cannot distinguish two candies of different flavors by their smells².

Fig. 3.

The PEZ candies sold in Japan; the lemon and orange candies are all white and indistinguishable.

Fig. 4.

How to prepare two candies of different flavors on Alice’s palm.

Let us consider how a Boolean value can be encoded by a flavor of the candy: Let the lemon flavor be denoted by 0, and let the orange flavor be denoted by 1. As shown in Fig. 3, candies with the same flavor are packed in the same package. Let Alice take a lemon candy and an orange candy from the packages publicly and place the two candies with different flavors on her palm, as shown in Fig. 4. Next, let Alice arrange the two candies inside her hand (without Bob knowing their order), as shown in Fig. 5, according to her input bit $a\in \{0,1\}$, as follows. If $a=0$, she rearranges the two candies in the order of lemon, and then, orange, i.e., 0 to 1; otherwise, in the order of orange to lemon, i.e., 1 to 0. Subsequently, she takes the two candies from her palm and places them on the table so that the order satisfies

as shown in Fig. 6. In this manner, Alice can prepare two candies (of different flavors) corresponding to her private bit $a\in \{0,1\}$ and its negation $\overline{a}$ without Bob knowing its value. Note that Alice and Bob face each other, and Bob watches Alice’s behavior during the entire process. Therefore, Alice has no choice but to place two candies of different flavors on the table; if Alice acts maliciously, such an illegal action will be always identified.

Fig. 5.

Rearrange the two candies in Alice’s hand without Bob knowing its order.

Fig. 6.

Place the candies (whose order matches Alice’s private bit) on the table without Bob knowing the order.

We are now ready to present our protocol; it is based on the idea behind the card-based AND protocol proposed in  [16]. Our protocol proceeds as follows.

• 1. As described above, Alice prepares two candies corresponding to a and $\overline{a}$. Similarly, Bob prepares two candies that correspond to b and $\overline{b}$. A sequence of candies is arranged on a table as follows:

  

  Remember that the candies are indistinguishable from each other; for example, Alice does not know how the third candy tastes (unless she bites it to confirm its flavor).

• 2. Alice replaces the candy corresponding to $\overline{a}$ with a candy corresponding to 0, i.e., she discards (or eats) the candy corresponding to $\overline{a}$ and places a candy there corresponding to 0, which is taken from the lemon package:

  

• 3. Alice and Bob fill the four candies into two identical dispensers as follows.

  

• 4. Shuffle the two dispensers. The resulting state can be described as follows.

  

  Here, $r\in \{0,1\}$ is a uniformly distributed random bit, and $\alpha$ and $\beta$ are defined as follows: if $r=0$, $(\alpha ,\beta )=(a,0)$; if $r=1$, $(\alpha ,\beta )=(0,a)$. That is, $r=0$ indicates that the shuffle has not swapped the two dispensers, and $r=1$ means that the shuffle has swapped them. Moreover, if $b \oplus r=0$, we have $a\wedge b=a\wedge r=\beta$ because $a \wedge 0=0$ and $a \wedge 1=a$; if $b \oplus r=1$, we have $a\wedge b= a\wedge \overline{r}=\alpha$ because $a \wedge \overline{0}=a$ and $a \wedge \overline{1}=0$.

• 5. Pop out the candy from each dispenser and then bite them³. If the candy $b\oplus r$ popped out of the top dispenser corresponds to 0, the candy remaining in the bottom dispenser $\beta$ represents the output $a \wedge b$; if $b \oplus r$ corresponds to 1, the candy remaining in the top dispenser $\alpha$ represents the output $a\wedge b$.

This is our AND protocol, using five candies and two dispensers along with one shuffle. Note that the shuffle and popping out candies can be done publicly. It should be also noted that in Step 1, hidden operations shown in Fig. 5 are required to prepare players’ private inputs; this is inevitable for MPC and, as mentioned before, both players cannot place any pair of candies that deviates from the encoding rule.

After Step 5, the players obtain a candy corresponding to $a\wedge b$:

If they bite it, they can know the value of $a\wedge b$. Instead, this candy can be used as an input to another computation: that is, if Carol prepares two candies according to her private bit $c\in \{0,1\}$, starting the AND protocol again with

generates a candy corresponding to $a\wedge b \wedge c$:

Thus, a secure AND computation of more than two inputs can be easily performed.

3 Formalizing Public-PEZ Protocols

In this section, by elaborating the idea behind our AND protocol shown in Sect. 2, we formally define each operation on PEZ candies and dispensers and provide a computational model of public-PEZ protocols that publicly perform MPC using PEZ candies and dispensers. We borrow the ideas and terms from the computational model of card-based protocols  [19].

3.1 Sequence of Candies

There are various flavors of PEZ candies, such as lemon and orange; however, as assumed before, all candies have the same appearance so that they are indistinguishable (unless they are eaten). Considering all available candies, we denote the multiset of them by $\mathcal {B}$, which we call a box. Any element $c\in \mathcal {B}$ represents a flavor, such as $c\in [\texttt {lemon},\texttt {lemon},\texttt {orange},\texttt {orange},\texttt {grape},\cdots ]$. For simplicity, hereinafter, we consider only two flavors and denote them by 0 or 1. Therefore, for instance, the AND protocol presented in Sect. 2 works on the box

$$ \mathcal {B}=[\,0,0,0,1,1\,]=[\,3\cdot 0,2\cdot 1\,] $$

because it uses three lemon candies and two orange candies. Generally, if a protocol requires k candies corresponding to 0 and $\ell$ candies corresponding to 1, the box is expressed as

$$ \mathcal {B}=[ \, k\cdot 0,\ell \cdot 1 \, ]. $$

Next, we consider a “sequence” of candies. When a player takes a candy from a package, its flavor is publicly known. For instance, if there are three lemon candies and two orange candies taken from the packages, the order of which is

we write this sequence as (0, 1, 0, 1, 0). Given such a sequence (0, 1, 0, 1, 0), let both Alice and Bob (holding input bits a and b, respectively) rearrange two candies inside their hand as in the AND protocol, shown in Sect. 2; then, we have

where the flavors of the left-most four candies become publicly unknown. If the flavor of candy $c\in \mathcal {B}$ is unknown to the public, we denote it by $\frac{?}{c}$. Therefore, for example, when $a=1$ and $b=0$, the sequence above can be written as

$$ \left( \frac{?}{1},\frac{?}{0},\frac{?}{0},\frac{?}{1},0 \right) . $$

Now, consider a situation where players eat the first candy; then, the flavor, 1, becomes public while the candy has disappeared. We use expression $\frac{c}{\epsilon }$ with $c\in \mathcal {B}$ to represent a candy whose flavor is known to the public, but the candy itself does not exist. Therefore, the resulting sequence (from eating the left-most candy) can be written as

$$ \left( \frac{1}{\epsilon },\frac{?}{0},\frac{?}{0},\frac{?}{1},0\right) . $$

For $c\in \mathcal {B}$, we define $\mathsf{{atom}}(c)=\mathsf{{atom}}(\frac{?}{c})=\mathsf{{atom}}(\frac{c}{\epsilon })=c$. For example, $\mathsf{{atom}}(1)=1$, $\mathsf{{atom}}(\frac{?}{0})=0$, and $\mathsf{{atom}}(\frac{1}{\epsilon })=1$. For the box $\mathcal {B}$ with $|\mathcal {B}|=m$, we call $\varGamma =(\alpha _{1},\alpha _{2},\ldots ,\alpha _{m})$ a sequence from the box $\mathcal {B}$ if $\alpha _{i} \in \{0,1,\frac{?}{0},\frac{?}{1},\frac{0}{\epsilon },\frac{1}{\epsilon }\}$ for every i, $1\le i \le m$, and $[\mathsf{{atom}}(\alpha _{1}),\mathsf{{atom}}(\alpha _{2}),\ldots ,\mathsf{{atom}}(\alpha _{m})]=\mathcal {B}$.

We define the set of all sequences from $\mathcal {B}$ as $\mathsf{{Seq}}^{\mathcal {B}}$:

$$ \mathsf{{Seq}}^{\mathcal {B}}=\{\varGamma \, |\, \varGamma \, \mathrm {is \,\, a \,\, sequence\,\, from \,\, \mathcal {B}}\}. $$

3.2 Action

Next, we define four actions appearing in public-PEZ protocols. Assume that we have a sequence $\varGamma =(\alpha _{1},\alpha _{2},\ldots ,\alpha _{m})$.

Suppose that players want to check the flavors of some candies $\frac{?}{c}$. In this case, the players must bite them to determine their flavor, and the eaten candies will disappear. We denote this action by $(\mathsf{{bite}}, T)$ for a set $T\subseteq \{1,2,\ldots ,m\}$ such that $\alpha _{i}=\frac{?}{0}$ or $\frac{?}{1}$ for every $i\in T$, where every candy in T is eaten and disappears. That is, the resulting sequence becomes $(\beta _{1},\beta _{2},\ldots ,\beta _{m})$ such that

$$\begin{aligned} \beta _{i}= {\left\{ \begin{array}{ll} \, \frac{\mathsf{{atom}}(\alpha _{i})}{\epsilon } &{} \mathrm {if}\,\, i \in T\\ \, \alpha _{i} &{} \mathrm {otherwise} \end{array}\right. } \end{aligned}$$

for every i, $1\le i\le m$. For instance, for a sequence $(\frac{?}{1},\frac{?}{0},\frac{?}{1},\frac{?}{1},\frac{?}{0})$, applying $(\mathsf{{bite}},T)$ with a set $T=\{1,3,5\}$ results in $(\frac{1}{\epsilon },\frac{?}{0},\frac{1}{\epsilon },\frac{?}{1},\frac{0}{\epsilon })$.

Suppose that players want to rearrange the order of sequence $\varGamma$. We denote this action by $(\mathsf{{permute}}, \pi )$ for a permutation $\pi \in S_{m}$, where $S_{m}$ is the symmetric group of degree m. That is, the resulting sequence becomes $(\alpha _{{\pi ^{-1}}(1)},\alpha _{{\pi ^{-1}}(2)},\ldots ,\alpha _{{\pi ^{-1}}(m)})$.

Suppose that players want to perform a shuffling action such as shuffling the two dispensers, seen in Sect. 2. We denote this type of action by $(\mathsf{{shuffle}}, \Pi , \mathcal {F})$ for a subset $\Pi \subseteq S_{m}$ and a probability distribution $\mathcal {F}$ on $\Pi$. That is, defining $\mathsf{{fixed}}(\Pi )=\{j \mid 1 \le j \le m, \, \forall \sigma \in \Pi \, \,\sigma (j)=j\}$, the resulting sequence becomes $(\beta _{1},\beta _{2},\ldots ,\beta _{m})$ such that

$$\begin{aligned} \beta _{i}= {\left\{ \begin{array}{ll} \, \alpha _{i} &{} \mathrm {if}\,\, i \in \mathsf{{fixed}}(\Pi )\\ \, \frac{?}{\mathsf{{atom}}(\alpha _{{\pi ^{-1}}(i)})} &{} \mathrm {if}\,\, i \notin \mathsf{{fixed}}(\Pi ) \end{array}\right. } \end{aligned}$$

for every i, $1\le i\le m$, where $\pi$ is drawn from $\Pi$ according to $\mathcal {F}$. When $\mathcal {F}$ is uniform, we write $(\mathsf{{shuffle}}, \Pi )$ by omitting it. Note that when an action $(\mathsf{{shuffle}}, \Pi , \mathcal {F})$ is applied to a sequence $(\alpha _{1},\alpha _{2},\ldots ,\alpha _{m})$, it should hold that $i\in \mathsf{{fixed}}(\Pi )$ for every i such that $\alpha _{i}=\frac{c}{\epsilon }$ for some c.

Herein, we introduce two shuffles that are also often used in card-based protocols. The first one is a “random cut” that shuffles a sequence cyclically. For instance, if a random cut is applied to a sequence of four candies, one of the following sequences is obtained. The probability of each occurrence is 1/4.

This shuffle is formally expressed as $(\mathsf{{shuffle}}, \{\mathsf{{id}}, (1\,2\,3\,4), {(1\,2\,3\,4)}^{2}, {(1\,2\,3\,4)}^{3}\})$ where $\mathsf{{id}}$ is the identity permutation. The second one is a “random bisection cut,” which was implicitly seen in Sect. 2. Here, a sequence of candies is divided in half and the two sub-sequences are shuffled. For instance, applying a random bisection cut to a sequence of four candies results in

where each result occurs with a probability of 1/2. This shuffle is formally expressed as $(\mathsf{{shuffle}}, \{\mathsf{{id}}, (1\,3)(2\,4)\})$.

Finally, we define an action used at the end of a protocol. We use $(\mathsf{{result}}, p)$ for $p\in \{1,2,\cdots ,m\}$ to represent that the protocol is terminated and its output is the p-th candy.

3.3 Computational Model of Public-PEZ Protocols

In this subsection, we define a computational model of public-PEZ protocols via an abstract machine.

Let $\mathcal {B}$ be a box. Depending on the players’ input, an initial sequence $\varGamma _{0}$ (from $\mathcal {B}$) is determined. By $U\subseteq \mathsf{{Seq}}^{\mathcal {B}}$, we denote the set of all possible input sequences.

Next, we define a visible sequence that represents all public information with regard to the flavors of the candies. Consequently, we define $\mathsf{{top}}(\frac{?}{c})=\,?$ and $\mathsf{{top}}(c)=\mathsf{{top}}(\frac{c}{\epsilon })=c$ for $c\in \mathcal {B}$, which is based on the fact that when players bite a candy, the candy will disappear but its flavor will be memorized by all players. Then, we define $\mathsf{{vis}}(\varGamma )$ of a sequence $\varGamma =(\alpha _{1},\alpha _{2},\ldots ,\alpha _{m})$ as

$$ \mathsf{{vis}}((\alpha _{1},\alpha _{2},\ldots ,\alpha _{m}))=(\mathsf{{top}}(\alpha _{1}),\mathsf{{top}}(\alpha _{2}),\ldots ,\mathsf{{top}}(\alpha _{m})). $$

For instance,

$$ \mathsf{{vis}}\left( \left( \frac{1}{\epsilon },0,\frac{?}{1},\frac{0}{\epsilon },\frac{1}{\epsilon },\frac{?}{0},1\right) \right) =(1,0,?,0,1,?,1). $$

Furthermore, we define the set $\mathsf{{Vis}}^{\mathcal {B}}$ of all visible sequences as

$$ \mathsf{{Vis}}^{\mathcal {B}}=\{\mathsf{{vis}}(\varGamma )\, |\, \varGamma \in \mathsf{{Seq}}^{\mathcal {B}}\}. $$

We are now ready to formally define a public-PEZ protocol. A protocol is a 4-tuple $\mathcal {P}=(\mathcal {B},U,A,Q)$ such that

• $\mathcal {B}$ is a box;

• $U\subseteq \mathsf{{Seq}}^{\mathcal {B}}$ is a set of input sequences;

• Q is a set of states, containing the initial state $q_{0}$ and final state $q_{f}$;

• $A:(Q-\{q_{f}\})\times \mathsf{{Vis}}^{\mathcal {B}} \rightarrow Q \times \texttt {Action}$ is an action function, where $\texttt {Action}$ is the set of all possible actions $(\mathsf{{bite}}, T)$, $(\mathsf{{permute}}, \pi )$, $(\mathsf{{shuffle}}, \Pi , \mathcal {F})$, and $(\mathsf{{result}}, p)$.

A protocol $\mathcal {P}=(\mathcal {B},U,A,Q)$ proceeds as imagined; starting with an initial sequence $\varGamma _{0}\in U$ and initial state $q_{0}$, it changes the sequence and state based on the output of the action function. When the state becomes $q_{f}$, the protocol $\mathcal {P}$ terminates with an action $(\mathsf{{result}}, p)$ for some p.

4 Formal Description of Our AND Protocol and Another One

In this section, we formally describe our AND protocol presented in Sect. 2 based on the computational model of public-PEZ protocols defined in Sect. 3, which can be described as follows.

Next, to display another formal protocol, we describe the XOR protocol based on the card-based XOR protocol  [22].

We describe the above XOR protocol as an example. However, we do not intend to use this practically because it is relatively complicated, has a loop, and is a Las Vegas algorithm. (Actually, we can obtain a simple finite-runtime XOR protocol based on the four-card XOR protocol in [21].) Note that the number of available candies is finite, i.e., the box $\mathcal {B}$ has exactly seven lemon candies and seven orange candies. Therefore, if there is no candy available in Step 6, the protocol fails. This is a big difference between card-based protocols and public-PEZ protocols; the Las Vegas algorithm does not work well in public-PEZ cryptography.

5 Implementations of Shuffles of Candies

In this section, we discuss the feasibility of shuffling actions in public-PEZ protocols. It is more difficult to shuffle a sequence of candies using the players’ hands, compared to shuffling a sequence of cards. Therefore, we consider using the following special tools to implement a random bisection cut and random cut on a sequence of candies.

• Random Bisection Cut. As already seen in Sect. 2, we use two identical dispensers. First, the two divided sequences of candies are packed into the two dispensers without changing the orders. Then, we shuffle the two dispensers, take out the candies from each of the dispensers, and arrange them. The operation of shuffling the two dispensers must be implemented so that nobody knows how many times they are switched. The previous research  [32] proposed a secure implementation method for a random bisection cut in card-based protocols using a Styrofoam ball. This method can be used in public-PEZ protocols as well. Specifically, two dispensers are placed in a Styrofoam ball (the contents of which cannot be seen from the outside). Then, the ball is thrown up to shuffle the dispensers inside the ball.

• Random cut. We consider using a hose as shown in Fig. 7. First, we place the candies (to be shuffled) in the hose while maintaining the order, and tape its inlet and outlet. Then, we move the candies by rotating the hose. Finally, we take out the candies from the hose, while maintaining the order, and arrange them. The diameter of the hose must be tight enough that the order of the candies inside the hose does not change when it is rotated.

Fig. 7.

How to implement a random cut.

6 Conclusion

In this study, we designed public-PEZ cryptography. We constructed its computational model and presented a few protocols within the model. Further, we discussed the feasibility of shuffling actions for a sequence of PEZ candies. As public-PEZ protocols do not require private actions, players can perform MPC more securely and easily. In particular, we believe that our AND protocol presented in Sect. 2 is practical enough to be utilized in daily activities.

People might assume that this paper would just replace “cards” in card-based cryptography with “candies and dispensers,” i.e., public-PEZ cryptography is a type of re-implementation of card-based cryptography, and thus, there would not be much novelty. However, we believe that this is not the case. As already demonstrated, unlike a deck of cards, one cannot turn a candy face down and a candy disappears after one confirms its value; therefore, we need novel and careful treatment to construct a rigorous model. In addition, public-PEZ cryptography is simple, which is a virtue.