# Quantum Election Protocol Based on Quantum Public Key Cryptosystem

Authors: Wenhua Gao; Li Yang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

There is no quantum election protocol that can fulfil the eight requirements of an electronic election protocol, i.e., completeness, robustness, privacy, legality, unreusability, fairness, verifiability, and receipt-freeness. To address this issue, we employ the general construction of quantum digital signature and quantum public key encryption, in conjunction with classic public key encryption, to develop and instantiate a general construction of quantum election protocol. The proposed protocol exhibits the following advantages: (i) no pre-shared key between any two participants is required, and no trusted third party or anonymous channels are required. The protocol is suitable for large-scale elections with numerous candidates and voters and accommodates the situation in which multiple voters vote simultaneously. (ii) It is the first protocol that dismantles the contradiction between verifiability and receipt-freeness in a quantum election protocol. It satisfies all eight requirements stated earlier under the physical assumptions that there exists a one-way untappable channel from the administrator to the voter and that there is no collusion between any of the three parties in the protocol. Compared with current election protocols with verifiability and receipt-freeness, this protocol relies upon fewer physical assumptions. (iii) This construction is flexible and can be instantiated into an election scheme having post-quantum security by applying cryptographic algorithms conveying post-quantum security. Moreover, utilizing quantum digital signature and public key encryption yields a good result: the transmitted ballots are in quantum states, so owing to the no-cloning theorem, ballot privacy is less likely to be compromised, even if private keys of the signature and public key encryption are leaked after the election. However, in existing election protocols employing classic digital signatures and public key encryption, ballot privacy can be easily violated if attackers obtain private keys. Thus, our construction enhances privacy.


---

## Body

## 1. Introduction

We employ elections for various work- and life-related scenarios. There are several forms and numerous applications of elections, such as the elections of student cadres in universities, chairmen in companies, and presidents in countries. The aforementioned applications require strict and secure election protocols. Fair and reasonable election systems can accommodate the interests of all aspects of a society and reduce or prevent social conflicts and are conducive to the long-term stability of a society. Furthermore, security problems in elections may affect the stability of a group or even an entire society. Therefore, it is of great significance to study election protocols. With the rapid development of the information age, electronic elections are widely replacing traditional paper voting methods, as they are more in line with our everyday lives and work. Designing a secure and effective electronic election protocol is, at present, a prevalent research topic.Electronic elections generally consist of three parties: the voters, administrator, and counter. The role of the voter is to forward his/her ballot anonymously to the counter, who counts the ballots and publishes the election results on a bulletin board; the administrator is responsible for helping the election run smoothly. Ever since the concept of elections was first proposed, cryptographers have been committed to constructing a secure and practical election scheme. The first electronic election protocol was proposed by Chaum [1] in 1981, which was followed by numerous other classic electronic election protocols. These classic election protocols can be mainly divided into three categories: electronic election protocols based on hybrid networks [1–4], electronic election protocols based on homomorphic encryption [5–7], and electronic election protocols based on blind signatures [3, 8–10].Furthermore, for the security of election protocols, Fujioka et al. [9] proposed that a voting scheme should satisfy all of the following seven requirements. completeness: all valid votes are counted correctly by the system when all parties in the protocol are honest; robustness: inappropriate behaviour of dishonest participants or nonparticipants cannot undermine the conduct of the election, and the system is fault-tolerant; privacy: the vote message of the ballot is secret, and only the corresponding voter and the counter can know it. In addition, no one, except the voters themselves, can associate it with the corresponding voter identity; legality: only legitimate voters can vote; unreusability: no voter can vote twice; fairness: during the voting process, the statistics of the votes cast shall not be announced, because the intermediate results of the voting would affect the voting tendency of voters who have not yet voted; verifiability: voters can finally verify whether their votes have been counted correctly. Subsequently, in response to the possibility of vote-buying and coercive vote fraud in the election protocol, Benaloh et al. [11] proposed the requirement of receipt−freeness, that is, the voters cannot prove to a third party the content of their vote. This requirement prevents voters from being bribed or forced to vote. Owing to the contradiction between being receipt-free and verifiable, it is difficult to construct an electronic election with the receipt-freeness property. Presently known receipt-free election schemes are based on the physical assumption that the attackers cannot monitor when voters are voting, because if attackers can monitor, then receipt-free voting cannot be realized. We believe that this assumption is necessary for the receipt-freeness of an election. Most receipt-free classic elections are based on the physical assumption that there is a one-way or two-way untappable channel. In addition, some protocols [4] require large amounts of zero-knowledge proof, which reduces the efficiency of the protocol, while some protocols require an anonymous channel [10] or randomizer [7], which increases the complexity of the protocol.Most classic electronic election protocols are based on the difficulty assumptions of large integer decomposition or discrete logarithms. The development of quantum computers poses a considerable threat to the security of these protocols. Therefore, constructing quantum election protocols with the property of resisting quantum computer attacks has become a prevalent research topic. Current quantum election protocols are mainly classified into two types: entangled states-based protocols [12–20] and nonentangled states-based protocols [21–23]. Some entangled state-based protocols can only perform a binary vote for “yes” or “no” [13, 14, 16, 17], which is not suitable for scenarios with numerous candidates. Some nonentangled state-based protocols [22, 23] require numerous keys to be pre-shared among the participants. Furthermore, the current quantum election protocols cannot fulfil all eight electoral requirements mentioned above. A quantum election protocol that can resolve the contradiction between receipt-freeness and verifiability has not been developed yet.To solve the abovementioned problems, considering the advantages of the physical properties of quantum states in the context of an election protocol, we propose the general construction of a quantum election protocol. Our construction is flexible and can thus be instantiated into an election scheme having post-quantum security by applying cryptographic algorithms, which possess post-quantum security properties. The proposed protocol is suitable for scenarios with numerous candidates and can simultaneously achieve all eight election protocol requirements, i.e., completeness, robustness, privacy, legality, unreusability, fairness, receipt-freeness, and verifiability. Our protocol requires fewer assumptions as compared with the classic election protocol.


### 1.1. Our Contributions

In this study, we utilise the proposed general construction of quantum digital signature [24] and quantum public key encryption [25], in conjunction with classic public key encryption, to develop a general construction of a quantum election protocol.In our construction, we utilise public key cryptographic algorithms, so no pre-shared key is required for any two participants. The protocol can resist an attack from participants, so there is no need for a trusted third party. Anonymous channels are not required because ballots are delivered with the help of an administrator. The protocol is suitable for large-scale elections with numerous candidates and voters and can accommodate scenarios in which multiple voters vote simultaneously.The protocol is the first to resolve the conflict between verifiability and receipt-freeness in a quantum election protocol, simultaneously achieving completeness, robustness, privacy, legality, unreusability, fairness, verifiability, and receipt-freeness under only two physical assumptions. The first assumption is that there exists a one-way untappable channel from the administrator to the voter. The second assumption is that there is no collusion between any of the three parties in the protocol. In the actual elections, the administrator and the counter are generally composed of multiple people representing different interested parties; thus, their mutual supervision makes the second assumption easy to implement.We utilise quantum public key encryption [25] with information theory security, quantum digital signature [24] with post-quantum security, and classic public key encryption with post-quantum security to instantiate the proposed construction into election schemes with post-quantum security. In the existing election protocols with classic digital signature and public key encryption, the transmitted ballots are classic ciphertexts, and the attacker may intercept and copy the ciphertexts. Once the corresponding private keys are known in the future, the attacker could then decrypt the ciphertexts, thus violating the privacy of the ballots. However, in our construction, the use of quantum digital signature and public key encryption yields a good result: the transmitted votes are delivered in the form of quantum states, which are unknown to the attacker. Therefore, according to the no-cloning theorem, the privacy of the ballots is not compromised even if the corresponding private keys are leaked after the election is completed. As an added benefit, private keys do not need to be kept secret after the election is complete. Furthermore, the keys of the quantum digital signature are classic; thus, classic public key infrastructure (PKI) can be used for key management and distribution.


### 1.2. Outline of the Paper

The remainder of this paper is organised as follows: Section2 describes the basic knowledge and definitions of the cryptographic primitives used in the protocol, including public key encryptions and digital signatures, and presents two existing models for quantum public key encryption and quantum digital signatures. Section 3 describes the generic construction of the proposed quantum election. Section 4 analyses the security of the generic construction described in Section 3, including completeness, robustness, privacy, legality, unreusability, fairness, verifiability, and receipt-freeness. Section 5 instantiates the general construction of the election protocol into election schemes with post-quantum security by applying cryptographic algorithms with post-quantum security, analyses the efficiency of the instantiation, and compares the efficiency and security with current protocols. Section 6 summarises our work and presents directions for future work.


## 1.1. Our Contributions

In this study, we utilise the proposed general construction of quantum digital signature [24] and quantum public key encryption [25], in conjunction with classic public key encryption, to develop a general construction of a quantum election protocol.In our construction, we utilise public key cryptographic algorithms, so no pre-shared key is required for any two participants. The protocol can resist an attack from participants, so there is no need for a trusted third party. Anonymous channels are not required because ballots are delivered with the help of an administrator. The protocol is suitable for large-scale elections with numerous candidates and voters and can accommodate scenarios in which multiple voters vote simultaneously.The protocol is the first to resolve the conflict between verifiability and receipt-freeness in a quantum election protocol, simultaneously achieving completeness, robustness, privacy, legality, unreusability, fairness, verifiability, and receipt-freeness under only two physical assumptions. The first assumption is that there exists a one-way untappable channel from the administrator to the voter. The second assumption is that there is no collusion between any of the three parties in the protocol. In the actual elections, the administrator and the counter are generally composed of multiple people representing different interested parties; thus, their mutual supervision makes the second assumption easy to implement.We utilise quantum public key encryption [25] with information theory security, quantum digital signature [24] with post-quantum security, and classic public key encryption with post-quantum security to instantiate the proposed construction into election schemes with post-quantum security. In the existing election protocols with classic digital signature and public key encryption, the transmitted ballots are classic ciphertexts, and the attacker may intercept and copy the ciphertexts. Once the corresponding private keys are known in the future, the attacker could then decrypt the ciphertexts, thus violating the privacy of the ballots. However, in our construction, the use of quantum digital signature and public key encryption yields a good result: the transmitted votes are delivered in the form of quantum states, which are unknown to the attacker. Therefore, according to the no-cloning theorem, the privacy of the ballots is not compromised even if the corresponding private keys are leaked after the election is completed. As an added benefit, private keys do not need to be kept secret after the election is complete. Furthermore, the keys of the quantum digital signature are classic; thus, classic public key infrastructure (PKI) can be used for key management and distribution.


## 1.2. Outline of the Paper

The remainder of this paper is organised as follows: Section2 describes the basic knowledge and definitions of the cryptographic primitives used in the protocol, including public key encryptions and digital signatures, and presents two existing models for quantum public key encryption and quantum digital signatures. Section 3 describes the generic construction of the proposed quantum election. Section 4 analyses the security of the generic construction described in Section 3, including completeness, robustness, privacy, legality, unreusability, fairness, verifiability, and receipt-freeness. Section 5 instantiates the general construction of the election protocol into election schemes with post-quantum security by applying cryptographic algorithms with post-quantum security, analyses the efficiency of the instantiation, and compares the efficiency and security with current protocols. Section 6 summarises our work and presents directions for future work.


## 2. Preliminaries

For the remainder of this paper, we assume the reader is familiar with the basic notions and notation of quantum computing. These can be found in textbooks such as [26].Givenr and ∑mαmm as input, quantum transformation Uf computing a function f:0,1t×0,1n⟶0,1ℓ is defined as(1)Ufr∑mαmm0=r∑mαmm0⊕fr,m⟶r∑mαmmfr,m,where ⊕ denotes bitwise addition. In addition, when given r and ∑mαmmfr,m as input, we can use unitary transformation again and get(2)Ufr∑mαmmfr,m=r∑mαmm0⟶r∑mαmm0.Unitary transformation implemented via quantum circuits ofUf is shown in Figure 1.Figure 1
The quantum circuit implementation ofUf.


### 2.1. Public Key Encryption

Public key encryption algorithms enable participants to transfer information securely without sharing secret key. A classic public key encryptionPKE=Gen,Enc,Dec consists of three algorithms, a finite message space ℳ, and a ciphertext space C. The key generation algorithm takes a security parameter λ as input and outputs a key pair pkpke,skpke. The encryption algorithm Enc takes public key pkpke and a message m∈ℳ as input and outputs a ciphertext c∈C. The deterministic decryption algorithm Dec takes skpke and a ciphertext c as input and outputs either a message m=Decskpke,c∈ℳ or a special symbol ⊥ to indicate that c is not a valid ciphertext. For correctness, we require that Prm=Decskpke,c|c=Encpkpke,m=1−neglλ, where neglλ denotes a negligible function. We say that PKE is deterministic if Enc is deterministic, while PKE is probabilistic if Enc is probabilistic.


#### 2.1.1. Quantum Public Key Encryption

