Extended Addition Protocol and Efficient Voting Protocols Using Regular Polygon Cards

Secure computation protocol is a cryptographic protocol for outputting computation results while keeping the input secret. Most of secure computation protocols are intended to be implemented on computers, but there has been some research into the use of physical objects to implement secure computation. In particular, the research area in which secure computation is performed using a deck of physical cards is called card-based cryptography [3, 4, 12]. Card-based protocols for various functions have been proposed: a secure voting protocol [11, 20, 21], a three-input majority protocol [1, 2, 15, 25‐27], a Millionaires’ protocol [9, 10, 13, 14, 16, 17], a secure matching protocol [19], a secure grouping protocol [7, 8], a covert lottery protocol [22], a private set intersection protocol [5], a secure ranking protocol [23, 24], a secure sorting protocol [6], and so on. Most of these protocols use binary cards such as and number cards such as .

For many people who are not familiar with cryptography, the most familiar task on secure computation would be voting. Mizuki, Asiedu, and Sone [11] proposed the first card-based voting protocol. It focuses on n voters and two candidates and requires \(2\lceil \log n \rceil + 6\) binary cards. An addition protocol, which is closely related to the voting protocol, was proposed by Ruangwises and Itho [18]. It computes the sum of n input bits using \(2n+2\) binary cards.

Shinagawa et al. [20, 21] proposed a new card called a regular n-sided polygon card, which can hold a value \(x \in \mathbb {Z}/n\mathbb {Z}\). A face-down card holding a value x is called a commitment to x. Based on regular n-sided polygon cards, they constructed an addition protocol that takes two commitments to \(x_1, x_2 \in \mathbb {Z}/n\mathbb {Z}\) as input and outputs a commitment to \(x_1 + x_2 \pmod n\). It requires two cards and one shuffle. They also proposed a voting protocol with v voters and c candidates when \(v<n\). It requires \(c(v+2)\) regular n-sided polygon cards and \(v+1\) shuffles.

To the best of our knowledge, there are no card-based voting protocols using cards other than the binary cards and the regular polygon cards.

In this paper, we propose an extended addition protocol, which takes two sequences of face-down cards representing \(x_1, x_2 \in \mathbb {Z}/mn\mathbb {Z}\) and outputs a sequence of face-down cards representing \(x_1 + x_2 \pmod {mn}\), and two voting protocols using regular n-sided polygon cards (see Table 1). Our extended addition protocol requires 2m cards and one shuffle. Our first voting protocol requires \(c(\lceil \frac{v+1}{n} \rceil + v + 1)\) cards and \(v+1\) shuffles. Note that Shinagawa et al.’s protocol has a restriction \(v < n\), our first voting protocol does not have such a restriction, i.e., we can choose the number of voters v freely. Our second voting protocol reduces the number of cards to \(\lceil \frac{v+1}{n} \rceil n + v + 1\) when \(v < n\) and \(c \le n\). Thus, there are trade-offs between the number of cards and the restrictions.

A regular n-sided polygon card proposed by Shinagawa et al. [21] is a card with the following properties:An integer a from 0 to \(n-1\), which is naturally considered as an element of \(\mathbb {Z}/n\mathbb {Z}\), can be encoded into a regular n-sided polygon card. In the following, we deal with \(n = 4\) and denote by its front side and by its back side. The encoding rule is as follows:A face-down card with an integer \(a\in \mathbb {Z}/n\mathbb {Z}\) as above encoding rule is called a commitment to a and denoted by \([\![a]\!] \). Let \(\mathcal {F}_{n}:= \{0, 1, \ldots , n-1\}\) be the set of front-side cards and \(\mathcal {B}_{n} := \{[\![0]\!] , [\![1]\!] , \ldots , [\![n-1]\!] \}\) be the set of back-side cards, and \(\mathcal {C}_{n}=\mathcal {F}_{n} \bigcup \mathcal {B}_{n}\).

In this paper, we use a stack of cards, which is introduced by Shinagawa et al. [20, 21]. A stack of cards is defined by an ordered collection of cards. For \(\ell \) cards \(c_1, c_2, \ldots , c_{\ell } \in \mathcal {C}_{n}\), a stack s is denoted by \(s = c_1 \circ c_2 \circ \cdots \circ c_{\ell }\), where the top is \(c_1\) and the bottom is \(c_{\ell }\). Given a stack s, a player can obtain two pieces of information only: the face of the topmost card \(c_1\) and the number of cards \(\ell \) in the stack. We note that although describing our protocols without the notion of stack is possible, introducing the notion has the advantage of making it easier to understand how to implement the protocol.

