

Quantum Voting Scheme Based on Conjugate CodingAbstractWe describe a quantum voting scheme in which a ballot is an unknown quantum state for a voter. Such a ballot is hard to forge because it is difficult in principle to make a copy of an unknown quantum state. Moreover, our quantum voting scheme guarantees anonymity because the ballot can be randomized by voters. We also describe a distributed variant of our scheme that is robust against a dishonest administrator. This scheme should remain usable in the coming era of quantum computers, which are expected to break most existing cryptographic schemes.
1. IntroductionThere are several types of voting systems. Open ballot voting is a system in which voters write their own names on their ballots for selfidentification and to prevent double voting. In such a voting system, the privacy of the voters is not guaranteed. If voter privacy is desired, an anonymous voting system is better than open ballot voting. To achieve fair anonymous voting, the voting scheme should satisfy the following requirements.
Unlike in open ballot voting, in anonymous voting we need to achieve correctness while keeping anonymity. Since this is a challenging issue for cryptography, there has been a lot of research on cryptographic anonymous voting schemes. However, almost all existing practical electronic voting schemes that satisfy these requirements are based on the computational complexity assumption of discrete logarithm or integer factoring, which will be broken by quantum algorithms. Therefore, when a quantum computer is made in the future, we will lose almost all our practical electronic voting schemes. On the other hand, quantum information technology (QIT), which includes quantum communications and quantum computation, should be suitable for constructing a voting scheme because it is difficult to make a copy of an unknown quantum state in quantum physics. That is, if an unknown quantum state is used for a ballot, it is hard to forge, which is very suitable for a voting scheme. In this paper, we describe the new concept ofquantum voting. The anonymity of the protocol is guaranteed unconditionally because the ballots can be randomized by voters. Correctness, i.e., the onevoter onevote principle, is guaranteed by a quantum complexity assumption called onemore unforgeability, which means that it is impossible to forge an additional valid ballot. We also present a cutandchoose protocol and a distributed protocol for preventing the administrator from dishonestly executing procedures. In a distributed version of our scheme, no central entity (center) knows enough of the whole secret to issue blank ballots, which is better in terms of keeping secrecy. 1.1 Related workQuantum voting: There have been a few proposals of quantum voting schemes [1], [2] for specialized situations. The key technique of these voting schemes is distributing quantum entanglement for obtaining anonymity. Unlike those schemes, ours does not use quantum entanglement, so it should be easier to achieve and be more flexible for various circumstances. Electronic voting: There have been many proposals of classical electronic voting schemes. They can be classified into three approaches: (1) blindsignaturebased schemes [3]–[5], (2) mixnetbased schemes [6]–[10], and (3) homomorphicencryptionbased schemes [11]–[14]. Some of these achieve receiptfreeness [12] under the assumption of a oneway untappable channel [5], [8], [15] or twoway untappable channel [12], [16], [17]. 2. Our quantum voting schemeLetH be a 2dimensional Hilbert space, i.e., the space of a 1qubit state and letH^{k} be the ktimes tensor product of H, i.e., the space of the kqubit state. We define 1qubit state Ψ_{a, b} ∈H as The value of b determines the basis: if b is 0, then a is encoded in basis Z; if b is 1, then a is encoded in basis X. This encoding is the same as BB84 quantum cryptography [18] or conjugate coding [19]. Similarly, the qubit measurement is performed in basis Z or X if the measurement basis b is specified to be 0 or 1, respectively. For basis K = (b_{1}, ..., b_{n+1}) ∈{0, 1}^{n+1} and r = (a_{1}, ..., a_{n+1}) ∈{0, 1}^{n+1}, we denote We call state φ_{r}, K a blank piece with respect to basis K if a_{n+1} = a_{1} ⊕ ... ⊕ a_{n}. A blank piece is a fraction of a blank ballot, as described later. For the measurement of an (n+1)qubit state ρ ∈ H^{(n+1)} in basis K = (b_{1}, ..., b_{n+1}) ∈{0, 1}^{n+1}, we say that the measurement result is valid if the result ã_{1}, ..., ã_{n+1} satisfies ã_{n+1} = ã_{1} ⊕ ... ⊕ ã_{n}. Note that if we measure blank piece φ_{r, K} in basis K, the measurement result is always valid. 2.1 Onemore unforgeabilityNow, we define the onemoreunforgeability assumption, on which our quantum voting scheme is constructed. We consider the following game involving adversary F that models an adversarial voter who tries to forge blank pieces, i.e., tries to create a total of (w + 1) blank pieces when given w blank pieces. Let adversary F be a polynomialtime quantum Turing machine and n be a security parameter. At the beginning of the game, basis K = (b_{1}, ..., b_{n+1}) ∈ {0, 1}^{n+1} is selected uniformly. Adversary F is given w (which is polynomial in n) blank pieces Φ_{rj,} _{K} ∈H^{(n+1)} (j = 1, ..., w) with respect to basis K. Here, r_{j} = (a_{j, 1,} ..., a_{j, n+1})∈{0, 1}^{n+1}, a_{j, 1}, ..., a_{j, n} are selected uniformly, and a_{j, n+1} = a_{j, 1} ⊕ ... ⊕ a_{j, n} (j = 1, ..., w). Note that F is not given K and r_{j}. Finally, adversary F outputs a (w+1)(n+1)qubit state ρ ∈ H ^{(w+1)(n+1)}. We define the advantage Adv(F) of adversary F as Assumption. (Onemore unforgeability) We say that the onemore unforgeability assumption holds if, for every polynomialtime quantum adversary F, the advantage Adv(F) is negligible with respect to security parameter n. 2.2 Quantum voting protocolIn this subsection, we describe our quantum voting protocol. The anonymity of this protocol is guaranteed unconditionally, and correctness is guaranteed if the onemoreunforgeability assumption holds. Let n be a security parameter and m = O(n) be the bit length of the voting message. There are an administrator A, counter C, and υ voters V_{i} (i = 1, ...,υ). We assume (1) an authenticated channel, where sender and receiver are authenticated, from administrator A to voter V_{i} and (2) a senderanonymous channel, where the sender is anonymous and the receiver is authenticated, from voter V_{i} to counter C. For simplicity, we assume that these channels are secure, i.e., errorfree. Counter C is assumed to carry out protocols correctly; otherwise, the result of voting could be manipulated as C desired. C just acts as a fair procedure and other aspects of security do not especially depend on his existence, i.e., C does not have any secrets of his own and all results of measurement are published. Issuing. Administrator A uniformly selects a secret K = (b_{1}, ..., b_{n+1}) ∈{0, 1}^{n+1}. Then, for i = 1, ..., υ, administrator A selects r^{i} = (r^{i}_{1}, ..., r^{i}_{m}) = (a^{i}_{1}, 1, ..., a^{i}_{1}, _{n+1}, ..., a^{i}_{m, 1}, ..., a^{i}_{m, n+1}) ∈{0, 1}^{m(n+1)}, where a^{i}_{j, 1} ... a^{i}_{j, n} (j = 1, ..., m) are selected uniformly and a^{i}_{j, n+1} = a^{i}_{j, 1} ⊕ ... ⊕ a^{i}_{j, n} (j = 1, ..., m), and constructs a blank piece Φ_{rij}, _{K} and a blank ballot A blank ballot is depicted in Fig. 1. Administrator A sends the blank ballot η^{i} to voter V_{i} through the authenticated channel.
Randomization. Voter V_{i} receives the blank ballot η^{i} from administrator A through the authenticated channel. He selects t^{i} = (t^{i}_{1}, ..., t^{i}_{m}) = (d^{i}_{1, 1}, ..., d^{i}_{1, n+1}, ..., d^{i}_{m, 1}, ..., d^{i}_{m, n+1}) ∈{0, 1}^{m(n+1)}, where d^{i}_{j, 1} ... d^{i}_{j, n} (j = 1, ..., m) are selected uniformly and d^{i}_{j, n+1} = d^{i}_{j, 1} ⊕ ... ⊕ d^{i}_{j, n} (j = 1, ..., m), and obtains a randomized blank ballot Y^{dij, n+1}, where Y = XZ = and Y^{0} = I = . A randomized blank ballot is depicted in Fig. 2.
Remark: The unitary transformation Y flips a for both bases Z and X. Sometimes, it also changes the global phase, but no one can distinguish the difference in global phase. Consequently, the global phase change caused by Y does not affect the user's anonymity. Remark: Since each blank ballot has a randomly chosen pattern of information r^{i}, if a voter utilizes a blank ballot without any modification, the administrator may be able to trace the ballot by recording r^{i}, so the voter's privacy cannot be guaranteed. Voting. Let M ⊂ {0, 1}^{m} be the set of all the valid voting messages, where the number of valid voting messages M is constant for security parameter n and m = O(n), so the probability that a random bit string becomes a valid voting message is negligible for n. On the randomized blank ballot η^{′i}, voter V_{i} writes his/her voting message c^{i} = (c^{i}_{1}, ..., c^{i}_{m}) ∈M ⊂ {0, 1}^{m}, where c^{i} is the name of the candidate for whom voter V_{i} wants to vote. Voter V_{i} makes his/her voting ballot
Counting. Counter C receives secret K from administrator A through a classical secure channel after all voters have sent their votes. He receives all ballots η^{(ci)} (i = 1, ..., υ) from all voters V_{i} (i = 1, ...,¦Ô) through the senderanonymous channel. He measures all ballots η^{(ci)} (i = 1, ...,¦Ô) and obtains the measurement results (˜a^{i}_{j, 1}, ..., ˜a^{i}_{j,n+1}) (i = 1, ...,¦Ô, j = 1, ..., m), where (˜a^{i}_{j,1}, ..., ˜a^{i}_{j,n+1}) are the measurement results of jth (n+1) qubits of η^{(ci)} in basis K = (b_{1}, ..., b_{n+1}). He computes ˜c^{i}_{j} = ˜a^{i}_{j,1} ⊕ ... ⊕ ˜a^{i}_{j, n+1} (i = 1, ...,¦Ô, j = 1, ..., m), and checks whether or not ˜c^{i} = (˜c^{i}_{1}, ..., ˜c^{i}_{m}) ∈M ⊂ {0, 1}^{m}. If ˜c^{i} ∈M, then ˜c^{i} is counted as the result of the voting; otherwise, ˜c^{i} is discarded. 2.3 Cutandchoose protocol for issuingIf a malicious administrator issues invalid blank pieces, correctness and anonymity can be violated because the administrator can nullify and/or trace a ballot by mixing invalid pieces into it. To avoid the risk of this, we can use a cutandchoose technique to verify the validity of blank pieces issued by the administrator. Our cutandchoose protocol is explained below. In the issuing stage, administrator A creates 2mυ blank pieces φ_{r}, K and puts them in register R. Each voter V_{i} randomly picks m blank pieces as his/her blank ballot η^{i}. Before the counting stage, after all voters have cast their votes, counter C receives secret K from administrator A through a classical secure channel and performs the following check. Counter C measures mv blank pieces left in register R using secret basis K and checks whether or not all the results of these measurements are valid. If some are found to be invalid, we judge that administrator A issued invalid blank pieces and abort the voting process. Note that a malicious administrator can mingle a small number of invalid blank pieces into a voter's blank ballot without detection even if we use the cutandchoose protocol. 2.4 The toutofl threshold protocol for issuingHere, we present a threshold distributed protocol based on threshold quantum cryptography. If an administrator who knows secret K illegally casts a valid voting ballot in the voting stage, or dishonestly gives secret K to adversaries, then the adversaries can freely forge ballots as they like. To avoid the risk of this, a distributed scheme is very effective. In such a scheme, several centers each hold a share of secret K, and these centers collaborate to create blank pieces. In this toutofl threshold distributed protocol, each center chooses its secret by itself and distributes shares of its own secret. Once the secrets have been shared among l centers, an arbitrary toutofl centers can issue valid blank pieces. After the preliminary secret distribution phase, even if l−t centers happen to be down or out of service, at least t centers will still work properly, so the whole scheme works correctly. Moreover, if the number of dishonest centers is smaller than t, they cannot make valid quantum ballots. We apply a threshold technique such as Shamir's secret sharing scheme [21] (i.e., toutofl scheme) for this threshold distributed protocol. We also apply Pederson's idea [22] that several centers share their own secrets. Distribution. For l centers to distribute shares of their secrets, all centers P_{j} out of the l centers perform the following procedure. P_{j} chooses its own secret σ_{j} = (b_{j,1}, b_{j, 2}, ..., b_{j,n+1}), where b_{j, k} are uniformly chosen from {0, 1}. The center P_{j} then makes l shares, S_{j,1}, ..., S_{j, l}, of σ_{j} by using Shamir's secret sharing scheme over GF(2^{N}), where N = n+1. Let f_{j} (x) be a secret (t−1)thdegree polynomial, S_{j}_{,i} = f_{j} (x_{j, i}) for i = 1, ..., l, and σ_{j} = f_{j}(0) over GF(2^{N}), where x_{j, i} for i = 1, ..., l are l distinct points in GF(2^{N}) and are published. The center P_{j} sends S_{j, i} to a center P_{i} secretly for each i = 1, ..., l. Precomputation. For simplicity, we assume that the t centers P_{1}, ..., P_{t} collaborate to issue blank pieces. For each i = 1, ..., t, P_{i} calculates and secretly stores the following value using the Lagrange interpolation formula Let Note that even in the collaboration procedure, K_{i} and σ_{j} are kept secret in P_{i}, and K is not recovered. Issuing. The t centers P_{1}, ..., P_{t} collaborate to construct a blank piece φ. Below, we describe the sequential protocol from P_{1} to P_{t}, but the order is not essential: any order is possible. P_{1} generates a quantum state Next, P_{1} sends φ^{[1]} to P_{2}. When P_{i} receives φ^{[i−1]} from P_{i−1}, P_{i} follows the following procedure to generate φ^{[i]} and sends it to P_{i+1}, where i = 2, ..., l and P_{l+1} is a voter. Then, P_{i} obtains φ^{[i]} by applying the following unitary transformation W^{[i]} to φ^{[i−1]}. where Here, a^{[i]}_{n+1} = a_{1}^{[i]} ⊕ ... ⊕ a_{n}^{[i]}, r^{[i]} = (a_{1}^{[i]}, ..., a_{n}^{[i]}), ∈{0, 1}^{n} is a random string uniformly picked by P_{i} for each blank piece, unitary transformation Y follows the previous definition in Subsection. 2.2, and After repeating this procedure, finally P_{l} sends φ^{[l]} to a voter as a blank piece. Correctness. φ^{[1]} encodes string a_{1}^{[1]}, ..., a^{[1]}_{n+1} using secret bases K^{[1]}. By unitary transformation W^{[2]}, φ^{[1]} is transformed into φ^{[2]} (here, we ignore the global phase), which encodes a_{1}^{[1]} ⊕ a_{1}^{[2]} , ..., a^{[1]}_{n+1} ⊕ a^{[2]}_{n+1} using basis K^{[1]} ⊕ K^{[2]}. Finally, φ^{[t]} encodes a_{1}^{[1]} ⊕ ... ⊕ a_{1}^{[l]} , ..., a^{[1]}_{n+1} ⊕ ... ⊕ a^{[l]}_{n+1} using basis K = K^{[1]} ⊕ K^{[2]} ⊕ ... ⊕ K^{[l]}. Thus, the quantum ballot φ^{[l]} is valid. Security. If we assume that the communication among l parties during their collaboration is protected from adversaries and that the l parties are honest, then the security of the threshold scheme is at least on the same level as the original voting scheme. 3. Security of our quantum voting scheme3.1 Security considerations for voting requirementsCorrectness. First, we consider an active attack by a voter who tries to forge ballots. In this case, security will depend on the quantum computational complexity problem, i.e., onemore unforgeability (the Assumption in Subsection 2.1), whose hardness is not clearly understood yet, so conclusive security is beyond the scope of this paper. Here, we show that several naïve attacks cannot work well. It is impossible to simply make a copy of an unknown quantum state in principle according to the nocloning theorem. If a forger (including a voter) tries to make a quantum ballot without knowing secret K, i.e., randomly makes a forged quantum ballot, the forged ballot ψ is accepted with probability M/2^{m}. Since the number of candidates M is constant, the probability of successful forging is negligible. If K is derived from valid blank ballots, an adversary can forge valid ballots freely. However, deriving secret key K is intractable, as described in Subsection 3.2. So, it is difficult for a dishonest voter to forge quantum ballots in our scheme. Next, we consider an active attack by the administrator. If the administrator mixes k invalid blank pieces into 2mv blank pieces in the issuing stage, we can detect invalid blank pieces with probability 1–1/2^{k} using our cutand choose protocol for issuing. If an invalid blank piece is detected, we abort the voting. The invalid blank pieces pass through the checking stage with probability 1/2^{k}, so in this case, the administrator can nullify at most k unspecified votes. Anonymity. A voter cannot break the privacy of another voter because he is isolated from the other voter's procedures and the communication channels are protected to make them secure. Thus, we consider only an active attack by the administrator. Since all quantum voting ballots are sent through an anonymous channel, if there is no identifiable information in a ballot, then the privacy of voting is kept. The administrator can record randomness r encoded in blank ballot η in order to try and break the privacy of voters. To prevent this, the voter randomizes η by applying random unitary transformation U with randomness t and obtains randomized blank ballot η with randomness r′ = r⊕ t. Since t is uniformly selected by the voter, the original randomness r is unconditionally concealed and privacy is protected. Although the administrator can mix k invalid blank pieces into 2mυ blank pieces in the issuing stage to trace votes and break privacy, we can detect the invalid blank pieces in the register with probability 1–1/2^{k} using our cutand choose protocol. If an invalid blank piece is detected, we abort the voting and discard the quantum voting ballots held by counter C. Therefore, in this case, votes are never revealed and privacy is protected. The invalid blank pieces pass through the checking stage with probability 1/2^{k}. In this case, the administrator can invalidate at most k unspecified votes and break the privacy of at most k unspecified voters. Receiptfreeness. A voter might try to embed some information into his/her voting ballot η^{(c)} in order to prove his/her vote to a buyer/coercer. However, since the voter does not know randomness r encoded in blank ballot η, he/she cannot control randomness r′ encoded in blank ballot η′. If the voter mixes errors into the name of candidate c encoded in his/her voting ballot η^{(c)}, then voting ballot η^{(c)} can be traced, but it will be discarded and not counted. A voter might try to copy his/her voting ballot η^{(c)} to make a receipt for the vote buyer/coercer. However, it is difficult to copy quantum voting ballot η^{(c)}, as already described in Correctness. 3.2 Intractability of finding secret key KLet us consider a straightforward individual attack on our voting scheme. An adversary F is given a blank ballot φ = φ_{r1, K} ... φ_{rm, K} and examines the basis K by measuring quantum bits individually as follows. First, F guesses K from {0, 1}^{n+1} and measures φ_{rj, K} with the basis and gets the result (˜a_{,j, 1}, ..., ˜a_{j}_{, n+1}). If the guess of K is correct, then all the results are valid i.e., ˜a_{j}_{, n+1} = ˜a_{j}_{, 1} ⊕ ... ⊕ ˜a_{j}_{, n} for all j. Then, F is assured that his guess is correct and he has obtained the correct K. The guess of b_{k} of K = (b_{1}, ..., b_{n}_{+1}) is correct with probability 1/2, so the probability that guesses of all b_{k} for k = 1, ..., n+1 are correct is only 1/2^{n+1}. Therefore, the secrecy of K against the simple individual attack is proven. It has been pointed out that a Grovertype attack is applicable to this construction [23] if we allow F to use a general (coherent) attack. However, it still needs exponential time quantum computation. Grover's algorithm [24] has been proven to be optimal within the querytype algorithm to find a unique solution from a database [25]–[27]. Thus, F needs another type of algorithm to get secret bases efficiently, but no efficient attack has been found yet. In our scheme, the parity of random bits a_{j}_{, 1} ⊕ ... ⊕ a_{j, n} = a_{j}_{, n+1} is encoded in ψ_{aj, n+1, bn+1} of φ_{rj, K} and the rest of φ_{rj, K} is a totally random state for voters who do not know K. The construction of our scheme is very simple and it seems to be difficult to find another type of algorithm that is not a querytype algorithm. Although the difficulty has not been proven, it might be reduced to the difficulty of a wellknown computational complexity problem such as [28], which is believed to be difficult even for a quantum computer. We leave this complexity as an open problem. 4. Concluding remarksIn this paper, we described a new cryptographic protocol concept, quantum voting. The anonymity of the protocol is unconditionally guaranteed, and correctness is guaranteed if the onemoreunforgeability assumption holds. We also presented a cutandchoose protocol and a distributed protocol for preventing the administrator from dishonestly executing procedures. In this paper, we just assumed that the quantum channel is secure (errorfree) for simplicity. We could eliminate this assumption by constructing a secure quantum channel using a quantum onetime pad [29], [30] or using some other means. We leave the analysis of quantum computational complexity as an open problem. Although the security of our protocol is based on quantum computational complexity and does not have unconditional security, it should have many applications in quantum information technology. To implement a quantum voting scheme, we need a quantum register/memory. Since our scheme does not make use of quantum entanglement, a sufficient register for our scheme is one of the most basic elements of quantum computers, that is, a 1qubit register that need not keep quantum correlation between two quantum bits. (The situation will be different when we implement quantum error correction.) Even such a quantum register is still beyond our current technologies. However, such technologies are being extensively studied and developed. In addition, the operation needed for our scheme is very simple, only 1qubit unitary transformation, which is already feasible. Finally, we emphasize that the use of a quantum state to achieve a voting scheme should be an attractive and fruitful research approach. The work described in this paper is the first step in this direction. References