The difference between quantum and classic public key encryption is that several of the six elements, including public and private keys generated by the key generation algorithm, encryption algorithm, decryption algorithm, plaintext, and ciphertext, may be represented in quantum states.In 2000, Okamoto [27] proposed the concept of quantum public key encryption. Today, the existing quantum public key encryption schemes can be roughly classified into several categories according to different problems that schemes are based on coding [25, 28–32], quantum algorithms [27, 33], indistinguishable quantum states [34–37], induced trapdoor one-way transformations [24], quantum bit rotation [38–41], and interaction between bell state particles [42–46]. In 2015, Wu et al. [47] classified quantum public key encryption into 64 types, according to whether the six elements of public key encryption belong to quantum space or not.Liang et al. [36] gave a generic quantum public key encryption construction for encrypting classic messages, where a private key corresponds to an exponent of different public keys. Then, Yang et al. [25] slightly improved the abovementioned scheme by using two Boolean functions instead of using one Boolean function. Every public key in [25] is an unknown quantum state for anyone except its generator, so the ciphertext quantum state obtained by encrypting a plaintext is also unknown to its encrypting party. Moreover, every public key is in different quantum state. These may be useful to achieve the receipt-freeness of election protocol. We briefly recall their generic quantum public key encryption construction qPKE=qGen,qEnc,qDec. Let p denote the number of messages to be encrypted, and mi denote the i-th message for i∈1,2,…,p.(i)
qGen. (1) Randomly select two functions F1,F2 from a set of polynomial computable functions F:0,1n⟶0,1n. (2) For i∈1,2,…,p, randomly select and compute ki,1=F1gi and ki,2=F2gi. Then, the quantum state ψki,1,ki,2 can be efficiently prepared according to ki,1 and ki,2. (3) Upload all gi,ψki,1,ki,2 to the public key register. Function F1,F2 is the private key. (4) In a word, qGen1n⟶pk=pkii∈1,2,…,p,sk=F1,F2, where pki=gi,ψki,1,ki,2.(ii)
qEnc. (1) In order to encrypt the i-th message mi, download the i-th part of the classic and quantum public-key pair pki=gi,ψki,1,ki,2 from the public key register. (2) Encrypt the classic plaintext mi by computing ψki,1,ki,2mi=Eψki,1,ki,2,mi, where E is a quantum encryption transformation, then output the ciphertext c=gi,ψki,1,ki,2mi. (3) In a word, qEncpki,mi⟶c.(iii)
qDec. (1) Given a ciphertext c=gi,ψki,1,ki,2mi, use private key F1,F2 to compute ki,1=F1gi,ki,2=F2gi. (2) According to the value of ki,1,ki,2, use D to decrypt ψki,1,ki,2mi and obtain the message mi=Dki,1,ki,2,ψki,1,ki,2mi, where D is a quantum decryption transformation. (3) In a word, qDecsk,c=gi,ψki,1,ki,2mi⟶mi.


### 2.2. Digital Signature

A classic digital signature,Signature=KeyGen,Sign,Verf, consists of three algorithms and a finite message space ℳ. The key generation algorithm takes a security parameter λ as input and outputs a key pair vksig,sksig. The signature algorithm Sign takes the secret key sksig and a message m∈M as input and outputs a signature σ. The verification algorithm Verf inputs vksig and a pair m,σ and outputs a bit message comprising either zero or one (this means that σ is a legal signature of message m). For correctness, we require that, pr 1=VerfvKsig,m,σ∣σ=SignsKsig,m=1−neglλ where neglλ denotes a negligible function.


#### 2.2.1. Quantum Digital Signature

The difference between quantum and classic digital signature is that several of the six elements may be represented in quantum states. These elements include the signature key and the verification key generated by the key generation algorithm, the signature algorithm, the verification algorithm, the plaintext, and the signature results of the quantum digital signature. Because of the special properties of quantum states, it is difficult to achieve a true quantum digital signature, and most existing quantum digital signature schemes require the participation of arbitrators. Quantum digital signatures, such as classic digital signatures, achieve both the identity authentication of signer and the integrity verification of message.With the development of quantum computer and quantum communication, it is necessary to study quantum digital signature. In 2001, Gottesman and Chuang [48] firstly proposed a quantum digital signature scheme for signing classic message. Subsequently, some arbitrated quantum digital signature protocols requiring the participation of trusted third parties [49–54] were proposed in succession. In 2010, Yang et al. [24] proposed an interactive quantum digital signature protocol for signing quantum message based on induced trapdoor one-way transformations. This protocol exploits the nature of quantum entangled states, realising the identity authentication of signer and protecting the integrity of messages without the participation of arbitrators. Subsequently, several quantum digital signature protocols without quantum memory were proposed [55, 56], thus improving the practicability of quantum signatures.A general construction of quantum digital signature for signing quantum message is proposed by Yang et al. [24]. The signature scheme qSignature consists of three algorithms qKGen,qSign,qVerf which are described as follows:(i)
qKGen. Randomly select a trapdoor one-way function f:0,1t+n⟶0,1t′+n′ which has a trapdoor f−1. Then, f is the verification key and f−1 is the signature secret key. In a word, qKGen1t,1n,1t′,1n′⟶vksig=f,sksig=f−1.(ii)
qSign. The signer signs a n bits quantum message ψ=∑mαmm to the verifier as follows: (1) the verifier randomly generates a number rver∈0,1t′ and sends it to the signer. (2) The signer randomly generates a number rsig∈0,1n′ and computes f−1rver,rsig=r,r′, where r∈0,1t and r′∈0,1n. (3) Then, with r, the signer performs the quantum transformation Uf on the quantum message ψ0=∑mαmm0 and obtains(3)∑mαmm0⟶1∑mαmmfr,m,and sends quantum state∑mαmmfr,m to the verifier. (4) In a word, qSignsksig,ψ⟶σ, where(4)σ=rver,r,r′,∑mαmmfr,m.(iii)
qVerf. (1) The verifier tells the signer that they have received the quantum state. (2) The signer announces r and r′. (3) The verifier computes fr,r′ and checks whether the first t′ bits of fr,r′ equal rver. They then perform the transformation,(5)∑mαmmfr,m⟶2∑mαmm0,and measure the second quantum register. They accept the signature if and only if the second register is in state0. In a word, qVerfvksig,ψ,σ⟶1 if and only if the second register is in state 0.


## 2.1. Public Key Encryption

Public key encryption algorithms enable participants to transfer information securely without sharing secret key. A classic public key encryptionPKE=Gen,Enc,Dec consists of three algorithms, a finite message space ℳ, and a ciphertext space C. The key generation algorithm takes a security parameter λ as input and outputs a key pair pkpke,skpke. The encryption algorithm Enc takes public key pkpke and a message m∈ℳ as input and outputs a ciphertext c∈C. The deterministic decryption algorithm Dec takes skpke and a ciphertext c as input and outputs either a message m=Decskpke,c∈ℳ or a special symbol ⊥ to indicate that c is not a valid ciphertext. For correctness, we require that Prm=Decskpke,c|c=Encpkpke,m=1−neglλ, where neglλ denotes a negligible function. We say that PKE is deterministic if Enc is deterministic, while PKE is probabilistic if Enc is probabilistic.


### 2.1.1. Quantum Public Key Encryption

The difference between quantum and classic public key encryption is that several of the six elements, including public and private keys generated by the key generation algorithm, encryption algorithm, decryption algorithm, plaintext, and ciphertext, may be represented in quantum states.In 2000, Okamoto [27] proposed the concept of quantum public key encryption. Today, the existing quantum public key encryption schemes can be roughly classified into several categories according to different problems that schemes are based on coding [25, 28–32], quantum algorithms [27, 33], indistinguishable quantum states [34–37], induced trapdoor one-way transformations [24], quantum bit rotation [38–41], and interaction between bell state particles [42–46]. In 2015, Wu et al. [47] classified quantum public key encryption into 64 types, according to whether the six elements of public key encryption belong to quantum space or not.Liang et al. [36] gave a generic quantum public key encryption construction for encrypting classic messages, where a private key corresponds to an exponent of different public keys. Then, Yang et al. [25] slightly improved the abovementioned scheme by using two Boolean functions instead of using one Boolean function. Every public key in [25] is an unknown quantum state for anyone except its generator, so the ciphertext quantum state obtained by encrypting a plaintext is also unknown to its encrypting party. Moreover, every public key is in different quantum state. These may be useful to achieve the receipt-freeness of election protocol. We briefly recall their generic quantum public key encryption construction qPKE=qGen,qEnc,qDec. Let p denote the number of messages to be encrypted, and mi denote the i-th message for i∈1,2,…,p.(i)
qGen. (1) Randomly select two functions F1,F2 from a set of polynomial computable functions F:0,1n⟶0,1n. (2) For i∈1,2,…,p, randomly select and compute ki,1=F1gi and ki,2=F2gi. Then, the quantum state ψki,1,ki,2 can be efficiently prepared according to ki,1 and ki,2. (3) Upload all gi,ψki,1,ki,2 to the public key register. Function F1,F2 is the private key. (4) In a word, qGen1n⟶pk=pkii∈1,2,…,p,sk=F1,F2, where pki=gi,ψki,1,ki,2.(ii)
qEnc. (1) In order to encrypt the i-th message mi, download the i-th part of the classic and quantum public-key pair pki=gi,ψki,1,ki,2 from the public key register. (2) Encrypt the classic plaintext mi by computing ψki,1,ki,2mi=Eψki,1,ki,2,mi, where E is a quantum encryption transformation, then output the ciphertext c=gi,ψki,1,ki,2mi. (3) In a word, qEncpki,mi⟶c.(iii)
qDec. (1) Given a ciphertext c=gi,ψki,1,ki,2mi, use private key F1,F2 to compute ki,1=F1gi,ki,2=F2gi. (2) According to the value of ki,1,ki,2, use D to decrypt ψki,1,ki,2mi and obtain the message mi=Dki,1,ki,2,ψki,1,ki,2mi, where D is a quantum decryption transformation. (3) In a word, qDecsk,c=gi,ψki,1,ki,2mi⟶mi.


## 2.1.1. Quantum Public Key Encryption

The difference between quantum and classic public key encryption is that several of the six elements, including public and private keys generated by the key generation algorithm, encryption algorithm, decryption algorithm, plaintext, and ciphertext, may be represented in quantum states.In 2000, Okamoto [27] proposed the concept of quantum public key encryption. Today, the existing quantum public key encryption schemes can be roughly classified into several categories according to different problems that schemes are based on coding [25, 28–32], quantum algorithms [27, 33], indistinguishable quantum states [34–37], induced trapdoor one-way transformations [24], quantum bit rotation [38–41], and interaction between bell state particles [42–46]. In 2015, Wu et al. [47] classified quantum public key encryption into 64 types, according to whether the six elements of public key encryption belong to quantum space or not.Liang et al. [36] gave a generic quantum public key encryption construction for encrypting classic messages, where a private key corresponds to an exponent of different public keys. Then, Yang et al. [25] slightly improved the abovementioned scheme by using two Boolean functions instead of using one Boolean function. Every public key in [25] is an unknown quantum state for anyone except its generator, so the ciphertext quantum state obtained by encrypting a plaintext is also unknown to its encrypting party. Moreover, every public key is in different quantum state. These may be useful to achieve the receipt-freeness of election protocol. We briefly recall their generic quantum public key encryption construction qPKE=qGen,qEnc,qDec. Let p denote the number of messages to be encrypted, and mi denote the i-th message for i∈1,2,…,p.(i)
qGen. (1) Randomly select two functions F1,F2 from a set of polynomial computable functions F:0,1n⟶0,1n. (2) For i∈1,2,…,p, randomly select and compute ki,1=F1gi and ki,2=F2gi. Then, the quantum state ψki,1,ki,2 can be efficiently prepared according to ki,1 and ki,2. (3) Upload all gi,ψki,1,ki,2 to the public key register. Function F1,F2 is the private key. (4) In a word, qGen1n⟶pk=pkii∈1,2,…,p,sk=F1,F2, where pki=gi,ψki,1,ki,2.(ii)
qEnc. (1) In order to encrypt the i-th message mi, download the i-th part of the classic and quantum public-key pair pki=gi,ψki,1,ki,2 from the public key register. (2) Encrypt the classic plaintext mi by computing ψki,1,ki,2mi=Eψki,1,ki,2,mi, where E is a quantum encryption transformation, then output the ciphertext c=gi,ψki,1,ki,2mi. (3) In a word, qEncpki,mi⟶c.(iii)
qDec. (1) Given a ciphertext c=gi,ψki,1,ki,2mi, use private key F1,F2 to compute ki,1=F1gi,ki,2=F2gi. (2) According to the value of ki,1,ki,2, use D to decrypt ψki,1,ki,2mi and obtain the message mi=Dki,1,ki,2,ψki,1,ki,2mi, where D is a quantum decryption transformation. (3) In a word, qDecsk,c=gi,ψki,1,ki,2mi⟶mi.


## 2.2. Digital Signature

A classic digital signature,Signature=KeyGen,Sign,Verf, consists of three algorithms and a finite message space ℳ. The key generation algorithm takes a security parameter λ as input and outputs a key pair vksig,sksig. The signature algorithm Sign takes the secret key sksig and a message m∈M as input and outputs a signature σ. The verification algorithm Verf inputs vksig and a pair m,σ and outputs a bit message comprising either zero or one (this means that σ is a legal signature of message m). For correctness, we require that, pr 1=VerfvKsig,m,σ∣σ=SignsKsig,m=1−neglλ where neglλ denotes a negligible function.


### 2.2.1. Quantum Digital Signature

