Quantum homomorphic broadcast multi-signature based on homomorphic aggregation

Xin Xu(徐鑫) and Ai-Han Yin(殷爱菡)

Department of Information Engineering,East China JiaoTong University,Nanchang 330013,China

Keywords: quantum signature,homomorphic aggregation,homomorphic multi-signature,Bell state

1.Introduction

As an extension of handwritten signatures in the digital field,digital signatures are now used in daily life.Since modern computers cannot solve such problems in polynomial time,the security of signatures relies on mathematically complex puzzles in classical cryptography.However, since the Shor quantum parallel algorithm[1]solved RSA encryption problem in a limited time in 1994,the security of digital signatures has begun to shake.In order to improve the security of digital signatures,many researchers have begun to use quantum properties to study how to ensure signature security,which opens the door of quantum signature.

In 1984,Bennett and Brassard[2]proposed the first quantum key distribution protocol.Quantum key distribution is the premise of other quantum protocols,one of which is quantum signature.Its purpose is to enable communication parties to generate a secure key for processing messages.Although the research of quantum key distribution set up early, there are still many scholars to enrich the content of this field now.For example,Wanget al.[3]proposed twin-field quantum key distribution over 830-km fibre and made a breakthrough in the establishment of ground-based quantum security networks on a scale of 1000 km,and Fan-Yuanet al.[4,5]proposed that all contributes to the development of quantum cryptography.

Quantum signature is an important research direction in quantum cryptography.One of its important characteristics is that its security completely changes the traditional digital signature’s dependence on difficult mathematical assumptions,that is,the security of quantum signature depends on the basic principles of quantum mechanics, such as uncertainty principle and non-cloning theorem.So,in theory,a secure quantum signature could deal with a quantum computer attack.Because of these security characteristics of quantum signature,the related research has received much attention.[6–8]In recent years, the research on quantum signature has made new progress, such as efficient quantum digital signatures without symmetrization step proposed by Luet al.,[9]which improves the signature rate of the protocol; secure and practical multiparty quantum digital signatures proposed by Wenget al.,[10]which improves the data utilization rate; and experimental quantum secure network with digital signatures and encryption proposed by Yinet al.,[11]which combines quantum signature with network and expands the research scope of quantum signature.

Quantum multi-signature is a branch of quantum signature, which is widely used in e-commerce, property division,fund management and other scenarios.[12–14]It is characterized by multiple signers signing the same message, and according to the different signature orders that can be divided into ordered signature and broadcast signature: these two modes have their own advantages and disadvantages.Both models have advantages and disadvantages.In 2007, Wenet al.[15]firstly proposed a realizable quantum ordered multiple digital signature scheme based on classical multiple signatures, which relies on quantum key distribution and one-time pad algorithm to ensure the security of the protocol.Then,they[16]proposed a quantum digital multi-signature using controlled quantum teleportation for multi-signature and does not rely on an arbitrator to verify the signature.In the same year, Wenet al.[17]proposed two quantum broadcast multisignature protocols, one for classical digital message, which uses quantum unidirectional function to realize signature and verification, and the other for quantum message, which uses quantum teleportation technology.In 2016, Duet al.[18]proposed an efficient quantum ordered multi-signature protocol,which also uses quantum key distribution and one-time pad algorithm,but only needs to perform unitary operations on single particles to complete the signature instead of multi-particle entangled state.In 2019, Jianget al.[19]proposed a novel quantum multi-signature protocol based on locally indistinguishable orthogonal product states, which ensures information security with fewer decoy particles during transmission.In 2021, Heet al.[20]analyzed the security of some quantum multi-signature protocols that have been used so far and proposed related improvements.This shows that the research on quantum multi-signature is slow but still ingoing.[21,22]

Quantum multi-signature protocols are also often combined with other signature protocols.In 2019, Qinet al.[23]proposed an efficient quantum multi-proxy signature protocol,in which the rights of the original signer are assigned to multiple proxy signers, that is, a single signature becomes multiple proxy signatures.In the same year, Zhanget al.[24]proposed a novel quantum broadcasting multiple blind signature scheme based on partial entanglement of multiple particles.With the deepening of the research,the research on the application in the signature protocol is also conducted.In 2017,Shaoet al.[25]proposed an electronic payment protocol based in quantum multi-agent blind signature.In 2018,Niuet al.[26]improved the Shaoet al.’s protocol and proposed a practical quantum multi-agent blind signature electronic payment protocol.