Now we introduce the basic operations for regular polygon cards used in our protocols.

The addition protocol proposed by Shinagawa et al. [20, 21] is summarized as follows:We describe the protocol for \(n=4\) as follows: Based on the addition protocol, protocols for subtraction, copy, and constant-multiplication can be easily obtained.

Suppose that there are v voters and c candidates. The i-th voter having \(a_i \in \mathbb {Z}/c\mathbb {Z}\) as input, which is encoded by a sequence of cards as follows:where \(e_j(a_i) = 1\) if \(a_i = j\) and 0 otherwise.

The voting protocol proposed by Shinagawa et al. [20, 21] is summarized as follows:Before describing the protocol, we explain the idea behind the protocol. First, an \((v+2) \times c\) card matrix is arranged: The topmost v rows correspond to v voters’ inputs and the bottom two rows correspond to the rows for recording the result and reordering the order of the sequence. Then, a pile-shifting shuffle is applied to this matrix and then the input of each voter is added to the bottom row. Since one pile-shifting shuffle is required to add the input of each voter and one pile-shifting shuffle is required to rearrange the order of the sequence at the end, the protocol requires \(v+1\) pile-shifting shuffles in total.

The protocol for \((v, c, n) = (2, 3, 4)\) proceeds as follows:

In this section, we propose a cyclic integer encoding, which enables to deal with a large number of modulus. A cyclic integer encoding is parameterized by n and k, where n is the modulus and k is the number of cards.

The encoding rule for \(n = 4\) and \(k = 3\) is as follows:By moving the leftmost card to the rightmost with adding 1, the value i is changed to \(i+1 \pmod {12}\).

A cyclic integer encoding for general case is defined as follows. For a vector of integers \(v = (a_1, a_2, \ldots , a_k) \in (\mathbb {Z}/n\mathbb {Z})^k\), the next vector of v is defined by \(\textsf{next}(v) = (a_2, \ldots , a_k, a_1 + 1)\), where the addition is done by modulo n. An (n, k) cyclic integer encoding is defined by a function \(\textsf{E}_{(n,k)}\) that maps an integer \(i \in \mathbb {Z}/nk\mathbb {Z}\) to a vector \(\textsf{next}^i(0^k)\), where \(0^k = (0,0,\ldots , 0)\) is the zero vector of length k. We omit (n, k) when it is clear from the context. Note that the inverse map \(\textsf{E}_{(n,k)}^{-1}\) can be easily computed by:A multi-card commitment is a sequence of face-down cards based on the cyclic integer encoding. As a special case of multi-card commitment when \(k = 1\), a commitment using one card is sometimes referred to as a single-card commitment. For example, when \(n = 4\) and \(k = 3\), a multi-card commitment to 7 is shown as follows:By moving the leftmost card to the rightmost with applying a rotation, a multi-card commitment \([\![\textsf{E}(x)]\!] \) is changed to \([\![\textsf{E}(x + 1)]\!] \). We call it a next operation. For a sequence of stacks \((s_1, s_2, \ldots , s_{m})\), the next operation \(\textsf{next}\) is similarly defined as follows:A rot-and-shift shuffle is a shuffle that takes a sequence of k stacks \(\textbf{s}\) and outputs \(\textsf{next}^r(\textbf{s})\), where \(r \in \mathbb {Z}/nk\mathbb {Z}\) is chosen uniformly at random. Here, the random number r must be hidden from all players, including the player performing the shuffle. For example, when \(n = 4, k = 3\) and \(r = 8\) is chosen, The following is an example of a rot-and-shift shuffle when \(n = 4, k = 3\), and \(r = 8\):To implement a rot-and-shift shuffle, you can apply the next operation (which can be performed by human hands) many times until you lose track of the number of repetitions. Another implementation is to use private permutations: Each player \(P_i\) chooses \(r_i \in \mathbb {Z}/nk\mathbb {Z}\) privately and uniformly at random in his head, and applies the next operation \(r_i\) times privately. Note that while both implementations are indeed operable, there are several challenges to making them secure. In the former implementation, it seems difficult to hide the number of next operations if it is not done quickly. In the latter implementation, it seems difficult to generate uniform random numbers in the brain. Since the rot-and-shift shuffle is useful as shown in this paper, it is an interesting research question that whether the rot-and-shift shuffle has a simpler implementation.

