Secure quantum signature scheme without entangled state

Abstract

The security of most quantum signatures cannot be proved with security model under chosen-message attack. No formal proof can prove that their security is fully dependent on the basic quantum theory. Based on the orthogonal quantum state and key-controlled quantum hash function, an arbitrated quantum signature is proposed. In this scheme, the signatory produces the quantum signature by quantum-encrypting the output of key-controlled quantum hash function. The signature verification is performed by decrypting the signed message and comparing the decrypted message with the output of the key-controlled quantum hash function. The security of the proposed scheme depends on the indistinguishability of the unknown quantum sequence. Its unforgeability can be formally proved with security model under chosen-message attack. Therefore, its security can be supported by the formal proof. On the other hand, in the proposed scheme, no entangled state is used. It also has better qubit efficiency as well.

1 Introduction

With the gradual advancement of digitalization in today’s life, more and more messages need to be authenticated. That is, the receiver has to figure out the source of messages and checks whether they have been disturbed or eavesdropped or neither. To ensure the confidentiality and integrity of a message, Diffie et al. presented the theory of digital signature [1]. The signature generation process is essentially that the signer encrypts the message with his/her own signing key and the signing algorithm. Similarly, the signature verification process is essentially that the receiver decrypts the signature with the verifying key and verifying algorithm.

Digital signature schemes are used in various communication scenarios [2,3,4,5,6] to authenticate the identity of the communicator source and ensure the integrity and verifiability of communication data. Therefore, high requirements are put forward for the security of mathematic-problem-based digital signatures, whose safety barriers are built on the foundation of mathematic problems. However, according to the modern quantum research results, most of these problems such as discrete logarithm problem and prime factorization can be easily solved by quantum computers [7,8,9].

To keep the security of digital signature in the post-quantum era, Gottesman and Chuang introduced the idea of quantum digital signature [10] whose security was guaranteed by the quantum physics theory. Theoretically, the quantum signature not only can be unforgeable for the quantum adversary, but also can be secure against the eavesdropping attack.

The research result of reference [10] has opened up a new field of study: “quantum signatures” and many researchers have published abundant research results in this field. Among them, the most popular one is the arbitrated quantum signature (AQS) [11]. In the AQS scheme, there are three roles, signer, receiver and arbitrator. The signatory’s private key can be reused to sign different messages. The receiver verifies the signed messages. The arbitrator plays a role as a trusted party who helps the other parties sign or verify a message. What is more, the potential disputations between the signatory and the receiver can be solved by the arbitrator. Therefore, it seems that the AQS scheme is more practical than the one without any arbitrator. Based on the frame work in [11], a lot of researches on AQS schemes were developed. For example, in a proxy AQS scheme [12,13,14], the original signer is represented by the proxy signatory to produce a signature. In the blind AQS scheme [15, 16], the signatory signs a blind message such that the signer does not know what message is signed. In a designated verifier AQS [17, 18], only the designated receiver can verify the quantum signature.

However, although many AQSs have been presented, the security analysis of most AQSs is not perfect. There is not any security model in most of AQSs. The security of these existing schemes against forgery under chosen-message attacks(FU-CMA) cannot be formally deduced as the basic quantum mechanics theories. This means the security of these schemes against forgery under chosen-message attack cannot be guaranteed by the basic quantum mechanics theories. In fact, facing the quantum adversary’s chosen-message attacks, many AQSs were broken soon after being proposed. For examples, Jiang et al. [19, 20] proposed the practical AQSs based on the locally indistinguishable orthogonal product states, which were relatively easier to prepare than the entangled quantum states. Unfortunately, their schemes were insecure, because the receivers could generate the forgeries by adaptively modifying the received messages and applying some unitary operations on the corresponding quantum signatures [21, 22]. The scheme in [23] had some special properties such as blind message and proxy delegation. However, Zhou et al. [24] demonstrated that if some Hadamard operations were adaptively performed on the quantum signature in [23] then the corresponding signature could be used to generate a new forgery. Recently, Ding et al. [25] proved that the AQS scheme in [26] was insecure because a quantum adversary may transform the original signature to a forged signature on some new message by using the controlled-NOT operations. What's more, some similar chosen-message forgery attacks for the quantum signature schemes were proposed as well [27, 28]. Recently, Xin et al. presented the provably secure AQS based on the entanglement states in [31], which introduced the provable security idea of quantum signature. However, there is no formal security model in their scheme.

In this paper, a new AQS with security model is presented. The security of our AQS is formally proved under the security model. We prove the unforgeability of the proposed signature relies on the indistinguishability of the unknown quantum sequence. Furthermore, no partner needs to prepare entanglement state in our AQS. The proposed AQS also has better virtue in qubit efficiency. So, compared with the other similar AQSs, the security of our AQS can be supported by formal proof. It also has better practicability and efficiency than the similar AQSs.