Quantum homomorphic signature has been proposed in recent year, which is the extension of homomorphic signature in quantum field.In 2015, Shanget al.[27]proposed a quantum homomorphic signature protocol for the first time,which uses entanglement swapping to complete signature aggregation.This protocol solves the problem of multi-stream identity authentication in quantum signature, effectively ensures the security of key,and verifies the identities of different data sources in quantum network.In 2016,Luoet al.[28]also proposed a quantum homomorphic signature protocol.Unlike Shang’s protocol,this protocol is based on signature aggregation of Bell state measurement.In 2017, Liet al.[29]thought of a new idea from the spectral characteristics, and proposed a quantum homomorphic signature scheme by using the continuous variable part of the quantum spectrum.This scheme uses continuous-variable quantum information and transmits more information at lower cost.In 2019, Shanget al.[30]introduced a serial verification model and a parallel verification model,and proposed a new quantum homomorphic signature protocol with repeatable verification.The serial model handles the signature verification problem,and the parallel verification model handles the signature repetition problem.This protocol is beneficial to signature verification in general scenarios.

These quantum homomorphic signatures are based on the signature model proposed by Shanget al.[27]In this model,the message holder and the signer are played by the same person, which can authenticate the identities of different data sources.However,this setting also limits the application scenarios of quantum homomorphic signatures.To broaden its application scope,we introduce quantum multi signatures,and also improve the shortcomings of traditional quantum multi signatures through quantum homomorphic signatures.Quantum multi signature is a common signature.It needs to convert classical messages into quantum sequences.Therefore,it needs to prepare multiple quantum states,leading to a long initialization phase.In addition,in the verification phase,it only relies on the classical bit key.If the key is stolen,it is easy to forge the signature and pass the verification.

In this paper, we apply homomorphic aggregation to quantum multi-signature, and propose a quantum homomorphic multi-signature protocol,which uses homomorphic property to complete the generation and verification of signature.This method not only broadens the application scope of quantum homomorphic signature,but also improves quantum multi signature,so that it only needs to prepare a quantum state,reducing the preparation time,and requires quantum sequences and classical keys when verifying signatures, making attackers unable to pass the verification when they only have the key.We mainly introduce the following aspects.First, we introduce the basic knowledge related to quantum signatures,then we introduce the proposed scheme in detail, and finally analyze the proposed scheme.

2.Related works

2.1.Quantum homomorphic signature

Quantum homomorphic signature is a quantum signature with homomorphic properties, or an extension of a homomorphic signature in a quantum field, and the generation and verification of signatures are realized by using the homomorphic properties.From the calculation method, we can divide homomorphism into additive homomorphism and multiplicative homomorphism.Suppose that there are two inputsY1andY2, if there is a functionfthat satisfiesρ(Y1+Y2)=f(ρ(Y1),ρ(Y2)), then the functionρwill be additively homomorphic.Similarly, the functionρis multiplicative homomorphic when the functionfconforms toρ(Y1×Y2) =f(ρ(Y1),ρ(Y2)).

Homomorphic signature schemes are mainly divided into five types: linear homomorphism,polynomial function homomorphism, full homomorphism, homomorphic aggregation,and multi-key homomorphism.[31,32]Among them,homomorphic aggregation is different from other schemes,it can solve multi-user application scenarios.In this type of scenario, the generated signatures are aggregated from the signatures corresponding to different messages,which are signed by different users,and each user has its own secret key.

Fig.1.Homomorphic aggregation.

Entanglement swapping is a property of quantum state,[33–35]it can be used to achieve homomorphic aggregation in the field of quantum signatures.Assume that there are two Bell states,|φ+〉12and|φ+〉34.The Bell state measurement is performed on particle 1 and particle 3,so that the two particles that are not originally entangled are entangled together,becoming Bell state|ϕ〉13,and the other two particles collapse into|ϕ〉24.The specific quantum states of these two pairs of new Bell states are as follows:

Here is just one of entanglement swapping of Bell state.

2.2.Quantum multi-signature

Quantum multi-signature can be divided into two types according to the signature order of the signers, namely quantum broadcast multi-signature and quantum ordered multisignature.

In quantum broadcast multi-signature,[36]the issuer sends the message to be signed to each signer out of order; each signer sends the message and corresponding signature to the collector after completing the signature; the collector verifies each individual signature and then aggregates them into a multi-signature and sends it to the verifier; finally, the verifier verifies the validity of the multi-signature.The advantage of this is that the signers will not contact each other’s information, and the signature does not need to wait.After the signature is completed,it can be directly sent to the collector.However, the disadvantage is that the multi signature work is completed by one node, which needs to have high credibility and strong processing capability.

Fig.2.Quantum broadcast multi-signature.

In an ordered multi-signature scheme,[37,38]the issuer specifies the order of the signers’signature,and then sends the message to the first signer.Except the first signer,each signer verifies the validity of the previous signature after receiving it, if the signature is valid, the signer continues to sign, and then sends the signature to the next signer;otherwise,it would reject the signature and terminates the entire process.Until all signers complete the signing operation,the signed message is sent to the verifier.Finally, the verifier verifies the validity of the multi-signature.The advantage of this approach is that when problems occur in the signature,they can be found in a timely manner and will not accumulate errors to the final verifier.However, the disadvantage is that previous signature will be received by the subsequent signers, which may cause attacks between signers.In addition, the subsequent signers need to wait for the previous signer to complete the signature before signing,resulting in a long overall time.

It can be seen that quantum homomorphic signature and quantum broadcast multi signature have a high degree of consistency in the signature model.

Fig.3.Quantum ordered multi-signature.

3.Proposed protocol

In this section, we propose a quantum homomorphic multi-signature scheme based on homomorphic aggregation in detail.The scheme consists of four stages, namely initialization, signing, aggregation and verification.There are four kinds of participants, namely Alice who holds the message to be signed, Bob who is responsible for signing, Dace who aggregates signatures,and Charlie who verifies the signature.The flow chart of this scheme is shown in Fig.4.

Fig.4.Scheme flow chart.

(i)Initialization

Step 1Alice converts the message to be signed into a binary sequence.Here, we limit the length of the binary sequence to 2, which is a special value in order to better introduce the details of the scheme and avoid the redundancy of content.It does not affect the universality of the scheme.The resulting binary sequence is namedXand send to Charlie in advance.

Step 2According to the length of the binary sequenceXowned by Alice,Charlie prepares three classical bits of the same length (denoted asKi), and shares them with Bobiby quantum key distribution protocol,these are secret keys shared between Bobiand Charlie,hereKi ∈{00,01,10,11}.

Step 3Dave prepares three EPR entangled pairs:

(ii)Signing

Step 1Dave takes one particle from each of the three entangled EPR pairs, here we choose particle 2, particle 4 and particle 6, which can be denoted as|ϕ〉2,|ϕ〉4,|ϕ〉6, respectively.Then Dave sends these particles to Bob1, Bob2, and Bob3respectively.At the same time, Alice also sends the binary sequenceXto Bobi.

Step 2After Bobireceives the binary sequenceXand particles from Alice, he performs an exclusive OR operation on the binary sequenceXand the secret keyKihe holds,and the resultX ⊕Kiis used to sign the received particle 2i.

Here, the unitary operator used in the particle signature corresponds to the exclusive OR resultX ⊕Ki,and the corresponding relationship is as follows:

Step 3Bobisends the transformed particle 2i, namely|ϕ′〉2i, and the exclusive OR resultX ⊕Kito Dave.Here, the superscript(′)indicates that the particle or quantum state completes the signature operation.

(iii)Aggregation

After Bobicompletes the signature of particle 2iwith the exclusive OR resultX ⊕Ki, the original three EPR entangled pairs would change, the states of these would be|ϕ′〉12=U(X ⊕K1)(2)·|φ+〉12,|ϕ′〉34=U(X ⊕K2)(4)·|φ+〉34,|ϕ′〉56=U(X ⊕K3)(6)·|φ+〉56.These transformed EPR entangled pairs are Bobi’s signatures.