The difference between quantum and classic digital signature is that several of the six elements may be represented in quantum states. These elements include the signature key and the verification key generated by the key generation algorithm, the signature algorithm, the verification algorithm, the plaintext, and the signature results of the quantum digital signature. Because of the special properties of quantum states, it is difficult to achieve a true quantum digital signature, and most existing quantum digital signature schemes require the participation of arbitrators. Quantum digital signatures, such as classic digital signatures, achieve both the identity authentication of signer and the integrity verification of message.With the development of quantum computer and quantum communication, it is necessary to study quantum digital signature. In 2001, Gottesman and Chuang [48] firstly proposed a quantum digital signature scheme for signing classic message. Subsequently, some arbitrated quantum digital signature protocols requiring the participation of trusted third parties [49–54] were proposed in succession. In 2010, Yang et al. [24] proposed an interactive quantum digital signature protocol for signing quantum message based on induced trapdoor one-way transformations. This protocol exploits the nature of quantum entangled states, realising the identity authentication of signer and protecting the integrity of messages without the participation of arbitrators. Subsequently, several quantum digital signature protocols without quantum memory were proposed [55, 56], thus improving the practicability of quantum signatures.A general construction of quantum digital signature for signing quantum message is proposed by Yang et al. [24]. The signature scheme qSignature consists of three algorithms qKGen,qSign,qVerf which are described as follows:(i)
qKGen. Randomly select a trapdoor one-way function f:0,1t+n⟶0,1t′+n′ which has a trapdoor f−1. Then, f is the verification key and f−1 is the signature secret key. In a word, qKGen1t,1n,1t′,1n′⟶vksig=f,sksig=f−1.(ii)
qSign. The signer signs a n bits quantum message ψ=∑mαmm to the verifier as follows: (1) the verifier randomly generates a number rver∈0,1t′ and sends it to the signer. (2) The signer randomly generates a number rsig∈0,1n′ and computes f−1rver,rsig=r,r′, where r∈0,1t and r′∈0,1n. (3) Then, with r, the signer performs the quantum transformation Uf on the quantum message ψ0=∑mαmm0 and obtains(3)∑mαmm0⟶1∑mαmmfr,m,and sends quantum state∑mαmmfr,m to the verifier. (4) In a word, qSignsksig,ψ⟶σ, where(4)σ=rver,r,r′,∑mαmmfr,m.(iii)
qVerf. (1) The verifier tells the signer that they have received the quantum state. (2) The signer announces r and r′. (3) The verifier computes fr,r′ and checks whether the first t′ bits of fr,r′ equal rver. They then perform the transformation,(5)∑mαmmfr,m⟶2∑mαmm0,and measure the second quantum register. They accept the signature if and only if the second register is in state0. In a word, qVerfvksig,ψ,σ⟶1 if and only if the second register is in state 0.


## 2.2.1. Quantum Digital Signature

The difference between quantum and classic digital signature is that several of the six elements may be represented in quantum states. These elements include the signature key and the verification key generated by the key generation algorithm, the signature algorithm, the verification algorithm, the plaintext, and the signature results of the quantum digital signature. Because of the special properties of quantum states, it is difficult to achieve a true quantum digital signature, and most existing quantum digital signature schemes require the participation of arbitrators. Quantum digital signatures, such as classic digital signatures, achieve both the identity authentication of signer and the integrity verification of message.With the development of quantum computer and quantum communication, it is necessary to study quantum digital signature. In 2001, Gottesman and Chuang [48] firstly proposed a quantum digital signature scheme for signing classic message. Subsequently, some arbitrated quantum digital signature protocols requiring the participation of trusted third parties [49–54] were proposed in succession. In 2010, Yang et al. [24] proposed an interactive quantum digital signature protocol for signing quantum message based on induced trapdoor one-way transformations. This protocol exploits the nature of quantum entangled states, realising the identity authentication of signer and protecting the integrity of messages without the participation of arbitrators. Subsequently, several quantum digital signature protocols without quantum memory were proposed [55, 56], thus improving the practicability of quantum signatures.A general construction of quantum digital signature for signing quantum message is proposed by Yang et al. [24]. The signature scheme qSignature consists of three algorithms qKGen,qSign,qVerf which are described as follows:(i)
qKGen. Randomly select a trapdoor one-way function f:0,1t+n⟶0,1t′+n′ which has a trapdoor f−1. Then, f is the verification key and f−1 is the signature secret key. In a word, qKGen1t,1n,1t′,1n′⟶vksig=f,sksig=f−1.(ii)
qSign. The signer signs a n bits quantum message ψ=∑mαmm to the verifier as follows: (1) the verifier randomly generates a number rver∈0,1t′ and sends it to the signer. (2) The signer randomly generates a number rsig∈0,1n′ and computes f−1rver,rsig=r,r′, where r∈0,1t and r′∈0,1n. (3) Then, with r, the signer performs the quantum transformation Uf on the quantum message ψ0=∑mαmm0 and obtains(3)∑mαmm0⟶1∑mαmmfr,m,and sends quantum state∑mαmmfr,m to the verifier. (4) In a word, qSignsksig,ψ⟶σ, where(4)σ=rver,r,r′,∑mαmmfr,m.(iii)
qVerf. (1) The verifier tells the signer that they have received the quantum state. (2) The signer announces r and r′. (3) The verifier computes fr,r′ and checks whether the first t′ bits of fr,r′ equal rver. They then perform the transformation,(5)∑mαmmfr,m⟶2∑mαmm0,and measure the second quantum register. They accept the signature if and only if the second register is in state0. In a word, qVerfvksig,ψ,σ⟶1 if and only if the second register is in state 0.


## 3. Generic Construction of Quantum Election

In this section, we present a generic construction of quantum election protocol. Section3.1 gives an overview of the construction and Section 3.2 gives a more detailed description.


### 3.1. Overview of Our Construction

The proposed election protocol runs as follows. (1) A voter holds his/her vote message and performs quantum public key encryption on it by using the counter’s public key, obtaining the quantum ciphertext which is the ballot of the voter. (2) The ballot is signed by the voter and sent to the administrator. Then, the voter’s signature is verified by the administrator. (3) The ballot is signed by the administrator and sent to the counter. Then, the administrator’s signature is verified by the counter. (4) The ballot is decrypted by using the counter’s private key and verification information is generated by the counter. (5) The information is sent to the voter with the help of the administrator. Finally, the voter can verify whether his/her vote is counted correctly or not.


### 3.2. Our Concrete Construction

In this section, we give a detailed description of quantum election protocol which consists of four cryptography primitives: classic probabilistic public key encryptionpPKE=pGen,pEnc,pDec, classic deterministic public key encryption dPKE=dGen,dEnc,dDec, quantum digital signature qSignature=qKGen,qSign,qVerf, and quantum public key encryption qPKE=qGen,qEnc,qDec, where quantum public key encryption and quantum digital signature are two generic constructions proposed by Yang et al. [25] and Yang et al. [24], respectively. Please refer to Sections 2.1 and 2.2 for more details.


#### 3.2.1. Initialization

Letp denote the number of voters, and vi denote the i-th voter for i∈1,2,…,p. Let q denote the number of legitimate candidates, and Aj∈0,1n−s represent the identity of the j-th legitimate candidate for each j∈1,2,…,q. Moreover, let Admin represent the administrator and Counter represent the counter. In the protocol, each voter has a unique identity string denoted by idi, while Admin has an identity idad. Identity strings are publicly known. The participants carry on the following steps:(i)
Admin. (1) Admin runs the algorithm qKGen of qsignature and gets a pair of public and private keys fad,fad−1. (2) Admin runs the algorithm pGen of pPKE and gets a pair of public and private keys pkad,skad. (3) Admin runs the algorithm dGen of dPKE and gets a pair of public and private keys pkad′,skad′.(ii)
Counter. (1) In order to encrypt p messages, Counter runs the algorithm qGen of qPKE and gets a pair of public and private keys pkte,skte, where pkte=gi,ψki,1,ki,2i∈1,2,…,p and skte=F1,F2.(iii)
vi. vi runs the algorithm qKGen of qsignature and gets a pair of public and private keys fvi,fvi−1.


#### 3.2.2. Election

(1)
Preprocessing:Each voter randomly selects a public key from the quantum public key register. Taking the public keygi,ψki,1,ki,2 chosen by voter vi as an example and assuming that vi wants to vote for candidate Aj, vi carries on the following steps:(i)
vi downloads one classic and quantum public-key pair gi,ψki,1,ki,2 of Counter from the public key register.(ii)
vi generates a random string ei∈0,1s and selects a candidate Aj∈0,1n−s to make up a vote message Tji, where Tji=Aj‖ei∈0,1n represents a simple concatenation of Aj and ei.(iii)
By performing quantum encryption transformationqEnc on the vote message Tji, vi obtains ciphertext gi,ψki,1,ki,2Tji=qEncψki,1,ki,2,Tji. ψki,1,ki,2Tji is the quantum ballot and it is clear that it is an n-bit quantum superposition state which can be denoted as ∑mαmm.(2)
Ballot-casting from voter to administrator:This process is briefly illustrated in Figure2. For the purpose of authenticating the identity of vi and the integrity of ballot, the administrator Admin needs to mutually communicate with vi so that Admin can verify the correctness of the received signature sent by vi.(i)
Ifvi wants to vote, they will send their idi to Admin.(ii)
LetT denote the number of idi received by Admin at the same time. After receiving idi, Admin searches the local data set ID; if idi∈ID or T>1, the request for voting is rejected. Otherwise, Admin randomly generates radi,1∈0,1t′ and sends it to vi.(iii)
vi randomly generates a number rvi∈0,1n′ and computes fvi−1radi,1,rvi=ri,1,ri,1′, where ri,1∈0,1t and ri,1′∈0,1n.(iv)
Withri,1, vi performs the quantum transformation Ufvi on ψi,1=ψki,1,ki,2Tji0 and obtains ψi,2, where(6)ψi,1=∑mαmm0⟶Ufviψi,2=∑mαmmfviri,1,m.In a word,qSignfvi−1,ψki,1,ki,2Tji⟶σ, and it is easy to see that σ=radi,1,ri,1,ri,1′,ψi,2.(v)
By running the encryption algorithmpEnc, vi obtains classic ciphertext cvi⟶ad=pEncpkad,ri,1,ri,1′,gi. Then, vi sends cvi⟶ad,ψi,2,idi to Admin.(vi)
After receivingcvi⟶ad,ψi,2,idi from vi, Admin decrypts cvi⟶ad with their private key skad and obtains the plaintext ri,1,ri,1′,gi=pDecskad,cvi⟶ad. As a result, Admin can get the signature σ=radi,1,ri,1,ri,1′,ψi,2 of ψki,1,ki,2Tji,σ. If the output of qVerffvi,ψki,1,ki,2Tji,σ is equal to 1, Admin stores vi’s information idi,gi into their database. Note that in the computing process of qVerf, there exists the following operation to obtain quantum state:(7)ψi,2=∑mαmmfviri,1,m⟶Ufviψi,1=∑mαmm0.When all voters have completed this stage withAdmin, the protocol proceeds to the next stage.(3)
Ballot-casting from administrator to counter:This process is briefly illustrated in Figure3. For the purpose of authenticating the identity of Admin and the integrity of ballot, the Counter needs to mutually communicate with Admin so that Counter can verify the correctness of the received signature sent by Admin.(i)
IfAdmin wants to send vi’s ballot to Counter, they firstly send idad to Counter.(ii)
After receivingidad, Counter randomly generates rtei∈0,1t′ and sends it to Admin.(iii)
randomly generatesradi,2∈0,1n′ and computes fad−1rtei,radi,2=ri,2,ri,2′, where ri,2∈0,1t and ri,2′∈0,1n.(iv)
Withri,2, Admin performs the quantum transformation Ufad on ψi,1 and obtains ψi,3, where(8)ψi,1=∑mαmm0⟶Ufadψi,3=∑mαmmfadri,2,m.In a word,qSignfad−1,ψi,1⟶σad, and it is easy to see that σad=rtei,ri,2,ri,2′,ψi,3.(v)
Admin sends σad,gi to Counter.(vi)
If the output ofqVerffad,ψi,1,σad equals 1, Counter can make sure the identity of Admin. Note that in the process of the above computing qVerf, there exists the following operation to obtain quantum state ψi,1,(9)ψi,3=∑mαmmfadri,2,m⟶Ufadψi,1=∑mαmm0.(vii)
With the quantum stateψi,1=∑mαmm0, Counter can obtain voter vi’s ballot ψki,1,ki,2Tji=∑mαmm and can get the ciphertext c=gi,ψki,1,ki,2Tji.AfterCounter receives and verifies all voters’ ballots from Admin, the election enters the next stage.(4)
Ballot-counting and result-publishing:Given the quantum ciphertextsc=gi,ψki,1,ki,2Tji, Counterdecrypts it and publishes the election result.(i)
Counter decrypts the ciphertext c by using qDec, i.e., qDecsk,c=Tji=Aj‖ei.(ii)
If the pre-n−s bits of the decryption result do not represent a qualified candidate, Counter rejects the ballot. Otherwise, Counter accepts the decryption result Tji and corresponding gi.(iii)
After accepting all the decryption results fromp voters, Counter computes the voting result of every voter vi in the form of Aj‖ei⊕dEncpkad′,fi, where fi∈0,1s is generated randomly by Counter. Then, Counter collects all the voting results and publishes them on the bulletin board.(5)
Confirming vote and terminating the election:Counter sends message to vi with the help of Admin so that vi can verify whether their vote is counted correctly. Under the physical assumption that there is a one-way noneavesdropping channel from the administrator to the voter, the election satisfies the requirement of receipt−freeness.(i)
By running the encryption algorithmdEnc, Counter obtains cte⟶ad,i=dEncpkad′,ei⊕fi and sends cte⟶ad,i,gi to Admin.(ii)
Admin utilises gi as a label to find the corresponding vi and sends cte⟶ad,i to vi by the one-way untappable channel from Admin to vi.(iii)
When all voters receive the corresponding ciphertext,Admin announces their private key skad′. Then, vi obtains ei⊕fi=dDecskad′,cte⟶ad,i. Finally, vi gets fi with the knowledge of ei. With ei and fi, vi can compute and obtain Aj‖ei⊕dEncpkad′,fi. Then, vi can verify whether they have successfully voted. If vi does not succeed in the verification, they can request a reelection. If all voters can make sure that their votes have been successfully voted, the election is complete and terminated.Figure 2
Ballot-casting from voter to administrator.Figure 3
Ballot-casting from administrator to counter.


## 3.1. Overview of Our Construction