The rest sections are organized as follows. Section 2 presents some preliminaries. We describe the proposed AQS in Sect. 3. In Sect. 4, we present the security proof of our AQS. The comparisons are showed in Sect. 5. The last section presents a brief conclusion.

2 Quantum one-way function

Definition 1

[10] We call a function F: x →|F_x⟩ as a quantum one-way function, if it satisfies: (1) Given x, it is easy to compute |F_x⟩ within polynomial time; (2) Given |F_x⟩, it is hard to invert x within polynomial time.

In this paper, we use “||” stands for the classical-bit connection. Let $k = \left( {k_{1} ,k_{2} , \cdots ,k_{l} } \right)$ be an l-bit string. Let $H = \frac{1}{\sqrt 2 }\left( {\begin{array}{*{20}c} 1 & 1 \\ 1 & { - 1} \\ \end{array} } \right)$, $I = \left( {\begin{array}{*{20}c} 1 & 0 \\ 0 & 1 \\ \end{array} } \right)$ and $Y = \left( {\begin{array}{*{20}c} 0 & 1 \\ { - 1} & 0 \\ \end{array} } \right)$ stand for Hadamard operation, identity operation and Y operation, respectively. Let the operator $Y^{ + } = \left( {\begin{array}{*{20}c} 0 & { - 1} \\ 1 & 0 \\ \end{array} } \right)$.

Assume that $f:\left\{ {0,1} \right\}^{*} \to \left\{ {0,1} \right\}^{n}$, $g:\left\{ {0,1} \right\}^{*} \to \left\{ {0,1} \right\}^{n}$ and $h:\left\{ {0,1} \right\}^{*} \to \left\{ {0,1} \right\}^{n}$ are three classical one-way hash functions with uniform outputs. In the following, based on the hash functions f, g and h, the key-controlled quantum one-way hash function is constructed.

Given k, define the key-controlled hash function as follows:

$$ F_{k} (m) = \otimes_{i = 1}^{n} H^{{g_{i} }} Y^{{h_{i} }} \left| {f_{i} } \right\rangle ,\;\forall m \in \left\{ {0,1} \right\}^{*} $$

(1)

where f(k||m) = (f₁, f₂, …, f_n), g(k||m) = (g₁, g₂, …, g_n) and h(k||m) = (h₁, h₂, …, h_n).

It is clear that, given m, it is easy to compute F_k(m). However, Given F_k(m), it is hard to invert m due to the one-way property of the hash function f. Therefore, the function F_k(.) can be seemed as a key-controlled quantum one-way hash function.

$$ F_{k} :\;\left\{ {0,{ 1}} \right\}^{l + } \, \to \,\{ |\left. 0 \right\rangle ,|\left. {1} \right\rangle ,|\left. + \right\rangle ,|\left. - \right\rangle \}^{n} , $$

which is controlled by the parameter key k. According to Eq. (1), it follows that the input of F_k includes the parameter k and message m. Therefore, the bit length of the input of F_k is at least l, while the qubit length of the output of F_k is n. It is necessary to require that $l - n > > {1}$ . This is because that, according to Holevo’s theorem [35], no more than n bits of information can be extracted by measuring n qubits. Then, given F_k(m), no more than n bits of information on the input can be extracted. Therefore, the probability of successfully guessing the key k remains small when $l - n > > {1}$. That is, the probability of successfully guessing the key k is

$$ p\left( k \right) = {1}/{2}^{(l - n)} \to 0\left( {{\text{l}} \to \infty } \right). $$

For example, if $l = {256}$ and$n = {128}$, it follows that$p\left( k \right) \approx {2}.{938735877}0{55719} \times {1}0^{{ - {39}}}$ . Therefore, the parameter l can be set by the system according the security level.

3 The proposed AQS scheme

The AQS involves three partners: Trent (a trusted arbitrator), Alice (the signatory) and Bob (the signature receiver). The scheme contains three processes: initialization process, signing process and verification process.

3.1 Initialization process

Signatory Alice shares secret key $k = \left( {k_{1} ,k_{2} , \cdots ,k_{l} } \right)$ (l >  > n) with Trent by the secure quantum key distribution protocol (QKDP) [29]. Similarly, she shares secret keys $x = \left( {x_{1} ,x_{2} , \cdots ,x_{n} } \right)$ and $y = \left( {y_{1} ,y_{2} , \cdots ,y_{n} } \right)$ with the receiver Bob by the QKDP [29].

3.2 Signing process

The message $m \in \{ 0,1\}^{*}$ is signed by performing the following signing steps:

• Sign-1. Alice computes the hash value ${F}_{k}(m)$ with the key-controlled quantum one-way hash function and her secret k:

  $$ F_{k} (m) = \left| M \right\rangle = \otimes_{i = 1}^{n} \left| {M_{i} } \right\rangle . $$

  (2)