Then, Dave combines these individual signatures|ϕ′〉(2i−1)(2i)received from Bobito generate an aggregated signature.The generation process of the aggregated signature is as follows.

Step 1Dave would aggregate the signature of Bob2and Bob3.The way to aggregate is to perform an entanglement swapping on quantum states|ϕ′〉34and|ϕ′〉56.First, Dave performs a Bell state measurement on particle 3 and particle 5 in these two quantum states, then, we obtain an entangled pair|ϕ′′〉35.This measurement enables two unentangled particles to become entangled.According to the entanglement exchange principle,the remaining non-entangled particles 4 and 6 would collapse into a pair of entangled states|ϕ′′〉46.Here,|ϕ′′〉46would be the combined signature of Bob2and Bob3,and the superscript (′′) indicates that the particle or quantum state completes the two operations of signature and entanglement swapping.

Step 2Dave performs an entanglement swapping on|ϕ′〉12and|ϕ′′〉46to connect the combined signature of Bob2and Bob3and the signature of Bob1.According to the procedure in Step 1,we can easily obtain the state of particle 1 and particle 4 after measurement which is|ϕ′′〉14.Similarly, the state of the particles 2 and 6 would collapse into|ϕ′′〉26.The|ϕ′′〉26would be the signature of Dave.

Step 3Dave performs exclusive OR operation on each signer’s signature informationX ⊕Ki,and obtains(X ⊕K1)⊕(X ⊕K2)⊕(X ⊕K3).

Step 4Dave sends the signature information(X ⊕K1)⊕(X ⊕K2)⊕(X ⊕K3)and|ϕ′′〉26to Charlie.

(iv)Verification

Charlie receives quantum states|ϕ′′〉26and (X ⊕K1)⊕(X ⊕K2)⊕(X ⊕K3)from Dave,and can use this information to verify the signature.The verification process is as follows.

Step 1After Charlie receives quantum state|ϕ′′〉26from Dave, he performs a Bell state measurement on the particles in|ϕ′′〉26to obtain the state of the quantum state|ϕ′′〉26, and then compares the measurement result|ϕ′′〉26with the initial quantum state|ϕ〉26in order to find an operator that satisfies the formula|ϕ′′〉26=c(Z)U(Z)6·|ϕ〉26.In the formula, the subscript“6”means operating on particle 6,and|c(Z)|=1.

Step 2Charlie compares(X ⊕K1)⊕(X ⊕K2)⊕(X ⊕K3)withZ.If(X ⊕K1)⊕(X ⊕K2)⊕(X ⊕K3)=Z,Charlie would confirm that|ϕ′′〉26is the signature of Dave.Otherwise,Charlie would deny the signature.

4.Scheme analysis

In this section, we analyze the proposed protocol from three aspects,namely homomorphic properties,security analysis and comparison.

4.1.Homomorphic property

We refer to two proven lemmas in Ref.[27] to demonstrate the homomorphic properties of our proposed scheme.The representation of these lemmas is as follows.

Lemma 1U(Y1)·U(Y2)·|ϕ〉=c(Y1,Y2)·U(Y1⊕Y2)·|ϕ〉,whereY1,Y2∈{00,01,10,11}|c(Y1,Y2)|=1.

Note thatU(Y1) andU(Y2) represent the unitary operators corresponding to secret keysY1andY2,and|c(Y1,Y2)|=1 is a factor that only affects the phase,so it can be ignored after the Bell state measurement.

Bringing Lemma 2 into the above formula, the resulting equation is obtained as follows:

Then bring Lemma 1 into the above formula.the resulting equation is below:

Comparing the above formula with

we can see that|ϕ′′〉3456is obtained by the unitary operation on particle 6 in|φ+〉35⊕|φ+〉46.Therefore, we obtain that|ϕ′′〉46=c(Z)U(Z)6|ϕ〉46, whereZ=X ⊕K2⊕X ⊕K3,c(Z)=cjc(U2U3).is a phase factor.|ϕ′′〉46is the aggregate signature of Bob2and Bob3.