The proposed election protocol runs as follows. (1) A voter holds his/her vote message and performs quantum public key encryption on it by using the counter’s public key, obtaining the quantum ciphertext which is the ballot of the voter. (2) The ballot is signed by the voter and sent to the administrator. Then, the voter’s signature is verified by the administrator. (3) The ballot is signed by the administrator and sent to the counter. Then, the administrator’s signature is verified by the counter. (4) The ballot is decrypted by using the counter’s private key and verification information is generated by the counter. (5) The information is sent to the voter with the help of the administrator. Finally, the voter can verify whether his/her vote is counted correctly or not.


## 3.2. Our Concrete Construction

In this section, we give a detailed description of quantum election protocol which consists of four cryptography primitives: classic probabilistic public key encryptionpPKE=pGen,pEnc,pDec, classic deterministic public key encryption dPKE=dGen,dEnc,dDec, quantum digital signature qSignature=qKGen,qSign,qVerf, and quantum public key encryption qPKE=qGen,qEnc,qDec, where quantum public key encryption and quantum digital signature are two generic constructions proposed by Yang et al. [25] and Yang et al. [24], respectively. Please refer to Sections 2.1 and 2.2 for more details.


### 3.2.1. Initialization

Letp denote the number of voters, and vi denote the i-th voter for i∈1,2,…,p. Let q denote the number of legitimate candidates, and Aj∈0,1n−s represent the identity of the j-th legitimate candidate for each j∈1,2,…,q. Moreover, let Admin represent the administrator and Counter represent the counter. In the protocol, each voter has a unique identity string denoted by idi, while Admin has an identity idad. Identity strings are publicly known. The participants carry on the following steps:(i)
Admin. (1) Admin runs the algorithm qKGen of qsignature and gets a pair of public and private keys fad,fad−1. (2) Admin runs the algorithm pGen of pPKE and gets a pair of public and private keys pkad,skad. (3) Admin runs the algorithm dGen of dPKE and gets a pair of public and private keys pkad′,skad′.(ii)
Counter. (1) In order to encrypt p messages, Counter runs the algorithm qGen of qPKE and gets a pair of public and private keys pkte,skte, where pkte=gi,ψki,1,ki,2i∈1,2,…,p and skte=F1,F2.(iii)
vi. vi runs the algorithm qKGen of qsignature and gets a pair of public and private keys fvi,fvi−1.


### 3.2.2. Election

(1)
Preprocessing:Each voter randomly selects a public key from the quantum public key register. Taking the public keygi,ψki,1,ki,2 chosen by voter vi as an example and assuming that vi wants to vote for candidate Aj, vi carries on the following steps:(i)
vi downloads one classic and quantum public-key pair gi,ψki,1,ki,2 of Counter from the public key register.(ii)
vi generates a random string ei∈0,1s and selects a candidate Aj∈0,1n−s to make up a vote message Tji, where Tji=Aj‖ei∈0,1n represents a simple concatenation of Aj and ei.(iii)
By performing quantum encryption transformationqEnc on the vote message Tji, vi obtains ciphertext gi,ψki,1,ki,2Tji=qEncψki,1,ki,2,Tji. ψki,1,ki,2Tji is the quantum ballot and it is clear that it is an n-bit quantum superposition state which can be denoted as ∑mαmm.(2)
Ballot-casting from voter to administrator:This process is briefly illustrated in Figure2. For the purpose of authenticating the identity of vi and the integrity of ballot, the administrator Admin needs to mutually communicate with vi so that Admin can verify the correctness of the received signature sent by vi.(i)
Ifvi wants to vote, they will send their idi to Admin.(ii)
LetT denote the number of idi received by Admin at the same time. After receiving idi, Admin searches the local data set ID; if idi∈ID or T>1, the request for voting is rejected. Otherwise, Admin randomly generates radi,1∈0,1t′ and sends it to vi.(iii)
vi randomly generates a number rvi∈0,1n′ and computes fvi−1radi,1,rvi=ri,1,ri,1′, where ri,1∈0,1t and ri,1′∈0,1n.(iv)
Withri,1, vi performs the quantum transformation Ufvi on ψi,1=ψki,1,ki,2Tji0 and obtains ψi,2, where(6)ψi,1=∑mαmm0⟶Ufviψi,2=∑mαmmfviri,1,m.In a word,qSignfvi−1,ψki,1,ki,2Tji⟶σ, and it is easy to see that σ=radi,1,ri,1,ri,1′,ψi,2.(v)
By running the encryption algorithmpEnc, vi obtains classic ciphertext cvi⟶ad=pEncpkad,ri,1,ri,1′,gi. Then, vi sends cvi⟶ad,ψi,2,idi to Admin.(vi)
After receivingcvi⟶ad,ψi,2,idi from vi, Admin decrypts cvi⟶ad with their private key skad and obtains the plaintext ri,1,ri,1′,gi=pDecskad,cvi⟶ad. As a result, Admin can get the signature σ=radi,1,ri,1,ri,1′,ψi,2 of ψki,1,ki,2Tji,σ. If the output of qVerffvi,ψki,1,ki,2Tji,σ is equal to 1, Admin stores vi’s information idi,gi into their database. Note that in the computing process of qVerf, there exists the following operation to obtain quantum state:(7)ψi,2=∑mαmmfviri,1,m⟶Ufviψi,1=∑mαmm0.When all voters have completed this stage withAdmin, the protocol proceeds to the next stage.(3)
Ballot-casting from administrator to counter:This process is briefly illustrated in Figure3. For the purpose of authenticating the identity of Admin and the integrity of ballot, the Counter needs to mutually communicate with Admin so that Counter can verify the correctness of the received signature sent by Admin.(i)
IfAdmin wants to send vi’s ballot to Counter, they firstly send idad to Counter.(ii)
After receivingidad, Counter randomly generates rtei∈0,1t′ and sends it to Admin.(iii)
randomly generatesradi,2∈0,1n′ and computes fad−1rtei,radi,2=ri,2,ri,2′, where ri,2∈0,1t and ri,2′∈0,1n.(iv)
Withri,2, Admin performs the quantum transformation Ufad on ψi,1 and obtains ψi,3, where(8)ψi,1=∑mαmm0⟶Ufadψi,3=∑mαmmfadri,2,m.In a word,qSignfad−1,ψi,1⟶σad, and it is easy to see that σad=rtei,ri,2,ri,2′,ψi,3.(v)
Admin sends σad,gi to Counter.(vi)
If the output ofqVerffad,ψi,1,σad equals 1, Counter can make sure the identity of Admin. Note that in the process of the above computing qVerf, there exists the following operation to obtain quantum state ψi,1,(9)ψi,3=∑mαmmfadri,2,m⟶Ufadψi,1=∑mαmm0.(vii)
With the quantum stateψi,1=∑mαmm0, Counter can obtain voter vi’s ballot ψki,1,ki,2Tji=∑mαmm and can get the ciphertext c=gi,ψki,1,ki,2Tji.AfterCounter receives and verifies all voters’ ballots from Admin, the election enters the next stage.(4)
Ballot-counting and result-publishing:Given the quantum ciphertextsc=gi,ψki,1,ki,2Tji, Counterdecrypts it and publishes the election result.(i)
Counter decrypts the ciphertext c by using qDec, i.e., qDecsk,c=Tji=Aj‖ei.(ii)
If the pre-n−s bits of the decryption result do not represent a qualified candidate, Counter rejects the ballot. Otherwise, Counter accepts the decryption result Tji and corresponding gi.(iii)
After accepting all the decryption results fromp voters, Counter computes the voting result of every voter vi in the form of Aj‖ei⊕dEncpkad′,fi, where fi∈0,1s is generated randomly by Counter. Then, Counter collects all the voting results and publishes them on the bulletin board.(5)
Confirming vote and terminating the election:Counter sends message to vi with the help of Admin so that vi can verify whether their vote is counted correctly. Under the physical assumption that there is a one-way noneavesdropping channel from the administrator to the voter, the election satisfies the requirement of receipt−freeness.(i)
By running the encryption algorithmdEnc, Counter obtains cte⟶ad,i=dEncpkad′,ei⊕fi and sends cte⟶ad,i,gi to Admin.(ii)
Admin utilises gi as a label to find the corresponding vi and sends cte⟶ad,i to vi by the one-way untappable channel from Admin to vi.(iii)
When all voters receive the corresponding ciphertext,Admin announces their private key skad′. Then, vi obtains ei⊕fi=dDecskad′,cte⟶ad,i. Finally, vi gets fi with the knowledge of ei. With ei and fi, vi can compute and obtain Aj‖ei⊕dEncpkad′,fi. Then, vi can verify whether they have successfully voted. If vi does not succeed in the verification, they can request a reelection. If all voters can make sure that their votes have been successfully voted, the election is complete and terminated.Figure 2
Ballot-casting from voter to administrator.Figure 3
Ballot-casting from administrator to counter.


## 3.2.1. Initialization

Letp denote the number of voters, and vi denote the i-th voter for i∈1,2,…,p. Let q denote the number of legitimate candidates, and Aj∈0,1n−s represent the identity of the j-th legitimate candidate for each j∈1,2,…,q. Moreover, let Admin represent the administrator and Counter represent the counter. In the protocol, each voter has a unique identity string denoted by idi, while Admin has an identity idad. Identity strings are publicly known. The participants carry on the following steps:(i)
Admin. (1) Admin runs the algorithm qKGen of qsignature and gets a pair of public and private keys fad,fad−1. (2) Admin runs the algorithm pGen of pPKE and gets a pair of public and private keys pkad,skad. (3) Admin runs the algorithm dGen of dPKE and gets a pair of public and private keys pkad′,skad′.(ii)
Counter. (1) In order to encrypt p messages, Counter runs the algorithm qGen of qPKE and gets a pair of public and private keys pkte,skte, where pkte=gi,ψki,1,ki,2i∈1,2,…,p and skte=F1,F2.(iii)
vi. vi runs the algorithm qKGen of qsignature and gets a pair of public and private keys fvi,fvi−1.


## 3.2.2. Election

(1)
Preprocessing:Each voter randomly selects a public key from the quantum public key register. Taking the public keygi,ψki,1,ki,2 chosen by voter vi as an example and assuming that vi wants to vote for candidate Aj, vi carries on the following steps:(i)
vi downloads one classic and quantum public-key pair gi,ψki,1,ki,2 of Counter from the public key register.(ii)
vi generates a random string ei∈0,1s and selects a candidate Aj∈0,1n−s to make up a vote message Tji, where Tji=Aj‖ei∈0,1n represents a simple concatenation of Aj and ei.(iii)
By performing quantum encryption transformationqEnc on the vote message Tji, vi obtains ciphertext gi,ψki,1,ki,2Tji=qEncψki,1,ki,2,Tji. ψki,1,ki,2Tji is the quantum ballot and it is clear that it is an n-bit quantum superposition state which can be denoted as ∑mαmm.(2)
Ballot-casting from voter to administrator:This process is briefly illustrated in Figure2. For the purpose of authenticating the identity of vi and the integrity of ballot, the administrator Admin needs to mutually communicate with vi so that Admin can verify the correctness of the received signature sent by vi.(i)
Ifvi wants to vote, they will send their idi to Admin.(ii)
LetT denote the number of idi received by Admin at the same time. After receiving idi, Admin searches the local data set ID; if idi∈ID or T>1, the request for voting is rejected. Otherwise, Admin randomly generates radi,1∈0,1t′ and sends it to vi.(iii)
vi randomly generates a number rvi∈0,1n′ and computes fvi−1radi,1,rvi=ri,1,ri,1′, where ri,1∈0,1t and ri,1′∈0,1n.(iv)
Withri,1, vi performs the quantum transformation Ufvi on ψi,1=ψki,1,ki,2Tji0 and obtains ψi,2, where(6)ψi,1=∑mαmm0⟶Ufviψi,2=∑mαmmfviri,1,m.In a word,qSignfvi−1,ψki,1,ki,2Tji⟶σ, and it is easy to see that σ=radi,1,ri,1,ri,1′,ψi,2.(v)
By running the encryption algorithmpEnc, vi obtains classic ciphertext cvi⟶ad=pEncpkad,ri,1,ri,1′,gi. Then, vi sends cvi⟶ad,ψi,2,idi to Admin.(vi)
After receivingcvi⟶ad,ψi,2,idi from vi, Admin decrypts cvi⟶ad with their private key skad and obtains the plaintext ri,1,ri,1′,gi=pDecskad,cvi⟶ad. As a result, Admin can get the signature σ=radi,1,ri,1,ri,1′,ψi,2 of ψki,1,ki,2Tji,σ. If the output of qVerffvi,ψki,1,ki,2Tji,σ is equal to 1, Admin stores vi’s information idi,gi into their database. Note that in the computing process of qVerf, there exists the following operation to obtain quantum state:(7)ψi,2=∑mαmmfviri,1,m⟶Ufviψi,1=∑mαmm0.When all voters have completed this stage withAdmin, the protocol proceeds to the next stage.(3)
Ballot-casting from administrator to counter:This process is briefly illustrated in Figure3. For the purpose of authenticating the identity of Admin and the integrity of ballot, the Counter needs to mutually communicate with Admin so that Counter can verify the correctness of the received signature sent by Admin.(i)
IfAdmin wants to send vi’s ballot to Counter, they firstly send idad to Counter.(ii)
After receivingidad, Counter randomly generates rtei∈0,1t′ and sends it to Admin.(iii)
randomly generatesradi,2∈0,1n′ and computes fad−1rtei,radi,2=ri,2,ri,2′, where ri,2∈0,1t and ri,2′∈0,1n.(iv)
Withri,2, Admin performs the quantum transformation Ufad on ψi,1 and obtains ψi,3, where(8)ψi,1=∑mαmm0⟶Ufadψi,3=∑mαmmfadri,2,m.In a word,qSignfad−1,ψi,1⟶σad, and it is easy to see that σad=rtei,ri,2,ri,2′,ψi,3.(v)
Admin sends σad,gi to Counter.(vi)
If the output ofqVerffad,ψi,1,σad equals 1, Counter can make sure the identity of Admin. Note that in the process of the above computing qVerf, there exists the following operation to obtain quantum state ψi,1,(9)ψi,3=∑mαmmfadri,2,m⟶Ufadψi,1=∑mαmm0.(vii)
With the quantum stateψi,1=∑mαmm0, Counter can obtain voter vi’s ballot ψki,1,ki,2Tji=∑mαmm and can get the ciphertext c=gi,ψki,1,ki,2Tji.AfterCounter receives and verifies all voters’ ballots from Admin, the election enters the next stage.(4)
Ballot-counting and result-publishing:Given the quantum ciphertextsc=gi,ψki,1,ki,2Tji, Counterdecrypts it and publishes the election result.(i)
Counter decrypts the ciphertext c by using qDec, i.e., qDecsk,c=Tji=Aj‖ei.(ii)
If the pre-n−s bits of the decryption result do not represent a qualified candidate, Counter rejects the ballot. Otherwise, Counter accepts the decryption result Tji and corresponding gi.(iii)
After accepting all the decryption results fromp voters, Counter computes the voting result of every voter vi in the form of Aj‖ei⊕dEncpkad′,fi, where fi∈0,1s is generated randomly by Counter. Then, Counter collects all the voting results and publishes them on the bulletin board.(5)
Confirming vote and terminating the election:Counter sends message to vi with the help of Admin so that vi can verify whether their vote is counted correctly. Under the physical assumption that there is a one-way noneavesdropping channel from the administrator to the voter, the election satisfies the requirement of receipt−freeness.(i)
By running the encryption algorithmdEnc, Counter obtains cte⟶ad,i=dEncpkad′,ei⊕fi and sends cte⟶ad,i,gi to Admin.(ii)
Admin utilises gi as a label to find the corresponding vi and sends cte⟶ad,i to vi by the one-way untappable channel from Admin to vi.(iii)
When all voters receive the corresponding ciphertext,Admin announces their private key skad′. Then, vi obtains ei⊕fi=dDecskad′,cte⟶ad,i. Finally, vi gets fi with the knowledge of ei. With ei and fi, vi can compute and obtain Aj‖ei⊕dEncpkad′,fi. Then, vi can verify whether they have successfully voted. If vi does not succeed in the verification, they can request a reelection. If all voters can make sure that their votes have been successfully voted, the election is complete and terminated.Figure 2
Ballot-casting from voter to administrator.Figure 3
Ballot-casting from administrator to counter.


