Quantum Voting Scheme Based on Conjugate Coding

1.1 Related work

Quantum 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) blind-signature-based schemes [3]–[5], (2) mix-net-based schemes [6]–[10], and (3) homomorphic-encryption-based schemes [11]–[14]. Some of these achieve receipt-freeness [12] under the assumption of a one-way untappable channel [5], [8], [15] or two-way untappable channel [12], [16], [17].

2.1 One-more unforgeability

Now, we define the one-more-unforgeability 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 polynomial-time quantum Turing machine and n be a security parameter. At the beginning of the game, basis K = (b₁, ..., b_n+1) ∈ {0, 1}ⁿ⁺¹ is selected uniformly. Adversary F is given w (which is polynomial in n) blank pieces Φ_{rj, K} ∈H⁽ⁿ⁺¹⁾ (j = 1, ..., w) with respect to basis K. Here, r_j = (a_{j, 1,} ..., a_{j, n+1})∈{0, 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

where (ã_{j, 1}, ..., ã_{j, n+1}) are the measurement results of the j-th (n+1) qubits of ρ in basis K and the probability is taken over the choice of K, the choice of r_j (j = 1, ..., w), and the postulate of quantum measurement.

Assumption. (One-more unforgeability) We say that the one-more unforgeability assumption holds if, for every polynomial-time quantum adversary F, the advantage Adv(F) is negligible with respect to security parameter n.

2.2 Quantum voting protocol

In this subsection, we describe our quantum voting protocol. The anonymity of this protocol is guaranteed unconditionally, and correctness is guaranteed if the one-more-unforgeability 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 sender-anonymous 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., error-free. 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₁, ..., b_n+1) ∈{0, 1}ⁿ⁺¹. Then, for i = 1, ..., υ, administrator A selects rⁱ = (rⁱ₁, ..., rⁱ_m) = (aⁱ₁, 1, ..., aⁱ₁, _n+1, ..., aⁱ_{m, 1}, ..., aⁱ_{m, n+1}) ∈{0, 1}^m(n+1), where aⁱ_{j, 1} ... aⁱ_{j, n} (j = 1, ..., m) are selected uniformly and aⁱ_{j, n+1} = aⁱ_{j, 1} ⊕ ... ⊕ aⁱ_{j, n} (j = 1, ..., m), and constructs a blank piece Φ_rⁱj, _K and a blank ballot

A blank ballot is depicted in Fig. 1.

Administrator A sends the blank ballot ηⁱ to voter V_i through the authenticated channel.

Fig. 1. Quantum blank ballot ηⁱ.

Randomization. Voter V_i receives the blank ballot ηⁱ from administrator A through the authenticated channel. He selects tⁱ = (tⁱ₁, ..., tⁱ_m) = (dⁱ_{1, 1}, ..., dⁱ_{1, n+1}, ..., dⁱ_{m, 1}, ..., dⁱ_{m, n+1}) ∈{0, 1}^m(n+1), where dⁱ_{j, 1} ... dⁱ_{j, n} (j = 1, ..., m) are selected uniformly and dⁱ_{j, n+1} = dⁱ_{j, 1} ⊕ ... ⊕ dⁱ_{j, n} (j = 1, ..., m), and obtains a randomized blank ballot

where U^(ti) = U₁^(ti₁) ... U_m^(ti_m) and U_j^(ti_j) = Y^{di_{j, 1}} ...

Y^{di_{j, n+1}}, where Y = XZ = and Y⁰ = I = .

A randomized blank ballot is depicted in Fig. 2.

Fig. 2. Randomized quantum blank ballot η^′i.

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ⁱ, if a voter utilizes a blank ballot without any modification, the administrator may be able to trace the ballot by recording rⁱ, 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ⁱ = (cⁱ₁, ..., cⁱ_m) ∈M ⊂ {0, 1}^m, where cⁱ is the name of the candidate for whom voter V_i wants to vote. Voter V_i makes his/her voting ballot

where U^(ci) = U₁^(ci₁) ... U_m^(ci_m), U_j^(ci_j) = I ... I Y^ci_j. A voting ballot is depicted in Fig. 3. Voter V_i sends the ballot η^(ci) to counter C through the sender-anonymous channel.

Fig. 3. Quantum voting ballot η^(ci).

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 sender-anonymous channel. He measures all ballots η^(ci) (i = 1, ...,υ) and obtains the measurement results (˜aⁱ_{j, 1}, ..., ˜aⁱ_j,n+1) (i = 1, ...,υ, j = 1, ..., m), where (˜aⁱ_j,1, ..., ˜aⁱ_j,n+1) are the measurement results of j-th (n+1) qubits of η^(ci) in basis K = (b₁, ..., b_n+1). He computes ˜cⁱ_j = ˜aⁱ_j,1 ⊕ ... ⊕ ˜aⁱ_{j, n+1} (i = 1, ...,υ, j = 1, ..., m), and checks whether or not ˜cⁱ = (˜cⁱ₁, ..., ˜cⁱ_m) ∈M ⊂ {0, 1}^m. If ˜cⁱ ∈M, then ˜cⁱ is counted as the result of the voting; otherwise, ˜cⁱ is discarded.

2.3 Cut-and-choose protocol for issuing

If 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 cut-and-choose technique to verify the validity of blank pieces issued by the administrator. Our cut-and-choose 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 ηⁱ.

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 cut-and-choose protocol.

2.4 The t-out-of-l threshold protocol for issuing

Here, 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 t-out-of-l 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 t-out-of-l 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., t-out-of-l 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)-th-degree 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₁, ..., 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

be the binary representation of K_i in GF(2^N), where b_k^[i] are in {0, 1}. The whole secret is

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₁, ..., P_t collaborate to construct a blank piece φ. Below, we describe the sequential protocol from P₁ to P_t, but the order is not essential: any order is possible.

P₁ generates a quantum state

where r^[1] = (a₁^[1], ..., a_n^[1]), ∈{0, 1}ⁿ is a random string uniformly picked by P₁ for each blank piece, and a^[1]_n+1 = a₁^[1] ⊕ ... ⊕ a_n^[1]. Here, ψa_i^[1]b_i^[1] is defined in the same manner as in Eq. (1).

Next, P₁ sends φ^[1] to P₂. 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₁^[i] ⊕ ... ⊕ a_n^[i], r^[i] = (a₁^[i], ..., a_n^[i]), ∈{0, 1}ⁿ 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], ..., 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] ⊕ a₁^[2] , ..., a^[1]_n+1 ⊕ a^[2]_n+1 using basis K^[1] ⊕ K^[2]. Finally, φ^[t] encodes a₁^[1] ⊕ ... ⊕ a₁^[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.1 Security considerations for voting requirements

Correctness. 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., one-more 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 no-cloning 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 cut-and 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 cut-and 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.

Receipt-freeness. 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 K

Let 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}ⁿ⁺¹ 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₁, ..., 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ⁿ⁺¹. Therefore, the secrecy of K against the simple individual attack is proven.

It has been pointed out that a Grover-type 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 query-type 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 query-type algorithm. Although the difficulty has not been proven, it might be reduced to the difficulty of a well-known 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.