Similarly, Dave performs the same operation on|φ+〉12and|ϕ′′〉46, and we obtain easily that|ϕ′′〉26=c(Z)U(Z)6|ϕ〉26,wherec(Z)=cjc(U1,U2,U3),Z=X ⊕K1⊕X ⊕K2⊕X ⊕K3,is a phase factor and|ϕ′′〉26is the aggregate signature of Bob1,Bob2,and Bob3.

Here,we define that the function offas the operation of entanglement swapping and the function Sign as the operation of signature.

Thus, the signatures of the signers can be written as follows:

Then,collector aggregates these signatures through entanglement swapping,and the result can be written as follows:

In the above formula,

If the aggregated signature is generated by the informationXi ⊕Yi,then

Thus,

Compared with the additive homomorphic modelρ(Y1+Y2)=f(ρ(Y1)ρ(Y2)), our signature scheme satisfies the additive homomorphism property.

4.2.Security analysis

We analyze the security of the proposed quantum signature protocol from the following three aspects: verifiability,non-repudiation, and unforgeability.To simplify the model,the participants in the protocol are assumed to be honest.

(I)Verifiability: The verifier can verify the validity of the signature of the corresponding signer through the shared secret key.

In our scheme, there are two signature processes: one is the individual signature generated by the signer and the other is the aggregated signature generated by the collector,and the verifier can verify the validity of both signatures.After the verifier receives the signature sent by the collector, an equation|ϕ′′〉AB=c(Z)U(Z)B|ϕ〉ABwith the initial quantum state is formed, and thenZin the equation is compared with the secret keyXito verify the validity of the signer’s signature.Then, the verifier can ask the collector to send it the quantum state after the entanglement swapping, and can calculate whether the aggregate signature generated by the collector is valid through initial quantum state.

Non-repudiation and unforgeability are important security requirements in a signature scheme.For convenience,we use the examples in this work to illustrate the above two properties.

(II)Non-repudiation: The secret key held by the signer is not only a tool for signing,but also the signer’s identity label,so it cannot deny its own signature.

No signer can deny their signatures.The verifier compares the received aggregated signature|ϕ′′〉26with the initial quantum state,and forms an equation that satisfies the formula|ϕ′′〉26=c(Z)U(Z)6·|ϕ〉26.Assuming that the verifier performs exclusive OR operation onZandK2⊕K3,and the result isK1,it can prove that the signer Bob1has indeed signed and the signature cannot be denied.Here,K1is equivalent to a signed label.Note that the verifier needs to processZaccording to the number of signers in the above step,if the number is odd,Zis processed asZ ⊕X;if it is even,Zis not operated.

(III) Unforgeability: The signer’s secret key is obtained from the verifier through the BB84 protocol which proves to be unconditionally secure, and no one else can forge the signature.

The signature cannot be forged.In a signature protocol,the secret keyKiis an important factor in generating the signature, so enhancing the security of the secret key transmission is to enhance the security of the signature.In our signature scheme,the secret keyKiis distributed by the BB84 protocol and the secret keyKican be safely shared by Bobiand Charlie,because the key distribution protocol proves to be unconditionally secure.On the other hand,the secret keyKicannot be calculated from the message and the corresponding signature.Suppose that the Eve steals both particle 2 andX ⊕K1in the process of the signer sending the information to the collector,he cannot calculate|ϕ′〉12without particle 1 or the unitary operationU(X ⊕K1) with only particle 2.Therefore, attackers cannot steal the secret keyKiof the protocol with only particles 2iandX ⊕Kiso that the signature cannot be forged.

4.3.Comparisons

Although quantum multi-signature has been studied for a long time, its research direction is mainly its applications in different signature scenarios,or its combination with other signature protocols.Here,we refer to previous signature protocols related to quantum multi-signature as traditional quantum multi-signature and compare it with our proposed quantum homomorphic multi-signature.We mainly compare the following three aspects,as shown in Table 1.

Table 1.Comparisons of proposed protocol with traditional protocols.