## 4. Security Analysis

We assume that there exists no collusion between any two of the three parties in the protocol. In actual elections, the administrator and the counter are generally composed of multiple people representing different interest groups, so their mutual supervision makes this assumption easy to hold. Both participants and nonparticipants can potentially attack the protocol. We define an attack from participants as an internal attack and an attack from nonparticipants as an external attack. In this section, we prove that our proposed election protocol satisfies the eight requirements, namely, completeness, robustness, privacy, legality, unreusability, fairness, verifiability, and receipt-freeness.


### 4.1. Completeness

Theorem 1.
(completeness). In the protocol, all valid votes are counted correctly when all participants are honest.Proof.
(sketch). According to the definition of completeness, all valid votes are counted correctly when all parties in the protocol are honest. A qualified votervi for i∈1,2,…,p encrypts the vote message Aj‖ei which is a simple concatenation of binary string Aj, representing a legal candidate and binary string ei generated randomly by vi, with a classic and quantum public-key pair gi,ψki,1,ki,2 which is selected randomly by vi from Counter’s public key pool. After the ballot ψki1,ki2Tji is signed and verified twice, Counter finally obtains the ciphertext gi,ψki1,ki2Tji. Then, Counter can obtain the vote message of vi’s ballot by decrypting the ciphertext with their private key F1,F2. Hence, it is clear that the proposed protocol satisfies completeness.


### 4.2. Robustness

Theorem 2.
(robustness). The inappropriate behaviour of dishonest participants or nonparticipants cannot disrupt the election; i.e., the protocol is fault-tolerant.Proof.
We analyse the robustness of the protocol by considering the inappropriate behaviour of participants including voters, administrator and counter, and nonparticipants.(i)
When a dishonest votervj seeks to disrupt the election, they may have three strategies. In the first case, vj does not vote, that is, in the ballot-casting from voter to administrator stage, vj does not send idj or cvj⟶ad,ψj,2,idj to Admin. However, it is clear that Admin will be aware of this missing vote. In the second case, vj sends an invalid message group cvj⟶ad,ψj,2,idjfalse to Admin in the ballot-casting from voter to administrator stage. While the running result of qVerf achieved by Admin will not equal 1, this wrong action will be detected by. In the third case, vj generates a random binary string Afalse, which does not represent a qualified candidate and encrypts Afalse||ej with Counter’s public key gj,ψkj,1,kj,2. However, Counter will find out the illegal Afalse in the ballot-counting and result-publishing stage and reject the ballot. In a word, the voter vj cannot succeed in disrupting the election.(ii)
If the internal attackerAdmin wants to disrupt the election, they may have two strategies. In the first case, Admin tampers with the quantum state ψi,1 from a legitimate voter vi in the ballot-casting from administrator to counter stage. However, because Admin does not know the candidate that vi is going to vote for, their random tampering will result in a random decrypting of the result obtained by Counter in the ballot-counting and result-publishing stage. Then, Counter will reject the ballot with a high probability. Because the probability that Admin successfully guesses the candidate that is voted for by vi is 1/q, the probability that they correctly tamper with the quantum state is also 1/q. Then, the probability that the decrypted result obtained by Counter represents a legitimate candidate is also 1/q, so the probability that the ballot is rejected in the ballot-counting and result-publishing stage by Counter is q−1/q. In addition, even if the tampered ballot is accepted by Counter, vi can be aware that their vote is not counted correctly in the confirming vote and terminating the election stage. Then, vi can request a reelection. In the second case, Admin may substitute the quantum state ψi,1. In this manner, Counter will accept the decrypted result, but vi will find that their vote has not been counted correctly during the confirming vote and terminating the election stage, and they can request a reelection.(iii)
IfCounter wants to destroy the election, they may modify the vote message of the accepted ballot and then publish the modified result in the ballot-counting and result-publishing stage. Suppose that Counter tampers with the vote message Aj‖ei of eligible voter vi to Aj′‖ei. To be unnoticed by vi, Counter must send a ffalse so that vi can verify their vote successfully. To achieve that, Counter can find another vote message, such as Aj‖eo, which is chosen by another legal voter vo and make ffalse satisfy ei⊕dEncpkad′,ffalse=eo⊕dEncpkad′,fo. However, because Counter does not have Admin’s private key skad′, it is difficult for Counter to provide a ffalse that can make vi verify their vote message on the bulletin board successfully. Therefore, the misbehaviour of Counter cannot be successful if the classic deterministic public key encryption dPKE is secure.(iv)
If external attackers want to tamper with the ballot from a legitimate votervi, they can only attack during the transmission of cvi⟶ad,ψi,2,idi in the ballot-casting from voter to administrator stage or during the transmission of σad,gi in the ballot-casting from administrator to counter stage. However, the security of the quantum signature algorithm qSignature enables this attack to be detected by Admin or Counter.
Hence, the protocol is robust.


### 4.3. Privacy

Theorem 3.
(privacy). In the protocol, the vote message of the ballot is secret, and only the corresponding voter and the counter can know it. In addition, no one except the voters themselves can associate it with the corresponding voter identity.Proof.
Nonparticipants of the protocol, the administrator, and the counter are all likely to attack the privacy of ballots, so we analyse the three cases in turn. Meanwhile, to prove our election can achieve privacy, we use the no-cloning theorem [57], which states that an exact copy of an unknown quantum state is impossible to achieve in quantum mechanics.(i)
Resistance to attacks from nonparticipants: if a nonparticipant of the protocol wants to attack the privacy ofvi’s ballot, the only possible opportunity occurs during the transmission of information in the ballot-casting from voter to administrator stage and ballot-casting from administrator to counter stage. Assuming that the attacker intercepts cvi⟶ad,ψi,2,idi in the ballot-casting from voter to administrator stage, the security of pPKE ensures that the attackers cannot decrypt cvi⟶ad to obtain ri,1,ri,1′,gi and cannot obtain the signature σ=radi,1,ri,1,ri,1′,ψi,2 of ψki,1,ki,2Tji. Then, the attacker cannot untangle quantum state ψi,2 to obtain ψi,1 and the ciphertext c=gi,ψki,1,ki,2Tji, let alone obtain the vote message of the ballot, because they do not know Counter’s private key F1,F2. Moreover, if the transmitted ballot is classic, the attacker may copy it during its transmission. Once the corresponding private keys are known in the future, the attacker could then violate the privacy of the ballot. However, in our construction, the ballot is transmitted in the form of a quantum state, and ψi,2 is unknown to the attacker. Owing to the no-cloning theorem, after the election is completed, even if the private keys F1,F2 and skad are leaked, the privacy of the ballots is not compromised. If the attacker intercepts σad,gi in the ballot-casting from administrator to counter stage, they can untangle ψi,3 with ri,2 to obtain ψi,1 and the ciphertext c=gi,ψki,1,ki,2Tji. However, they cannot decrypt the ciphertext to obtain vi’s vote message, because the attacker does not know Counter’s private key F1,F2. In this case, ψi,1 is unknown to the attacker. Thus, the attacker cannot copy this state and obtain the vote message of the ballot even if the private key F1,F2 is leaked after the election.(ii)
Resistance to an attack fromAdmin: Admin can obtain the ciphertext c=gi,ψki,1,ki,2Tji in the stage of ballot-casting from voter to administrator, but the security of qPKE ensures that they cannot obtain the vote message of the ballot, because Counter’s private key F1,F2 is unknown. Similar to the earlier analysis, c=gi,ψki,1,ki,2Tji is unknown to Admin, so they cannot copy the ciphertext c. Going further, they cannot obtain the vote message of the ballot even if the private key F1,F2 is leaked after the election.(iii)
Resistance to an attack fromCounter: if Counter wants to attack the privacy of vi’s ballot, they may attack in the stages of ballot-casting from voter to administrator and ballot-casting from administrator to counter. In the stage of ballot-casting from voter to administrator, Counter may intercept cvi⟶ad,ψi,2,idi during the transformation and attempt to obtain vi’s vote message via the intercepted information. However, similar to this type of attack from nonparticipants, the security of pPKE ensures that Counter cannot obtain ri,1,ri,1′,gi and obtain the signature σ=radi,1,ri,1,ri,1′,ψi,2 of ψki,1,ki,2Tji. Thus, Counter cannot untangle quantum state ψi,2 to obtain ψi,1 and the ciphertext c=gi,ψki,1,ki,2Tji. Therefore, it is impossible for Counter to use the private key F1,F2 to decrypt the ciphertext to obtain vi’s vote message. In this stage, ψi,2 is unknown to Counter; thus, they cannot copy it and associate vi′s ballot content with vi’s identity even if Admin’s private key skad is leaked after the election. Moreover, it is worth noting that Counter cannot utilise gi, which is obtained in the stage of ballot-casting from administrator to counter, as a label of vi′s identity to associate vi′s vote message with vi’s identity because gi is encrypted by pPKE in the stage of ballot-casting from voter to administrator. In the stage of ballot-casting from administrator to counter, even though Counter can finally obtain vi’s vote message, they do not know which voter the decrypted ballot comes from because Admin replaces the voter identity idi with gi at this stage.
As a result, the protocol can satisfy the privacy requirement during an election, and the privacy will not be threatened even if corresponding private keys are leaked after the election.


### 4.4. Legality

Theorem 4.
(legality). In the protocol, only legitimate voters can vote.Proof.
(sketch). The security ofqSignature ensures that only the vote cast by a legitimate voter vi for i∈1,2,…,p can be accepted. In the stage of ballot-casting from voter to administrator, vi performs the quantum algorithm to sign their ballot ψki,1,ki,2Tji with their private key fvi−1, i.e., qSignfvi−1,ψki,1,ki,2Tji⟶σ. Then,Admin verifies the signature with vi’s public key fvi, i.e., qVerffvi,ψki,1,ki,2Tji,σ. The Admin accepts the information from vi only if the output of qVerf equals 1, which ensures that Admin only accepts the ballot from legitimate voter vi. Similarly, Counter only accepts the ballot from Admin. Therefore, only legitimate voters can vote successfully.


### 4.5. Unreusability

Theorem 5.
(unreusability). In the protocol, no voter can vote twice.Proof.
(sketch). In the stage of ballot-casting from voter to administrator, if the legal votervi wants to vote, they send idi Admin to first. The condition that idi∉ID and T≤1 ensures that Admin accepts idi only once, so vi can vote only once. Furthermore, in the case where voter vi pretends to be another legitimate voter vi′ and sends idi′ to Admin, the illegal ballot from vi will not be accepted by Admin because vi has no private key fvi′−1 and the security of qSignature ensures that the output of quantum verification algorithm qVerf is not 1. Thus, one legal voter can vote only once.


### 4.6. Fairness

Theorem 6.
(fairness). In the protocol, the intermediate results of the voting do not affect the preference of those who have not yet voted.Proof.
(sketch). After accepting all the vote messages fromq voters, Counter collects the voting result of every voter and then publishes all results on the bulletin board in the stage of ballot-counting and result-publishing. Therefore, no one can obtain the intermediate results of the election, and the protocol is fair.


### 4.7. Verifiability