• Sign-2. Alice generates her signature $\left| S \right\rangle = \otimes_{i = 1}^{n} \left| {S_{i} } \right\rangle$ by performing the controlled H operator and Y operator on each $\left| {M_{i} } \right\rangle$ with the secret keys x and y, where each

  $$ \left| {S_{i} } \right\rangle = Y^{{x_{i} }} H^{{y_{i} }} \left| {M_{i} } \right\rangle . $$

  (3)

• Sign-3. Alice generates sufficient decoy particles for eavesdropping detection. All decoy particles are picked randomly in {|0⟩,|1⟩,|+⟩,|−⟩}. Then, Alice inserts these decoy states into |S⟩ randomly and records the location and state of every decoy state. After that, she obtains a non-orthogonal qubit string |S_A⟩. Then, Alice sends (m,|S_A⟩) to Bob.

3.3 Verification process

The signed message is verified by the steps as follows:

• Verify-1. While Bob receives Alice’s (m,|S_A⟩), Alice publishes the information of all the decoy states in the qubit string |S_A⟩ such as their states and locations. Bob measures all decoy states in |S_A⟩ and compares the measurement results with the decoy states published by Alice. If the error rate of the measurement is higher than the threshold set by the communication system, the signature scheme should restart. If not, Bob obtains the signature $\left| S \right\rangle$ from the |S_A⟩ by discarding all the decoy states.

• Verify-2. Bob performs the key-controlled Hadamard operation and Y operation on all quantum states in $\left| S \right\rangle$ with the shared keys x and y and gets.

  $$ \left| {M^{\prime } } \right\rangle = \otimes_{i = 1}^{n} \left| {M_{i}^{\prime } } \right\rangle , $$

  (4)

  where each

  $$ \left| {M_{i}^{\prime } } \right\rangle = H^{{y_{i} }} \left( {Y^{ + } } \right)^{{x_{i} }} \left| {S_{i} } \right\rangle . $$

  (5)

  Next, he generates sufficient decoy states for eavesdropping detection. Then, he inserts these decoy states into $\left| {M^{\prime } } \right\rangle$ and gets $\left| {M_{B}^{\prime } } \right\rangle$. Bob records the locations and states of all the decoy qubits. Finally, Bob sends (m, $\left| {M_{B}^{\prime } } \right\rangle$) to Trent.

• Verify-3. After Trent receives Bob’s (m, $\left| {M_{B}^{\prime } } \right\rangle$), Trent performs the eavesdropping check operations which are similar as those did in the step Verify-1. If the quantum channel is not eavesdropped, Trent obtains $\left| {M^{\prime } } \right\rangle = \otimes_{i = 1}^{n} \left| {M_{B}^{\prime } } \right\rangle$ by discarding the decoy states. By using the key-controlled quantum hash function and the shared k, Trent computes F_k(m). Theoretically, the quantum signature is valid only if

  $$ F_{k} (m) = \left| {M^{\prime } } \right\rangle . $$

  (6)