In the traditional quantum multi-signature scheme, the message holder first converts the message to be signed into a binary sequence,and then converts it into a quantum sequence.Taking the Bell state used in our paper for example,the message holder needs to prepare four different Bell states.But in our proposed signature scheme,the message holder only needs to convert the message to be signed into a binary sequence,the Bell state is prepared by the collector,and only one Bell state needs to be prepared,which can significantly improve the efficiency of Bell state preparation.

In the signature stage, in the traditional quantum multisignature scheme, the signer’s secret key is used to perform multiple unitary operations on the same quantum state.If the quantum state and related keys are stolen by Eve, the signature may be forged.In our scheme,the signer uses the unitary operation to sign different quantum states, and then uses the entanglement exchange to complete the aggregation of the signatures.Even if Eve steals the relevant information,he cannot obtain the key to forge the signature.

In the verification phase, the verifier only has the secret key shared with the signer.In the traditional multi-signature scheme, it can only verify whether the signer’s key is used correctly,but cannot judge whether the signed message is correct.In our scheme, the verifier not only shares the key of the signer,but also has the binary sequence of the message to be signed,which can verify the correctness of the key and the authenticity of the message signed by the signer.

4.4.Tolerable number of dishonest users

In our scheme,the aggregator and the verifier are two important nodes that must be trusted,so dishonesty is assumed to occur to the signer.In the signature scheme, the signer owns the original message and the original key,so there may be two dishonest behaviors: one is to modify the original message,and the other is to modify the original key.

In both cases, we use the same method to find dishonest users.When the authentication fails, the verifier asks the aggregator for the signature key sent by each signer.Since the signature key is the result of the exclusive OR (XOR) of the original message and the original key,the aggregator cannot know the details, but the verifier can, so it can verify the aggregated key.Therefore, in theory, the number of faithless users that the scheme can tolerate is equal to the total number of signers,but this is an ideal situation,and it still requires trust in aggregators and validators.

4.5.Influence of quantum key distribution

In quantum key distribution, there is a definition called Plob boundary, which reflects the ability of the protocol to distribute the key.It can be expressed asR=−log2(1−η),whereRrepresents the key rate andηdenotes the channel transmittance between users.In general, the key rate should

Owing to the large number of photons lost in the channel,i.e.,the low transmittance of the channel,the key rate of most quantum key distribution protocols is limited by the key capacity of the protocol.Some protocols overcome the key capacity through single photon interference to improve the key rate,and can make the transmission distance lengthen to a staggering 830 km, but the phase tracking and phase locking technology are needed to compensate for the related fluctuation problems, which will increase the complexity of the experiment,and may cause related security risks.Some protocols[39]did not need phase tracking or phase locking technology, but used two-photon interference, through the time multiplexing and post-matching methods to break through the key capacity,but the transmission distance would decrease.In the same environment, a transmission range of 450 km can be achieved without phase tracking, and 270 km can be achieved further without phase locking technology.It weighs practicality and performance.

4.6.Quantum memory device

As the core of quantum repeater, quantum memory can capture and store entangled quantum,but up to now only 4 entangled quantum operation have been realized, so the related protocol relying on quantum memory is really not practical.In our scheme,the aggregator prepares quantum states according to the number of signers, and needs to conduct entanglement exchange of the signed quantum states,so it needs to store the quantum states it has, and with the increase of the number of signers and message length,the number of quantum states that need to be stored will increase, so this protocol cannot eliminate the quantum memory.It will take a long time for the protocol to move from theory to experiment.

5.Conclusions

In this work, we proposed a quantum homomorphic multi-signature scheme based on homomorphic aggregation,which reduces the dependence on the classical key,making it impossible for any attacker to forgery attack only by stealing the secret key and quantum state.In our scheme,the collector is able to aggregate multiple individual signatures consisting of quantum states into a new multi-signature, and the signature process conforms to additive homomorphism.According to the security analysis, the scheme is safe.Our scheme can produce fewer kinds of quantum states,higher signature complexity, and more kinds of verifiable information than traditional quantum multi-signature schemes.

Acknowledgement

Project supported by the National Natural Science Foundation of China(Grant No.61762039).