Theorem 7.
(verifiability). In the protocol, voters can finally verify whether their votes have been counted correctly.Proof.
(sketch).Counter announces the voting result of every voter vi in the form of Aj||ei⊕dEncpkad′,fi. Subsequently, running the encryption algorithm dEnc, Counter obtains cte⟶ad,i=dEncpkad′,ei⊕fi; they then send cte⟶ad,i to vi with the help of Admin. After vi receives it, Admin publishes their private key skad′. Running the decryption algorithm dDec, vi obtains ei⊕fi=dDecskad′,cte⟶ad,i. vi obtains fi with the knowledge of ei. With ei, fi, and pkad′, vi can compute ei⊕dEncpkad′,fi. By searching for ei⊕dEncpkad′,fi on the bulletin board and verifying whether the candidate information corresponding to ei⊕dEncpkad′,fi is Aj, vi can verify whether their vote has been counted correctly.


### 4.8. Receipt-Freeness

Theorem 8.
(receipt-freeness). In the protocol, the voter cannot prove to a third party the content of their vote.Proof.
The protocol can achieve receipt-freeness under the physical assumption that there is a one-way untappable channel from the authority (i.e., the administrator) to the voter [4, 58]. By a standard exclusive-OR trick, this assumption can be implemented by having a number of one-way channels, assuming that the adversary cannot simultaneously tap every one of them [4].
Suppose that votervi wants to vote for candidate Aj, while there is a briber who requires vi to vote for candidate Aa. In this protocol, under the premise that the number of ballots for candidate Aa displayed on the bulletin board does not affect the judgment of the briber (for example, the number of votes for candidate Aa is zero, and this case can be ignored in a large-scale election), and vi can vote for candidate according to their preferences, but lie to the briber successfully by providing the briber with false evidence to prove that they voted for candidate Aa.
In the pre-voting stage, the briber may have asked voter to provideei as evidence for future verification. In this stage, vi performs quantum encryption transformation qEnc on Tji, obtaining the ciphertext gi,ψki,1,ki,2Tji=qEncψki,1,ki,2,Tji. In vi’s view, the density operator of the quantum public key ψki,1,ki,2is(10)ρpk,i=PrF1,F2⋅∑F1∑F2ψF1gi,F2giψF1gi,F2gi=122n∑ki,1∑ki,2ψki,1,ki,2ψki,1,ki,2=I2n.
That is, invi’s view, the quantum public key ψki,1,ki,2 is in the maximum mixed state. Then, the quantum ciphertext ψki,1,ki,2Tji is also in the maximum mixed state for vi. So, even if vi sells all known information to the briber, the briber cannot obtain any information about the vote message of vi by eavesdropping cvi⟶ad,ψi,2,idi on the channel from vi to Admin in the ballot-casting from voter to administrator stage. Therefore, the step of computing the ciphertext, i.e., gi,ψki,1,ki,2Tji=qEncψki,1,ki,2,Tji, avoids the requirement that the channel from the vi to Admin is untappable.
In the stage of confirming vote and terminating the election,vi receives cte⟶ad,i by the one-way untappable channel from Admin and obtains ei⊕fi=dDecskad′,cte⟶ad,i by performing dDec. Finally, vi obtains fi with the knowledge of ei. Now, we show that vi cannot prove their vote to the briber according to fi. vi first searches for a vote for candidate Aa on the bulletin board. Assuming the voter va has voted for the candidate Aa, then their corresponding message, which is published by Counter on the bulletin board, is Aa‖ea⊕dEncpkad′,fa, where ea and fa are binary strings of lengths randomly generated by va and Counter, respectively. As skad′ is known, vi can obtain ffalse which satisfies ea⊕dEncpkad′,fa=ei⊕dEncpkad′,ffalse. Then, vi can obtain ffalse by running the dDec algorithm, i.e., ffalse=dDecskad′,ei⊕ea⊕dEncpkad′,fa. Then, vi tells ffalse to the briber, such that the briber can find Aa‖ei⊕dEncpkad′,ffalse on the bulletin board. Therefore, with fi, vi cannot prove to the briber how they voted. In conclusion, the protocol is receipt-free.


## 4.1. Completeness

Theorem 1.
(completeness). In the protocol, all valid votes are counted correctly when all participants are honest.Proof.
(sketch). According to the definition of completeness, all valid votes are counted correctly when all parties in the protocol are honest. A qualified votervi for i∈1,2,…,p encrypts the vote message Aj‖ei which is a simple concatenation of binary string Aj, representing a legal candidate and binary string ei generated randomly by vi, with a classic and quantum public-key pair gi,ψki,1,ki,2 which is selected randomly by vi from Counter’s public key pool. After the ballot ψki1,ki2Tji is signed and verified twice, Counter finally obtains the ciphertext gi,ψki1,ki2Tji. Then, Counter can obtain the vote message of vi’s ballot by decrypting the ciphertext with their private key F1,F2. Hence, it is clear that the proposed protocol satisfies completeness.


## 4.2. Robustness

Theorem 2.
(robustness). The inappropriate behaviour of dishonest participants or nonparticipants cannot disrupt the election; i.e., the protocol is fault-tolerant.Proof.
We analyse the robustness of the protocol by considering the inappropriate behaviour of participants including voters, administrator and counter, and nonparticipants.(i)
When a dishonest votervj seeks to disrupt the election, they may have three strategies. In the first case, vj does not vote, that is, in the ballot-casting from voter to administrator stage, vj does not send idj or cvj⟶ad,ψj,2,idj to Admin. However, it is clear that Admin will be aware of this missing vote. In the second case, vj sends an invalid message group cvj⟶ad,ψj,2,idjfalse to Admin in the ballot-casting from voter to administrator stage. While the running result of qVerf achieved by Admin will not equal 1, this wrong action will be detected by. In the third case, vj generates a random binary string Afalse, which does not represent a qualified candidate and encrypts Afalse||ej with Counter’s public key gj,ψkj,1,kj,2. However, Counter will find out the illegal Afalse in the ballot-counting and result-publishing stage and reject the ballot. In a word, the voter vj cannot succeed in disrupting the election.(ii)
If the internal attackerAdmin wants to disrupt the election, they may have two strategies. In the first case, Admin tampers with the quantum state ψi,1 from a legitimate voter vi in the ballot-casting from administrator to counter stage. However, because Admin does not know the candidate that vi is going to vote for, their random tampering will result in a random decrypting of the result obtained by Counter in the ballot-counting and result-publishing stage. Then, Counter will reject the ballot with a high probability. Because the probability that Admin successfully guesses the candidate that is voted for by vi is 1/q, the probability that they correctly tamper with the quantum state is also 1/q. Then, the probability that the decrypted result obtained by Counter represents a legitimate candidate is also 1/q, so the probability that the ballot is rejected in the ballot-counting and result-publishing stage by Counter is q−1/q. In addition, even if the tampered ballot is accepted by Counter, vi can be aware that their vote is not counted correctly in the confirming vote and terminating the election stage. Then, vi can request a reelection. In the second case, Admin may substitute the quantum state ψi,1. In this manner, Counter will accept the decrypted result, but vi will find that their vote has not been counted correctly during the confirming vote and terminating the election stage, and they can request a reelection.(iii)
IfCounter wants to destroy the election, they may modify the vote message of the accepted ballot and then publish the modified result in the ballot-counting and result-publishing stage. Suppose that Counter tampers with the vote message Aj‖ei of eligible voter vi to Aj′‖ei. To be unnoticed by vi, Counter must send a ffalse so that vi can verify their vote successfully. To achieve that, Counter can find another vote message, such as Aj‖eo, which is chosen by another legal voter vo and make ffalse satisfy ei⊕dEncpkad′,ffalse=eo⊕dEncpkad′,fo. However, because Counter does not have Admin’s private key skad′, it is difficult for Counter to provide a ffalse that can make vi verify their vote message on the bulletin board successfully. Therefore, the misbehaviour of Counter cannot be successful if the classic deterministic public key encryption dPKE is secure.(iv)
If external attackers want to tamper with the ballot from a legitimate votervi, they can only attack during the transmission of cvi⟶ad,ψi,2,idi in the ballot-casting from voter to administrator stage or during the transmission of σad,gi in the ballot-casting from administrator to counter stage. However, the security of the quantum signature algorithm qSignature enables this attack to be detected by Admin or Counter.
Hence, the protocol is robust.


## 4.3. Privacy

Theorem 3.
(privacy). In the protocol, the vote message of the ballot is secret, and only the corresponding voter and the counter can know it. In addition, no one except the voters themselves can associate it with the corresponding voter identity.Proof.
Nonparticipants of the protocol, the administrator, and the counter are all likely to attack the privacy of ballots, so we analyse the three cases in turn. Meanwhile, to prove our election can achieve privacy, we use the no-cloning theorem [57], which states that an exact copy of an unknown quantum state is impossible to achieve in quantum mechanics.(i)
Resistance to attacks from nonparticipants: if a nonparticipant of the protocol wants to attack the privacy ofvi’s ballot, the only possible opportunity occurs during the transmission of information in the ballot-casting from voter to administrator stage and ballot-casting from administrator to counter stage. Assuming that the attacker intercepts cvi⟶ad,ψi,2,idi in the ballot-casting from voter to administrator stage, the security of pPKE ensures that the attackers cannot decrypt cvi⟶ad to obtain ri,1,ri,1′,gi and cannot obtain the signature σ=radi,1,ri,1,ri,1′,ψi,2 of ψki,1,ki,2Tji. Then, the attacker cannot untangle quantum state ψi,2 to obtain ψi,1 and the ciphertext c=gi,ψki,1,ki,2Tji, let alone obtain the vote message of the ballot, because they do not know Counter’s private key F1,F2. Moreover, if the transmitted ballot is classic, the attacker may copy it during its transmission. Once the corresponding private keys are known in the future, the attacker could then violate the privacy of the ballot. However, in our construction, the ballot is transmitted in the form of a quantum state, and ψi,2 is unknown to the attacker. Owing to the no-cloning theorem, after the election is completed, even if the private keys F1,F2 and skad are leaked, the privacy of the ballots is not compromised. If the attacker intercepts σad,gi in the ballot-casting from administrator to counter stage, they can untangle ψi,3 with ri,2 to obtain ψi,1 and the ciphertext c=gi,ψki,1,ki,2Tji. However, they cannot decrypt the ciphertext to obtain vi’s vote message, because the attacker does not know Counter’s private key F1,F2. In this case, ψi,1 is unknown to the attacker. Thus, the attacker cannot copy this state and obtain the vote message of the ballot even if the private key F1,F2 is leaked after the election.(ii)
Resistance to an attack fromAdmin: Admin can obtain the ciphertext c=gi,ψki,1,ki,2Tji in the stage of ballot-casting from voter to administrator, but the security of qPKE ensures that they cannot obtain the vote message of the ballot, because Counter’s private key F1,F2 is unknown. Similar to the earlier analysis, c=gi,ψki,1,ki,2Tji is unknown to Admin, so they cannot copy the ciphertext c. Going further, they cannot obtain the vote message of the ballot even if the private key F1,F2 is leaked after the election.(iii)
Resistance to an attack fromCounter: if Counter wants to attack the privacy of vi’s ballot, they may attack in the stages of ballot-casting from voter to administrator and ballot-casting from administrator to counter. In the stage of ballot-casting from voter to administrator, Counter may intercept cvi⟶ad,ψi,2,idi during the transformation and attempt to obtain vi’s vote message via the intercepted information. However, similar to this type of attack from nonparticipants, the security of pPKE ensures that Counter cannot obtain ri,1,ri,1′,gi and obtain the signature σ=radi,1,ri,1,ri,1′,ψi,2 of ψki,1,ki,2Tji. Thus, Counter cannot untangle quantum state ψi,2 to obtain ψi,1 and the ciphertext c=gi,ψki,1,ki,2Tji. Therefore, it is impossible for Counter to use the private key F1,F2 to decrypt the ciphertext to obtain vi’s vote message. In this stage, ψi,2 is unknown to Counter; thus, they cannot copy it and associate vi′s ballot content with vi’s identity even if Admin’s private key skad is leaked after the election. Moreover, it is worth noting that Counter cannot utilise gi, which is obtained in the stage of ballot-casting from administrator to counter, as a label of vi′s identity to associate vi′s vote message with vi’s identity because gi is encrypted by pPKE in the stage of ballot-casting from voter to administrator. In the stage of ballot-casting from administrator to counter, even though Counter can finally obtain vi’s vote message, they do not know which voter the decrypted ballot comes from because Admin replaces the voter identity idi with gi at this stage.
As a result, the protocol can satisfy the privacy requirement during an election, and the privacy will not be threatened even if corresponding private keys are leaked after the election.


## 4.4. Legality

Theorem 4.
(legality). In the protocol, only legitimate voters can vote.Proof.
(sketch). The security ofqSignature ensures that only the vote cast by a legitimate voter vi for i∈1,2,…,p can be accepted. In the stage of ballot-casting from voter to administrator, vi performs the quantum algorithm to sign their ballot ψki,1,ki,2Tji with their private key fvi−1, i.e., qSignfvi−1,ψki,1,ki,2Tji⟶σ. Then,Admin verifies the signature with vi’s public key fvi, i.e., qVerffvi,ψki,1,ki,2Tji,σ. The Admin accepts the information from vi only if the output of qVerf equals 1, which ensures that Admin only accepts the ballot from legitimate voter vi. Similarly, Counter only accepts the ballot from Admin. Therefore, only legitimate voters can vote successfully.


## 4.5. Unreusability

Theorem 5.
(unreusability). In the protocol, no voter can vote twice.Proof.
(sketch). In the stage of ballot-casting from voter to administrator, if the legal votervi wants to vote, they send idi Admin to first. The condition that idi∉ID and T≤1 ensures that Admin accepts idi only once, so vi can vote only once. Furthermore, in the case where voter vi pretends to be another legitimate voter vi′ and sends idi′ to Admin, the illegal ballot from vi will not be accepted by Admin because vi has no private key fvi′−1 and the security of qSignature ensures that the output of quantum verification algorithm qVerf is not 1. Thus, one legal voter can vote only once.