Then, to verify Eq. (6), Trent calculates g(k||m) = (g₁, g₂, …, g_n) and h((k||m) = (h₁, h₂, …, h_n). Then, he performs the key-controlled operations and gets $\left| {f^{\prime } } \right\rangle = \otimes_{i = 1}^{n} \left| {f_{i}^{\prime } } \right\rangle$, where each $\left| {f_{i}^{\prime } } \right\rangle = \left( {Y^{ + } } \right)^{{h_{i} }} H^{{g_{i} }} \left| {M_{i}^{\prime } } \right\rangle$. Next, he measures each $\left| {f_{i}^{\prime } } \right\rangle$ with base $\left\{ {\left| {0} \right\rangle ,\left| {1} \right\rangle } \right\}$ and gets the measurement result $f_{i}^{\prime } : = \left\{ {\begin{array}{*{20}c} {0,} & {{\text{if}}\; \, \left| {f_{i}^{\prime } } \right\rangle = \left| 0 \right\rangle } \\ {1,} & {{\text{if}}\; \, \left| {f_{i}^{\prime } } \right\rangle = \left| 1 \right\rangle } \\ \end{array} } \right.$. Let $f^{\prime } = \left( {f_{1}^{\prime } ,f_{2}^{\prime } , \cdots ,f_{n}^{\prime } } \right)$. Trent calculates f(k||m) and checks whether f(k||m) = f′. If f(k||m) = f′, Trent confirms Eq. (6) holds and publishes “True,” and Bob accepts the signature. Or Trent publishes “False” and Bob rejects the signature.

On the other hand, after the information “True” is published, Trent stores (m, f′) as the verification proof.

4 Security analysis

The correctness of our AQS is obvious. This section mainly presents the security analysis of the proposed AQS.

The security of the secret keys is analyzed in Sect. 4.1. The formal proof of unforgeability of the quantum signature is presented in Sect. 4.2.

4.1 The security of the secret keys

During initialization phase, signatory Alice generates secret keys k_, x and y by performing QKD protocol such as the BB84 protocol in [29]. According to the research result in [30], it follows that the BB84 protocol should be unconditional secure. Therefore, there is no adversary who has the ability of breaking the secret keys of the signatory in initialization phase.

During the signing phase, the signatory Alice generates the signature by computing quantum hash function value and encrypting the quantum states. This means that the quantum signature must include some information of these keys. For a signing system, anyone including the quantum adversary can access to the system and get the signer’s signature. A quantum adversary may adaptively ask polynomial quantum signatures from the signing system. He/She measures the quantum signatures so as to obtain some bits of the signer's keys. However, the security proof as follow shows that the AQS is information-theoretically secure so that it is impracticable for quantum adversary to deduce the secret information from the signature.

Suppose there is a quantum-adversary Eve (for example, the signature receiver Bob), who wants to get some information about the secret keys through message-signature pair. That means Eve should measure the quantum signatures. However, in the following, by computing the trace distance of density operators for different quantum signatures, the indistinguishability of the quantum signatures can be proved.

Theorem 1

Any quantum signature always has the same density operator.

Proof

In our scheme, we use QKD protocol [29] to ensure the secret keys x and y are unconditionally secure during the system initialization. Assume x and y have the uniform distribution. According to Eq. (3), for the adversary, the state of S_i depends on the distributions of the random x_i and y_i. Then, S_i can be seemed as mixed ensembles with distribution.

$$ \left\{ {\begin{array}{*{20}c} {\left| {M_{i} } \right\rangle } & {Y\left| {M_{i} } \right\rangle } & {H\left| {M_{i} } \right\rangle } & {YH\left| {M_{i} } \right\rangle } \\ {1/4} & {1/4} & {1/4} & {1/4} \\ \end{array} } \right\}. $$

A density operator is commonly used to represent the state of the mixed ensembles. Therefore, the state of S_i can be described as its density operator $\rho_{{S_{i} }}$. By Eq. (3), the density operator $\rho_{{S_{i} }}$ of S_i is computed as below:

$$ \begin{aligned} \rho_{{S_{i} }} & = \frac{{1}}{{4}}\sum\limits_{{x_{i} ,y_{i} \in \{ 0,1\} }} {Y^{{x_{i} }} H^{{y_{i} }} \left| {M_{i} } \right\rangle \left\langle {M_{i} } \right|H^{{y_{i} }} \left( {Y^{ + } } \right)^{{x_{i} }} } \\ & = \frac{{1}}{{4}}\left( {\left| {M_{i} } \right\rangle \left\langle {M_{i} } \right| + Y\left| {M_{i} } \right\rangle \left\langle {M_{i} } \right|Y^{ + } + H\left| {M_{i} } \right\rangle \left\langle {M_{i} } \right|H + YH\left| {M_{i} } \right\rangle \left\langle {M_{i} } \right|HY^{ + } } \right) \\ & = \frac{I}{2} \\ \end{aligned} $$

Note that the signature $\left| S \right\rangle = \otimes_{i = 1}^{n} \left| {S_{i} } \right\rangle$. Then, it follows that for any quantum signature, its density operator should be the same $\rho_{S} = \otimes_{i = 1}^{n} \rho_{{S_{i} }} = \frac{{I^{ \otimes n} }}{{2^{n} }}$.

According to the concept of indistinguishability for the classical private-key encryption [32], Yang et al. [33] defined the information-theoretic indistinguishability for a quantum private-key encryption scheme.

Definition 2

[33] A quantum private-key encryption scheme (G, E, D) is information-theoretically indistinguishable if, for every quantum circuit family {C_n}, for every positive polynomial p(⋅), for all sufficiently large n, and for every x, y ∈ {0,1}^poly(n) (i.e., |x| =|y|),

$$ \left| {\Pr \left[ {C_{n} \left( {E_{{G(1^{n} )}} (x) = 1} \right)} \right] - \Pr \left[ {C_{n} \left( {E_{{G(1^{n} )}} (y) = 1} \right)} \right]} \right| < 1/p(n), $$

where the encryption algorithm E should be a quantum algorithm, G is an internal coin tosser for the algorithm, and the ciphertexts E(x), E(y) are quantum states.

What is more, in [33], Yang et al. proved that the information-theoretical security of a quantum private-key encryption scheme depended on the distance of the density operators of cipher states.

Theorem 2

[33] For all plaintexts x and y, let the density operators of cipher states E(x) and E(y) be ρ_x and ρ_y, respectively. A quantum private-key encryption scheme is said to be information-theoretically indistinguishable if, for every positive polynomial p(⋅) and every sufficiently large n, D(ρ_x, ρ_y) < 1/p(n).

A quantum signature scheme can be seemed as a quantum private-key encryption scheme. Therefore, according to Theorem 2, it follows Corollary 1, which can be used to prove the information-theoretical security a quantum signature scheme [31].

Corollary 1

[31] For any positive polynomial p(.) and two different quantum signatures $\left| S \right\rangle$ and $\left| {S^{*} } \right\rangle$, if their trace distance $D(\rho_{S} ,\rho_{{S^{*} }} ) < \frac{1}{p(n)}$, the quantum signature scheme will be information-theoretically secure. This means no distinguishing algorithm can efficiently draw a distinction between quantum signatures $\left| S \right\rangle$ and $\left| {S^{*} } \right\rangle$.

Theorem 3

The proposed quantum signature has the information-theoretical security.

Proof

According to Theorem 1, it follows that for any two different quantum signatures $\left| S \right\rangle$ and $\left| {S^{*} } \right\rangle$, their density operators are the same. This means $D(\rho_{S} ,\rho_{{S^{*} }} ) = 0$. Therefore, according to Corollary 1, it follows that the proposed quantum signature has the information-theoretical security. This means there is no any algorithm which can efficiently distinguish $\left| S \right\rangle$ and $\left| {S^{*} } \right\rangle$.

Theorem 3 shows that it is infeasible for Eve to get some useful information about the secret keys x and y by measuring and distinguishing the quantum signatures.

Theorem 4

For different inputs, the outputs of $F_{k} ( \cdot )$ have the same density operator.

Proof

Note the outputs of $F_{k} ( \cdot )$ is $F_{k} (m) = \left| M \right\rangle = \otimes_{i = 1}^{n} \left| {M_{i} } \right\rangle$. Assume the hash functions f, g and h have the uniform outputs. Note that f: {0, 1}^* → (f₁, f₂, …, f_n), g: {0, 1}^* → (g₁, g₂, …, g_n) and h: {0, 1}^* → (h₁, h₂, …, h_n). For the adversary, because the distributions of the outputs (f₁, f₂, …, f_n), (g₁, g₂, …, g_n) and (h₁, h₂, …, h_n) are all uniform, each g_i, h_i and f_i (i = 1, 2,…, n) can randomly take the values of 0 and 1. Then, by Eq. (1), we can obtain the density operator of M_i.

$$ \begin{aligned} \rho_{{M_{i} }} & = \frac{{1}}{{8}}\sum\limits_{{g_{i} ,h_{i} ,f_{i} \in \{ 0,1\} }} {H^{{g_{i} }} Y^{{h_{i} }} \left| {f_{i} } \right\rangle \left\langle {f_{i} } \right|\left( {Y^{ + } } \right)^{{h_{i} }} } H^{{g_{i} }} \\ & = \frac{{1}}{{8}}\sum\limits_{{f_{i} \in \{ 0,1\} }} {\left( {\left| {f_{i} } \right\rangle \left\langle {f_{i} } \right| + Y\left| {f_{i} } \right\rangle \left\langle {f_{i} } \right|Y^{ + } + H\left| {f_{i} } \right\rangle \left\langle {f_{i} } \right|H + HY\left| {f_{i} } \right\rangle \left\langle {f_{i} } \right|Y^{ + } H} \right)} \\ & = \frac{I}{2} \\ \end{aligned} $$

It follows that $\rho_{M} = \otimes_{i = 1}^{n} \rho_{{M_{i} }} = \frac{{I^{ \otimes n} }}{{2^{n} }}$.

Theorem 5

The key-controlled hash value $F_{k} (m) = \left| M \right\rangle = \otimes_{i = 1}^{n} \left| {M_{i} } \right\rangle$ is information-theoretically secure.

Proof

It follows from Theorem 4 that, for any m ≠ m’, $\rho_{M} = \rho_{{M^{\prime}}} = \frac{{I^{ \otimes n} }}{{2^{n} }}$. Therefore, $D(\rho_{M} ,\rho_{{M^{\prime}}} ) = 0$. Therefore, the key-controlled hash value is information-theoretically secure.

In our scheme, the signature receiver Bob can get $\left| M \right\rangle$ the during the signature verification phase. However, Theorem 5 shows that $\left| M \right\rangle$ is information-theoretically secure. This means $\left| M \right\rangle$ is theoretically indistinguishable. Therefore, it is infeasible for Eve to get some useful information about $(f_{1} , \, f_{2} , \, \cdots , \, f_{n} )$, $(g_{1} , \, g_{2} , \, \cdots , \, g_{n} )$ and $(h_{1} , \, h_{2} , \, \cdots , \, h_{n} )$ by distinguishing $\left| M \right\rangle$. Note that f(k||m) = (f₁, f₂, …, f_n), g(k||m) = (g₁, g₂, …, g_n) and h(k||m) = (h₁, h₂, …, h_n), where f, g and h are the one-way hash functions. Without $(f_{1} , \, f_{2} , \, \cdots , \, f_{n} )$, $(g_{1} , \, g_{2} , \, \cdots , \, g_{n} )$ and $(h_{1} , \, h_{2} , \, \cdots , \, h_{n} )$, it’s hard for Eve to obtain the secret key k from $\left| M \right\rangle$.

Moreover, in our scheme, the quantum channel is checked by using eavesdropping detection technology. The adversary’s eavesdropping will disturb the decoy particles inserted into the quantum channel. Therefore, the adversary’s eavesdropping will be detected by the partners.

4.2 Unforgeability

The security of most AQSs against forgery attack was analyzed without security model and formal security proof. In this section, we formally prove the unforgeability of our AQS with security model under chosen-message attack.

4.2.1 Random oracle F _k

In our scheme, the key-controlled quantum hash function F_k is used. According to Theorem 4, it follows the output of F_k can be uniform if the hash functions f, g and h have the uniform distributions. Then, in the security analysis as follows, F_k is seemed as a random oracle mapping each possible query m ∈ {0, 1}^* to a fixed random response $\left| M \right\rangle = \otimes_{i = 1}^{n} \left| {M_{i} } \right\rangle \in \left\{ {\left| {0} \right\rangle ,\left| {1} \right\rangle ,\left| { + } \right\rangle ,\left| - \right\rangle } \right\}^{n}$.

4.2.2 Existential unforgeability

To our knowledge, most of the forgery attacks are FU-CMA. Simply speaking, the adversary generates the forgery based on the received quantum signatures. As discussed in Sect. 1, although many AQSs have been presented, their security against FU-CMA cannot be formally proved. No sufficient proof can prove that their security depends on the basic quantum mechanics theories. Some AQSs have been proved to be insecure against FU-CMA.

This section presents the formal security proof of the new AQS against FU-CMA. Its security can be guaranteed by the basic quantum mechanics principle, the indistinguishability of the unknown quantum state.

For an AQS, the FU-CMA game can be described as follows:

• Initialization(l) → (k_r, k_T). Given the security parameter l as input, this algorithm outputs the private keys (k_r, k_T). That is, by performing the unconditionally secure QKDP, the challenger shares private keys k_r and k_T with the receiver and the trusted arbitrator, respectively.

In the game, the signer Alice plays the role of challenger:

• Signature query(m_i) → $\sigma_{{m_{i} }}$. Given a message m_i ∈ {0, 1}^* as input, this algorithm outputs a quantum signature $\sigma_{{m_{i} }}$. That is, the adversary can adaptively select polynomial messages m₁, m₂,…, m_p(n) for signature query, where p(.) is a polynomial. For the message m_i submitted by the adversary, the challenger executes the signature generation algorithm and produces the signature $\sigma_{{m_{i} }}$. Then, the challenger sends the signature to the adversary.

In the game, the signature receiver Bob plays the role of adversary:

• Forgery. After the polynomial signature queries, the adversary Ad outputs a forged signature $\sigma_{{m^{*} }}$ for some message m^∗.

  If $\sigma_{{m^{*} }}$ is valid and the signature on m^∗ has never been queried before, the adversary wins the game. Let FogWin_Ad be the probability that adversary Ad wins the game.

  Definition 3

  A quantum forger Ad (q_S, q_F, ε)-breaks a quantum signature scheme if Ad wins the FU-CMA game with the probability at least ε by querying at most q_S signatures to the signature oracle and at most q_F queries to the random oracle. An AQS scheme is (q_S, q_F, ε)-existentially secure against UF-CMA if no forger can (q_S, q_F, ε)-break it.

  Theorem 6

  Our AQS is (q_S, q_F, ε)-secure against UF-CMA in the random oracle model. No forger can (q_S,q_F,ε)-break it.

  Proof

  Assume there is a quantum adversary Ad, who can (q_S, q_F, ε)-break our AQS. We construct the FU-CMA game between a challenger Ch and the adversary Ad. To simplify the game description, in the following, let the signer Alice play role of challenger Ch. Bob plays the role of adversary Ad, who masters more quantum sources than the outside adversary. Trent is a trusted arbitrator. Now, Alice receives an unknown particle sequence N = (N₁, N₂, …, N_n), whose state is $\left| N \right\rangle = \otimes_{i = 1}^{n} \left| {N_{i} } \right\rangle \in \left\{ {\left| 0 \right\rangle ,\left| 1 \right\rangle ,\left| + \right\rangle ,\left| - \right\rangle } \right\}^{n}$. Alice’s goal is to accurately distinguish the unknown quantum sequence N.

• Initialization. It is the same as that described in Sect. 3.1.

• Random oracle query. Assume that the random oracle F_k (please refer to Sect. 4.2.1) can be queried at most q_F times. Ch keeps a list RO-List, which is initially empty. If the oracle is queried about the message m_j, the following steps are performed.

  Ch checks the RO-List.

  If RO-List has contained a record (m_j, b_j, r_j, w_j) on m_j, where b_j = 0, $r_{j} = \left( {r_{j}^{1} ,r_{j}^{2} , \cdots ,r_{j}^{n} } \right) \in \{ 0,1\}^{n}$ and $w_{j} = \left( {w_{j}^{1} ,w_{j}^{2} , \cdots ,w_{j}^{n} } \right) \in \{ 0,1\}^{n}$, Ch computes $\left| {N^{j} } \right\rangle = \otimes_{i = 1}^{n} H^{{r_{j} }} Y^{{w_{j} }} \left| {N_{i} } \right\rangle$ and outputs $\left| {N^{j} } \right\rangle$ as the answer.

  If RO-List has contained a record (m_j, b_j) on m_j, where b_j = 1, according to Eqs. (1–2), Ch computes $\left| {N^{j} } \right\rangle = F_{k} (m_{j} ) = \left| M \right\rangle = \otimes_{i = 1}^{n} \left| {M_{i} } \right\rangle$ and outputs $\left| {N^{j} } \right\rangle$ as the answer.

  If RO-List does not contain any record on m_j, Ch flips a random coin with the result b_j ∈ {0, 1} such that the probability $p(b_{i} = 0) = \frac{1}{{q_{S} \, + \, 1}}$. If b_j = 0, Ch randomly generates two n-tuples $r_{j} = \left( {r_{j}^{1} ,r_{j}^{2} , \cdots ,r_{j}^{n} } \right) \in \{ 0,1\}^{n}$ and $w_{j} = \left( {w_{j}^{1} ,w_{j}^{2} , \cdots ,w_{j}^{n} } \right) \in \{ 0,1\}^{n}$, computes $\left| {N^{j} } \right\rangle = \otimes_{i = 1}^{n} H^{{r_{j} }} Y^{{w_{j} }} \left| {N_{i} } \right\rangle$ and outputs $\left| {N^{j} } \right\rangle$ as the answer. Then, Ch adds the record (m_j, b_j, r_j, w_j) to the RO-List. If b_j = 1, according to Eqs. (1–2), Ch computes $\left| {N^{j} } \right\rangle = F_{k} (m_{j} ) = \left| M \right\rangle = \otimes_{i = 1}^{n} \left| {M_{i} } \right\rangle$ and outputs $\left| {N^{j} } \right\rangle$ as the answer. Then, Ch adds the record (m_j, b_j) to the RO-List.

• Signature oracle query. Assume that the signature oracle can be queried at most q_S times. When the signature oracle is queried on m_j, Ch queries the random oracle on m_j. If the record on m_j in RO-List is (m_j, b_j, r_j, w_j), it means that b_j = 0. In this case, Ch outputs ‘Fail’. If the record on m_j in RO-List is (m_j, b_j), it means that b_j = 1. In this case, Ch performs the signing steps described in Sect. 3.2 and outputs the valid quantum signature (m_j, |S⟩) as the answer.

  Assume that the signature oracle successfully outputs all the answers without ‘Fail,’ and after the querying phase, Ad generates a forgery (m^*, $\left| {S^{*} } \right\rangle = \otimes_{i = 1}^{n} \left| {S_{i}^{*} } \right\rangle$) which can pass the signature verification, while the signature oracle has never output the AQS on m^*. Note that before generating the forgery (m^*, $\left| {S^{*} } \right\rangle$), Ad has to query the random oracle on m^*. If the record on m^* in RO-List is $\left( {m^{*} ,b_{j}^{*} ,r_{j}^{*} ,w_{j}^{*} } \right)$, the game outputs ‘Success,’ or it outputs ‘Fail.’

  If the game outputs ‘Success,’ it follows that the forgery satisfies the signature verification Eqs. (4–6). That is $F_{k} (m^{*} ) = \otimes_{i = 1}^{n} H^{{y_{i} }} \left( {Y^{ + } } \right)^{{x_{i} }} \left| {S_{i}^{*} } \right\rangle$, where $F_{k} (m^{*} ) = \left| {N^{*} } \right\rangle$ is the output of the random oracle in the game. Therefore, according to the output of the random oracle in the game and Eqs. (4–6), it follows that

  $$ \left| {N^{*} } \right\rangle = \otimes_{i = 1}^{n} H^{{r_{i}^{*} }} Y^{{w_{i}^{*} }} \left| {N_{i} } \right\rangle = \otimes_{i = 1}^{n} H^{{y_{i} }} \left( {Y^{ + } } \right)^{{x_{i} }} \left| {S_{i}^{*} } \right\rangle . $$

  (7)

  According to Eq. (7), it follows that

  $$ \left| N \right\rangle = \otimes_{i = 1}^{n} \left| {N_{i} } \right\rangle = \otimes_{i = 1}^{n} \left( {Y^{ + } } \right)^{{w_{i}^{*} }} H^{{r_{i}^{*} \oplus y_{i} }} \left( {Y^{ + } } \right)^{{x_{i} }} \left| {S_{i}^{*} } \right\rangle , $$

  (8)

  in which $\left| {S^{*} } \right\rangle = \otimes_{i = 1}^{n} \left| {S_{i}^{*} } \right\rangle$ is the forgery generated by the adversary, who masters the generation process of each $\left| {S_{i}^{*} } \right\rangle$. Therefore, by performing the game, the state of the unknown quantum sequence N can be accurately distinguished as $\left| N \right\rangle$ described in Eq. (8). Therefore, based on Eq. (8) and the knowledge of Ad’s (the generation process of each $\left| {S_{i}^{*} } \right\rangle$), we can master the evolution history of $\left| N \right\rangle$, which conflicts with the indistinguishability of the unknown particle sequence N = (N₁, N₂, …, N_n).

  Now, we analysis the probability of obtaining the evolution history of $\left| N \right\rangle$. Note that the adversary can (q_S, q_F, ε)-break our quantum signature scheme. This means that the following conditions should be satisfied. (i) The signature oracle successfully outputs all the answers. (ii) The adversary successfully generates a forgery (m^*, $\left| {S^{*} } \right\rangle = \otimes_{i = 1}^{n} \left| {S_{i}^{*} } \right\rangle$) which can pass the signature verification. (iii) The record on m^* in RO-List is $\left( {m^{*} ,b_{j}^{*} ,r_{j}^{*} ,w_{j}^{*} } \right)$. The conjunction of these occurs with the probability

  $$ p = \left( {1 - \frac{1}{{1 + q_{S} }}} \right)^{{q_{s} }} \cdot \varepsilon \cdot \frac{1}{{1 + q_{S} }}, $$

  (9)

  according to which we can get $p \ge \frac{\varepsilon }{{eq_{S} }}$, where e is natural constant approximately equal to 2.718. This means that if ε is non-negligible probability, the sequence N can be accurately discriminated with a non-negligible probability p as well, which conflicts with the indistinguishability of N. Therefore, our AQS scheme is (q_S, q_F, ε)-secure against UF-CMA.

4.2.3 Non-repudiation

Section 4.2.2 shows the proof that the outside adversaries including Bob cannot forge the signature. Note that Trent is a trusted arbitrator, who will not forge any of the signer’s signatures. Therefore, Alice and Bob cannot refuse a valid signature because of the property of unforgeability.

In our scheme, after the AQS verification, Trent stored (m, f′) for each valid AQS. If Alice denies the generation of AQS on m, Trent can verify whether f(k||m) =  f′. If f(k||m) =  f′, it follows that Alice has produced the AQS for the receiver, since only Alice shares the secret k with the arbitrator. What is more, Bob cannot refuse that he has ever get the AQS on m, since the signature-proof (m, f′) is derived from (m, $\left| {M_{B}^{\prime } } \right\rangle$), which was sent by Bob.

5 Comparisons

First, in our scheme, the security model for AQS under chosen-message attack is introduced. Our AQS can be proved to be secure against FU-CMA with formal security proof. In [25], neither security model no provable security proof was presented to support the corresponding security analysis results. In [31], the security of the scheme was proved without any security model.

Second, in [25, 31], the signer has to prepare the entangled particles so as to sign a message. In our scheme, there is not any entangled particle used to generate signatures.

Finally, we analysis the qubit efficiency of the similar schemes. The qubit efficiency [34] is defined as $\delta = \frac{{\delta_{1} }}{{\delta_{2} }}$, where δ₁(δ₂) is the count of transmitted bits (qubits) in the protocol. (Decoy states for detecting eavesdropping are ignored.) In our scheme, 2n qubits are transmitted, while n-bit message is authenticated. Then, the qubit efficiency of our scheme is $\delta = \frac{n}{2n} = 50\%$. The qubit efficiency of the similar schemes is showed in Table 1 as follows.

Table 1 Comparisons of the similar schemes

6 Conclusions

There is not any security model in most of AQSs. Their security cannot be formally proved. This means no sufficient proof can support their security against FU-CMA.

Then, the security model for AQS under FU-CMA was introduced. We propose a new AQS with security model. The security of the proposed quantum signature against FU-CMA can be proved under random oracle.

The proposed AQS can be used to sign bit message without using any entangled state.

The qubit efficiency of our AQS achieves 50%.

Table 1 shows the advantages of the proposed AQS.