An extended addition protocol takes two multi-card commitments \([\![\textsf{E}_{(n,k)}(x)]\!] \) and \([\![\textsf{E}_{(n,k)}(y)]\!] \) as input and outputs a multi-card commitment \([\![\textsf{E}_{(n,k)}(x+y)]\!] \). For security, the protocol ensures that the distribution of all opened values is independent of the distribution of the input values. The number of cards is 2k (i.e., it uses no additional cards) and the number of shuffles is one rot-and-shift shuffle. It proceeds as follows: We prove the security of the protocol. The opened value in the protocol is only \(\epsilon = x + r\) in Step 5. Since r is chosen uniformly at random due to the effect of the rot-and-shift shuffle, the opened value \(\epsilon \) is independent of the distribution of the inputs. Thus the protocol is secure.

Similarly, an addition protocol computing \(a+b_1, a+b_2, \ldots , a + b_k \in \mathbb {Z}/mn\mathbb {Z}\) for \(a, b_1, b_2, \ldots , b_k \in \mathbb {Z}/mn\mathbb {Z}\) can be constructed by making \(s_i = [\![a_i]\!] \circ b_{1, k-1-i} \circ b_{2, k-1-i} \circ \cdots \circ b_{k, k-1-i}\) in Step 2, where \(a_i\) and \(b_{j,i}\) are the i-th card of \(\textsf{E}(a)\) and \(\textsf{E}(b_j)\), respectively.

Also, by setting \(b_1 = b_2 = \cdots = b_k = 0\) for this extended addition protocol, a protocol that outputs k copies of a commitment to a can be constructed.

We propose a voting protocol with no restriction on parameters. In particular, the number of voters v and candidates c are not restricted by the number of sides n. This is contrast to the existing voting protocol [20, 21], which has a restriction on \(v < n\), i.e., the number of voters is less than the number of sides.

The idea behind our proposed protocol is almost same as the existing protocol in Sect. 3.2 except that our proposed protocol uses the cyclic integer encoding. Due to the cyclic integer encoding, the number of voters v is not restricted, i.e., the restriction \(v < n\) is removed.

Given a parameter (v, c, n), the number of cards k in the cyclic integer encoding is given by \(k = \lceil \frac{v+1}{n}\rceil \). In the same as the existing protocol, the i-th voter with \(a_i \in \mathbb {Z}/c\mathbb {Z}\) submits a sequence of cards representing \(e(a_i) = (e_0(a_i), e_1(a_i), \ldots , e_{c-1}(a_i))\), where \(e_j(a_i) = 1\) if \(a_i = j\) and 0 otherwise. For security, the protocol ensures that the distribution of all opened values is independent of the distribution of the input values. The protocol proceeds as follows: The correctness of the protocol is straightforward. For the security, we can observe that the opened values in Steps 2.c and 4 are independent and uniformly random numbers due to the pile-shifting shuffles. Thus the protocol is secure. The number of cards of the protocol is \(c(v+k+1)\). The number of shuffles is \(v+1\) pile-shifting shuffles.

We next propose a voting protocol for a small number of candidates \(c \le n\). In this case, the number of cards can be reduced to \(kn+v+1\). Before describing the protocol, we explain the idea behind the proposed protocol. The basic strategy of the protocol is similar to the protocol in Sect. 5.1, but the protocol has two major improvements. First, unlike the protocol in Sect. 5.1, each voter’s input is given as a single-card commitment. This is made possible by the assumption \(c \le n\). Second, the protocol uses a flower shuffle instead of the pile-shifting shuffle. This allows for efficient computation when using a single-card commitment.

Suppose that the i-th voter with \(a_i \in \mathbb {Z}/c\mathbb {Z}\) submits a single-card commitment \([\![a_i]\!] \). For security, the protocol ensures that the distribution of the opened values is independent from the distribution of the input values. The protocol proceeds as follows: The correctness of the protocol is straightforward. For the security, we can observe that the opened values in Steps 3.b and 5 are independent and uniformly random numbers due to the flower shuffles. Thus the protocol is secure. The number of cards of the protocol is \(nk+v+1\). The number of shuffles is \(v+1\) flower shuffles.

We claim that the number of cards of the above protocol is less than those of the protocol in Sect. 5.1 and the existing protocol by Shinagawa et al. [20, 21]. Suppose that \(v+1\) is divided by n for simplicity. Then we can choose \(k = \frac{v+1}{n}\). In this case, the number of cards of the above protocol is \(nk+v+1 = 2(v+1)\) while that of the protocol in Sect. 5.1 is \(c(k + v + 1) = \frac{c(1 + n)}{n}(v+1)\) and that of the existing protocol by Shinagawa et al. [20, 21] is \(c(v+2)\), both of which are greater than \(2(v+1)\) for any \(c \ge 2\). Since our protocol requires a condition on \(c \le n\), our protocol is more efficient than the other protocols for any \(2 \le c \le n\).