## 4.6. Fairness

Theorem 6.
(fairness). In the protocol, the intermediate results of the voting do not affect the preference of those who have not yet voted.Proof.
(sketch). After accepting all the vote messages fromq voters, Counter collects the voting result of every voter and then publishes all results on the bulletin board in the stage of ballot-counting and result-publishing. Therefore, no one can obtain the intermediate results of the election, and the protocol is fair.


## 4.7. Verifiability

Theorem 7.
(verifiability). In the protocol, voters can finally verify whether their votes have been counted correctly.Proof.
(sketch).Counter announces the voting result of every voter vi in the form of Aj||ei⊕dEncpkad′,fi. Subsequently, running the encryption algorithm dEnc, Counter obtains cte⟶ad,i=dEncpkad′,ei⊕fi; they then send cte⟶ad,i to vi with the help of Admin. After vi receives it, Admin publishes their private key skad′. Running the decryption algorithm dDec, vi obtains ei⊕fi=dDecskad′,cte⟶ad,i. vi obtains fi with the knowledge of ei. With ei, fi, and pkad′, vi can compute ei⊕dEncpkad′,fi. By searching for ei⊕dEncpkad′,fi on the bulletin board and verifying whether the candidate information corresponding to ei⊕dEncpkad′,fi is Aj, vi can verify whether their vote has been counted correctly.


## 4.8. Receipt-Freeness

Theorem 8.
(receipt-freeness). In the protocol, the voter cannot prove to a third party the content of their vote.Proof.
The protocol can achieve receipt-freeness under the physical assumption that there is a one-way untappable channel from the authority (i.e., the administrator) to the voter [4, 58]. By a standard exclusive-OR trick, this assumption can be implemented by having a number of one-way channels, assuming that the adversary cannot simultaneously tap every one of them [4].
Suppose that votervi wants to vote for candidate Aj, while there is a briber who requires vi to vote for candidate Aa. In this protocol, under the premise that the number of ballots for candidate Aa displayed on the bulletin board does not affect the judgment of the briber (for example, the number of votes for candidate Aa is zero, and this case can be ignored in a large-scale election), and vi can vote for candidate according to their preferences, but lie to the briber successfully by providing the briber with false evidence to prove that they voted for candidate Aa.
In the pre-voting stage, the briber may have asked voter to provideei as evidence for future verification. In this stage, vi performs quantum encryption transformation qEnc on Tji, obtaining the ciphertext gi,ψki,1,ki,2Tji=qEncψki,1,ki,2,Tji. In vi’s view, the density operator of the quantum public key ψki,1,ki,2is(10)ρpk,i=PrF1,F2⋅∑F1∑F2ψF1gi,F2giψF1gi,F2gi=122n∑ki,1∑ki,2ψki,1,ki,2ψki,1,ki,2=I2n.
That is, invi’s view, the quantum public key ψki,1,ki,2 is in the maximum mixed state. Then, the quantum ciphertext ψki,1,ki,2Tji is also in the maximum mixed state for vi. So, even if vi sells all known information to the briber, the briber cannot obtain any information about the vote message of vi by eavesdropping cvi⟶ad,ψi,2,idi on the channel from vi to Admin in the ballot-casting from voter to administrator stage. Therefore, the step of computing the ciphertext, i.e., gi,ψki,1,ki,2Tji=qEncψki,1,ki,2,Tji, avoids the requirement that the channel from the vi to Admin is untappable.
In the stage of confirming vote and terminating the election,vi receives cte⟶ad,i by the one-way untappable channel from Admin and obtains ei⊕fi=dDecskad′,cte⟶ad,i by performing dDec. Finally, vi obtains fi with the knowledge of ei. Now, we show that vi cannot prove their vote to the briber according to fi. vi first searches for a vote for candidate Aa on the bulletin board. Assuming the voter va has voted for the candidate Aa, then their corresponding message, which is published by Counter on the bulletin board, is Aa‖ea⊕dEncpkad′,fa, where ea and fa are binary strings of lengths randomly generated by va and Counter, respectively. As skad′ is known, vi can obtain ffalse which satisfies ea⊕dEncpkad′,fa=ei⊕dEncpkad′,ffalse. Then, vi can obtain ffalse by running the dDec algorithm, i.e., ffalse=dDecskad′,ei⊕ea⊕dEncpkad′,fa. Then, vi tells ffalse to the briber, such that the briber can find Aa‖ei⊕dEncpkad′,ffalse on the bulletin board. Therefore, with fi, vi cannot prove to the briber how they voted. In conclusion, the protocol is receipt-free.


## 5. Instantiation of Our Generic Construction

In this section, we instantiate the general construction of the election protocol.


### 5.1. Instantiation

#### 5.1.1. Quantum Public Key EncryptionqPKE=qGen,qEnc,qDec

To achieve post-quantum security for the protocol, we instantiate the construction of quantum public key cryptographyqPKE with quantum public key encryption scheme [25] based on conjugate encoding which is information-theoretic secure.LetI and Y be two of the Pauli matrices and H be the Hadamard transformation, where(11)I=1001,Y=0−ii0,H=12111−1.Fork=k1,k2,…,kn∈0,1n, we define Hk=Hk1⊗Hk2⊗⋯⊗Hkn, where H is the Hadamard transformation mentioned as above, H0=I,H1=H, and ⊗ is the tensor product. Similarly, we also define Yk=Yk1⊗Yk2⊗⋯⊗Ykn, where Y is one of the Pauli matrices defined as above. Let p denote the number of messages to be encrypted, and mi∈0,1n denote the i-th message for i∈1,2,…,p.(i)
qGen. (1) Randomly select two functions F1,F2 as private key from a set of polynomial computable functions F:0,1n⟶0,1n. (2) Randomly select gi∈0,1n and compute ki,1=F1gi and ki,2=F2gi. (3) Apply Hki,1 to ki,2 and obtain Hki,1ki,2. Take gi,Hki,1ki,2 as one public key. (4) In a word, qGen1n⟶pk=pkii∈1,2,…,p,sk=F1,F2, where pki=gi,Hki,1ki,2.(ii)
qEnc. (1) In order to encrypt the classic message mi, download the classic and quantum public-key pair pki=gi,Hki,1ki,2 from the public key register. (2) Encrypt mi∈0,1n by applying Ymi to Hki,1ki,2, then get the ciphertext c=gi,YmiHki,1ki,2. It is clear that Emi,Hki,1ki,2=YmiHki,1ki,2. (3) In a word, qEncpki,mi⟶c.(iii)
qDec. (1) Given the ciphertext c=gi,YmiHki,1ki,2, use private key F1,F2 to compute ki,1=F1gi,ki,2=F2gi. (2) According to ki,1, apply Hki,1 to YmiHki,1ki,2 and measure on the basis 0,1n to obtain mi⊕ki,2. Then, with ki,2, perform an exclusive OR on mi⊕ki,2 to get mi. (3) It is clear that the algorithm D is the whole process of step (2) described as above. (4) In a word, qDecsk,c=gi,YmiHki,1ki,2⟶mi.


#### 5.1.2. Quantum Digital SignatureqSignature=qKGen,qSign,qVerf The function of quantum signature in the election protocol is to make the verifier get the information that the signer wants to send authenticatively

To achieve post-quantum security for the protocol, we instantiate the construction of quantum digital signatureqSignature with quantum digital signature [24] which is constructed based on the McEliece cryptosystem with post-quantum security [59]. The McEliece secret key consists of a nonsingular n×n matrix S; a generator matrix G size of n×t for a Goppa code; and a t×t permutation matrix P. The McEliece public key is the n×t matrix SGP. In the following, t′=t/2 and n′=t/2.(i)
qKGen. (1) Generate the McEliece public and secret key SGP,S,G,P. (2) Let the secret key sksig be S,G,P and the verification key vksig be G′=SGP.(ii)
qSign. The signer signs a n bits quantum message ψ=∑mαmm to the verifier as follows: (1) the verifier randomly generates a number rver∈0,1t′ and sends it to the signer. (2) The signer randomly generates a number rsig∈0,1n′. (3) With the knowledge of sksig=S,G,P, the signer can get r,r′ which satisfy that r′G′⊕r=rver,rsig, where r∈0,1t,r′∈0,1n. (4) Note that f−1 is the whole process of step (3) described as above and fr,r′=r′G′⊕r. (5) Then, with r, the signer performs the quantum transformation Uf on the quantum message ψ0=∑mαmm0 and obtains(12)∑mαmm0⟶1∑mαmmfr,m,and sends quantum state∑mαmmfr,m to the verifier. (4) In a word, qSignsksig,ψ⟶σ, where(13)σ=rver,r,r′,∑mαmmfr,m.(iii)
qVerf. (1) The verifier tells the signer that they have received the quantum state. (2) The signer announces r and r′. (3) The verifier computes fr,r′=r′G′⊕r and checks whether the first t′ bits of fr,r′ equal rver. They then perform the transformation(14)∑mαmmfr,m⟶2∑mαmm0,and measure the second quantum register. They accept the signature if and only if the second register is in state 0. In a word, qVerfvksig,ψ,σ⟶1 if and only if the second register is in state 0.


#### 5.1.3. Classic Public Key EncryptionpPKE and dPKE

The classic probabilistic public key encryptionpPKE in the instantiation can be any classic public key encryption schemes with post-quantum security such as public key encryption based on coding [59], lattices [60], and multivariates [61].Bellare et al. [62] proposed a generic deterministic public key encryption construction from probabilistic public key encryption, i.e., if there exists a probabilistic public key encryption pPKE=pGen,pEnc,pDec, then there is a classic deterministic public key encryption scheme dPKE=dGen,dEnc,dDec which is illustrated in Figure 4. In the deterministic PKE construction, H denotes a hash function, such as SHA2 and SHA3.Figure 4
DeterministicPKE construction.


### 5.2. Efficiency Analysis

According to Ref. [18], quantum bit efficiency of quantum election protocol is defined as(15)n=C/Q,where the total number of transmitted classic bits (message bits) is C and the total number of quantum bits generated is Q.We can split this protocol into two parts. In the first part, the voter passes the vote message toCounter with the help of Admin. In the second part, Counter passes the verification information to the corresponding voter with the help of Admin. In the first part, the valid classic information transmitted is Tji, and its number of bits is n. To transmit Tji, the n bits quantum public key Hki,1ki,2, n bits quantum ciphertext YmiHki,1ki,2, and ψi,2, ψi,3 are generated, where ψi,2, ψi,3 are both n+t bits quantum states generated during the signature process. Hence, in this part, total of 4n+2t quantum bits are generated. In the second part, the valid classic information transmitted is fi⊕ei, whose length is s, where there is no quantum bit generated. Thus, the number C of valid classic bits transmitted in the protocol is n+s, and the number Q of quantum bits generated in the protocol is 4n+2t. Subsequently, the efficiency of the protocol is(16)η=n+s4n+2t.Whens is equal to t, the efficiency is greater than 1/4.


#### 5.2.1. Performance Comparison

There exist many quantum election protocols based on entangled states [12–14, 16–20]. However, some [13, 14, 16, 17] of these protocols can only perform a binary vote for “yes” or “no.” As a result, we make a performance comparison between our protocol and the quantum election protocols [12, 15, 18–20] which are applicable for scenarios with numerous candidates. Please read Table 1 for more details.Table 1
Performance comparison.
SchemesQuantum resourceEfficiencyInteractive timesLZWL20 [15]Cluster states1/94ZXZ17 [19]Entangled states1/69CDY16 [12]Bell states1/49ZZX18 [20]Cluster states1/44WXJ20 [18]GHZ states1/33OursEntangled states>1/48


### 5.3. Security Comparison

This protocol is an instantiation of our general construction. We have proved that our general construction satisfies the eight requirements of election, so the instantiation also satisfies the eight requirements. For the same reason which is described in Section5.2, we make a security comparison between our protocol and the quantum election protocols [12, 15, 18–20] which are applicable for scenarios with numerous candidates. Please read Table 2 for more details. It is clear that our election protocol is much more secure than other schemes.Table 2
Security comparison.
SchemesCompletenessRobustnessPrivacyLegalityUnreusabilityFairnessVerifiabilityReceipt-freenessLZWL20 [15]✓✕✓✓✓✓✓✕ZXZ17 [19]✓✕✓✓✓✓✓✕CDY16 [12]✓✕✓✓✓✓✓✕ZZX18 [20]✓✕✓✓✓✕✓✕WXJ20 [18]✓✕✓✓✓✕✓✕Ours✓✓✓✓✓✓✓✓


## 5.1. Instantiation

### 5.1.1. Quantum Public Key EncryptionqPKE=qGen,qEnc,qDec

To achieve post-quantum security for the protocol, we instantiate the construction of quantum public key cryptographyqPKE with quantum public key encryption scheme [25] based on conjugate encoding which is information-theoretic secure.LetI and Y be two of the Pauli matrices and H be the Hadamard transformation, where(11)I=1001,Y=0−ii0,H=12111−1.Fork=k1,k2,…,kn∈0,1n, we define Hk=Hk1⊗Hk2⊗⋯⊗Hkn, where H is the Hadamard transformation mentioned as above, H0=I,H1=H, and ⊗ is the tensor product. Similarly, we also define Yk=Yk1⊗Yk2⊗⋯⊗Ykn, where Y is one of the Pauli matrices defined as above. Let p denote the number of messages to be encrypted, and mi∈0,1n denote the i-th message for i∈1,2,…,p.(i)
qGen. (1) Randomly select two functions F1,F2 as private key from a set of polynomial computable functions F:0,1n⟶0,1n. (2) Randomly select gi∈0,1n and compute ki,1=F1gi and ki,2=F2gi. (3) Apply Hki,1 to ki,2 and obtain Hki,1ki,2. Take gi,Hki,1ki,2 as one public key. (4) In a word, qGen1n⟶pk=pkii∈1,2,…,p,sk=F1,F2, where pki=gi,Hki,1ki,2.(ii)
qEnc. (1) In order to encrypt the classic message mi, download the classic and quantum public-key pair pki=gi,Hki,1ki,2 from the public key register. (2) Encrypt mi∈0,1n by applying Ymi to Hki,1ki,2, then get the ciphertext c=gi,YmiHki,1ki,2. It is clear that Emi,Hki,1ki,2=YmiHki,1ki,2. (3) In a word, qEncpki,mi⟶c.(iii)
qDec. (1) Given the ciphertext c=gi,YmiHki,1ki,2, use private key F1,F2 to compute ki,1=F1gi,ki,2=F2gi. (2) According to ki,1, apply Hki,1 to YmiHki,1ki,2 and measure on the basis 0,1n to obtain mi⊕ki,2. Then, with ki,2, perform an exclusive OR on mi⊕ki,2 to get mi. (3) It is clear that the algorithm D is the whole process of step (2) described as above. (4) In a word, qDecsk,c=gi,YmiHki,1ki,2⟶mi.


### 5.1.2. Quantum Digital SignatureqSignature=qKGen,qSign,qVerf The function of quantum signature in the election protocol is to make the verifier get the information that the signer wants to send authenticatively

To achieve post-quantum security for the protocol, we instantiate the construction of quantum digital signatureqSignature with quantum digital signature [24] which is constructed based on the McEliece cryptosystem with post-quantum security [59]. The McEliece secret key consists of a nonsingular n×n matrix S; a generator matrix G size of n×t for a Goppa code; and a t×t permutation matrix P. The McEliece public key is the n×t matrix SGP. In the following, t′=t/2 and n′=t/2.(i)
qKGen. (1) Generate the McEliece public and secret key SGP,S,G,P. (2) Let the secret key sksig be S,G,P and the verification key vksig be G′=SGP.(ii)
qSign. The signer signs a n bits quantum message ψ=∑mαmm to the verifier as follows: (1) the verifier randomly generates a number rver∈0,1t′ and sends it to the signer. (2) The signer randomly generates a number rsig∈0,1n′. (3) With the knowledge of sksig=S,G,P, the signer can get r,r′ which satisfy that r′G′⊕r=rver,rsig, where r∈0,1t,r′∈0,1n. (4) Note that f−1 is the whole process of step (3) described as above and fr,r′=r′G′⊕r. (5) Then, with r, the signer performs the quantum transformation Uf on the quantum message ψ0=∑mαmm0 and obtains(12)∑mαmm0⟶1∑mαmmfr,m,and sends quantum state∑mαmmfr,m to the verifier. (4) In a word, qSignsksig,ψ⟶σ, where(13)σ=rver,r,r′,∑mαmmfr,m.(iii)
qVerf. (1) The verifier tells the signer that they have received the quantum state. (2) The signer announces r and r′. (3) The verifier computes fr,r′=r′G′⊕r and checks whether the first t′ bits of fr,r′ equal rver. They then perform the transformation(14)∑mαmmfr,m⟶2∑mαmm0,and measure the second quantum register. They accept the signature if and only if the second register is in state 0. In a word, qVerfvksig,ψ,σ⟶1 if and only if the second register is in state 0.


### 5.1.3. Classic Public Key EncryptionpPKE and dPKE

The classic probabilistic public key encryptionpPKE in the instantiation can be any classic public key encryption schemes with post-quantum security such as public key encryption based on coding [59], lattices [60], and multivariates [61].Bellare et al. [62] proposed a generic deterministic public key encryption construction from probabilistic public key encryption, i.e., if there exists a probabilistic public key encryption pPKE=pGen,pEnc,pDec, then there is a classic deterministic public key encryption scheme dPKE=dGen,dEnc,dDec which is illustrated in Figure 4. In the deterministic PKE construction, H denotes a hash function, such as SHA2 and SHA3.Figure 4
DeterministicPKE construction.


## 5.1.1. Quantum Public Key EncryptionqPKE=qGen,qEnc,qDec

To achieve post-quantum security for the protocol, we instantiate the construction of quantum public key cryptographyqPKE with quantum public key encryption scheme [25] based on conjugate encoding which is information-theoretic secure.LetI and Y be two of the Pauli matrices and H be the Hadamard transformation, where(11)I=1001,Y=0−ii0,H=12111−1.Fork=k1,k2,…,kn∈0,1n, we define Hk=Hk1⊗Hk2⊗⋯⊗Hkn, where H is the Hadamard transformation mentioned as above, H0=I,H1=H, and ⊗ is the tensor product. Similarly, we also define Yk=Yk1⊗Yk2⊗⋯⊗Ykn, where Y is one of the Pauli matrices defined as above. Let p denote the number of messages to be encrypted, and mi∈0,1n denote the i-th message for i∈1,2,…,p.(i)
qGen. (1) Randomly select two functions F1,F2 as private key from a set of polynomial computable functions F:0,1n⟶0,1n. (2) Randomly select gi∈0,1n and compute ki,1=F1gi and ki,2=F2gi. (3) Apply Hki,1 to ki,2 and obtain Hki,1ki,2. Take gi,Hki,1ki,2 as one public key. (4) In a word, qGen1n⟶pk=pkii∈1,2,…,p,sk=F1,F2, where pki=gi,Hki,1ki,2.(ii)
qEnc. (1) In order to encrypt the classic message mi, download the classic and quantum public-key pair pki=gi,Hki,1ki,2 from the public key register. (2) Encrypt mi∈0,1n by applying Ymi to Hki,1ki,2, then get the ciphertext c=gi,YmiHki,1ki,2. It is clear that Emi,Hki,1ki,2=YmiHki,1ki,2. (3) In a word, qEncpki,mi⟶c.(iii)
qDec. (1) Given the ciphertext c=gi,YmiHki,1ki,2, use private key F1,F2 to compute ki,1=F1gi,ki,2=F2gi. (2) According to ki,1, apply Hki,1 to YmiHki,1ki,2 and measure on the basis 0,1n to obtain mi⊕ki,2. Then, with ki,2, perform an exclusive OR on mi⊕ki,2 to get mi. (3) It is clear that the algorithm D is the whole process of step (2) described as above. (4) In a word, qDecsk,c=gi,YmiHki,1ki,2⟶mi.


## 5.1.2. Quantum Digital SignatureqSignature=qKGen,qSign,qVerf The function of quantum signature in the election protocol is to make the verifier get the information that the signer wants to send authenticatively

To achieve post-quantum security for the protocol, we instantiate the construction of quantum digital signatureqSignature with quantum digital signature [24] which is constructed based on the McEliece cryptosystem with post-quantum security [59]. The McEliece secret key consists of a nonsingular n×n matrix S; a generator matrix G size of n×t for a Goppa code; and a t×t permutation matrix P. The McEliece public key is the n×t matrix SGP. In the following, t′=t/2 and n′=t/2.(i)
qKGen. (1) Generate the McEliece public and secret key SGP,S,G,P. (2) Let the secret key sksig be S,G,P and the verification key vksig be G′=SGP.(ii)
qSign. The signer signs a n bits quantum message ψ=∑mαmm to the verifier as follows: (1) the verifier randomly generates a number rver∈0,1t′ and sends it to the signer. (2) The signer randomly generates a number rsig∈0,1n′. (3) With the knowledge of sksig=S,G,P, the signer can get r,r′ which satisfy that r′G′⊕r=rver,rsig, where r∈0,1t,r′∈0,1n. (4) Note that f−1 is the whole process of step (3) described as above and fr,r′=r′G′⊕r. (5) Then, with r, the signer performs the quantum transformation Uf on the quantum message ψ0=∑mαmm0 and obtains(12)∑mαmm0⟶1∑mαmmfr,m,and sends quantum state∑mαmmfr,m to the verifier. (4) In a word, qSignsksig,ψ⟶σ, where(13)σ=rver,r,r′,∑mαmmfr,m.(iii)
qVerf. (1) The verifier tells the signer that they have received the quantum state. (2) The signer announces r and r′. (3) The verifier computes fr,r′=r′G′⊕r and checks whether the first t′ bits of fr,r′ equal rver. They then perform the transformation(14)∑mαmmfr,m⟶2∑mαmm0,and measure the second quantum register. They accept the signature if and only if the second register is in state 0. In a word, qVerfvksig,ψ,σ⟶1 if and only if the second register is in state 0.


## 5.1.3. Classic Public Key EncryptionpPKE and dPKE

The classic probabilistic public key encryptionpPKE in the instantiation can be any classic public key encryption schemes with post-quantum security such as public key encryption based on coding [59], lattices [60], and multivariates [61].Bellare et al. [62] proposed a generic deterministic public key encryption construction from probabilistic public key encryption, i.e., if there exists a probabilistic public key encryption pPKE=pGen,pEnc,pDec, then there is a classic deterministic public key encryption scheme dPKE=dGen,dEnc,dDec which is illustrated in Figure 4. In the deterministic PKE construction, H denotes a hash function, such as SHA2 and SHA3.Figure 4
DeterministicPKE construction.


## 5.2. Efficiency Analysis

According to Ref. [18], quantum bit efficiency of quantum election protocol is defined as(15)n=C/Q,where the total number of transmitted classic bits (message bits) is C and the total number of quantum bits generated is Q.We can split this protocol into two parts. In the first part, the voter passes the vote message toCounter with the help of Admin. In the second part, Counter passes the verification information to the corresponding voter with the help of Admin. In the first part, the valid classic information transmitted is Tji, and its number of bits is n. To transmit Tji, the n bits quantum public key Hki,1ki,2, n bits quantum ciphertext YmiHki,1ki,2, and ψi,2, ψi,3 are generated, where ψi,2, ψi,3 are both n+t bits quantum states generated during the signature process. Hence, in this part, total of 4n+2t quantum bits are generated. In the second part, the valid classic information transmitted is fi⊕ei, whose length is s, where there is no quantum bit generated. Thus, the number C of valid classic bits transmitted in the protocol is n+s, and the number Q of quantum bits generated in the protocol is 4n+2t. Subsequently, the efficiency of the protocol is(16)η=n+s4n+2t.Whens is equal to t, the efficiency is greater than 1/4.


### 5.2.1. Performance Comparison

There exist many quantum election protocols based on entangled states [12–14, 16–20]. However, some [13, 14, 16, 17] of these protocols can only perform a binary vote for “yes” or “no.” As a result, we make a performance comparison between our protocol and the quantum election protocols [12, 15, 18–20] which are applicable for scenarios with numerous candidates. Please read Table 1 for more details.Table 1
Performance comparison.
SchemesQuantum resourceEfficiencyInteractive timesLZWL20 [15]Cluster states1/94ZXZ17 [19]Entangled states1/69CDY16 [12]Bell states1/49ZZX18 [20]Cluster states1/44WXJ20 [18]GHZ states1/33OursEntangled states>1/48


## 5.2.1. Performance Comparison

There exist many quantum election protocols based on entangled states [12–14, 16–20]. However, some [13, 14, 16, 17] of these protocols can only perform a binary vote for “yes” or “no.” As a result, we make a performance comparison between our protocol and the quantum election protocols [12, 15, 18–20] which are applicable for scenarios with numerous candidates. Please read Table 1 for more details.Table 1
Performance comparison.
SchemesQuantum resourceEfficiencyInteractive timesLZWL20 [15]Cluster states1/94ZXZ17 [19]Entangled states1/69CDY16 [12]Bell states1/49ZZX18 [20]Cluster states1/44WXJ20 [18]GHZ states1/33OursEntangled states>1/48


## 5.3. Security Comparison

This protocol is an instantiation of our general construction. We have proved that our general construction satisfies the eight requirements of election, so the instantiation also satisfies the eight requirements. For the same reason which is described in Section5.2, we make a security comparison between our protocol and the quantum election protocols [12, 15, 18–20] which are applicable for scenarios with numerous candidates. Please read Table 2 for more details. It is clear that our election protocol is much more secure than other schemes.Table 2
Security comparison.
SchemesCompletenessRobustnessPrivacyLegalityUnreusabilityFairnessVerifiabilityReceipt-freenessLZWL20 [15]✓✕✓✓✓✓✓✕ZXZ17 [19]✓✕✓✓✓✓✓✕CDY16 [12]✓✕✓✓✓✓✓✕ZZX18 [20]✓✕✓✓✓✕✓✕WXJ20 [18]✓✕✓✓✓✕✓✕Ours✓✓✓✓✓✓✓✓


## 6. Conclusion

In this paper, we utilise the general construction of quantum digital signature [24] and quantum public key encryption [25], in conjunction with classic public key encryption, to develop a general construction of a quantum election protocol. The protocol is suitable for large-scale elections with numerous candidates and voters and accommodates scenarios in which multiple voters vote simultaneously. The protocol does not require any two participants to pre-share a secret key, nor does it require anonymous channels or a trusted third party. This construction is the first to achieve the properties of completeness, robustness, privacy, legality, unreusability, fairness, verifiability, and receipt-freeness under attacks from both external and internal agents in the current quantum election protocols. We instantiate the general construction into an election scheme with post-quantum security by applying cryptographic algorithms having post-quantum security. Furthermore, our election protocol has higher security than that of existing protocols. All the keys of the quantum digital signature are classic so that the classic PKI can be used for key management and distribution.This construction is a theoretical achievement, and any practical application remains a distant goal. The quantum public key cryptosystem has significant room for development in comparison with the relatively well-established conventional public key cryptosystem. Numerous problems remain to be solved, such as developing the quantum PKI.



---

*Source: 5551249-2021-04-14.xml*