1. Introduction

Cryptography is essential for uncounted amount of applications that rely on non-repudiation, integrity and confidentiality of data. The two pillars of modern cryptography are encryption and digital signatures [1], where encryption guarantees confidentiality and digital signatures provide integrity and non-repudiation. Traditionally, public-key cryptography algorithms, such as the Rivest-Shamir-Adleman algorithm [2], are designed to simultaneously provide encryption and digital signature service. However, relying on the computational difficulty of certain mathematical problems, public-key cryptosystems are usually vulnerable to quantum computing attacks [3]. Quantum key distribution (QKD) allows two remote users to share a secret key string with information-theoretic security [4,5]. By combining one-time pad encryption [6] and QKD, one can implement information communication with perfect confidentiality [7]. In addition, the direct transmission of private information is made possible in principle by quantum encryption [8].

Digital signatures are widely applied in e-mails, electronic commerce and software distribution to ensure data integrity and non-repudiation [9]. Similar to QKD used for encryption service, quantum digital signatures (QDS) are expected to provide information-theoretic security to sign documents. The first QDS protocol was proposed in 2001 [10], but it is unfeasible because of challenging experimental requirements. In the next decade or so, great efforts have been made in developing QDS protocols and an important achievement was the removal of the requirement of quantum memory [11–15]. Nevertheless, the security analysis of the early QDS protocols are based on secure quantum channels, i.e., there is no eavesdropping, which is a conflicting assumption. In 2016, two independent QDS protocols were proposed and proved to be secure against the general attacks without the assumption of secure quantum channels [16,17]. Importantly, their experimental devices and techniques have already been widely employed in QKD. These two protocols are important steps towards practical QDS [9]. The one in [16] is based on non-orthogonal encoding. The other [17] utilizes orthogonal encoding, which results in the need of an additional symmetrization step in the protocol. In addition, great achievements have been made in the experimental and theoretical research of information-theoretically secure QDS [18–29], including the field test of measurement-device-independent (MDI) QDS [21].

For the orthogonal encoding based protocol [17] (see also [18,27]), the need of the symmetrization step, which requires an additional secure classical channel, is the main issue. Currently, secure classical channels can only be realized by combining QKD and one-time pad encryption. The symmetrization step will consume $6L$ bits of secret key generated by QKD if one uses $L$ bits as the signature [21]. Specially, in the worst case where the signer is located in the middle of two receivers, the low secret key rate of QKD between the two receivers severely limits the real-time signature rate of QDS. Besides, considering a quantum network with $J$ users, there will be a need of $J(J-1)/2$ secure classical channels [22], which is an unrealistically high amount in a real quantum network. For the non-orthogonal encoding based protocol [16], it does not require the symmetrization step. However, the signer has to send the same quantum states to two receivers. Only coincidence detection events, i.e., the two receivers both have click, are valid events. Let $\eta$ be the probability that one receiver has click, if the signer sends $N$ quantum states to the two receivers, there will be only $\eta ^{2} N$ valid events. Therefore, the signature rate quadratically scales with the probability of detection events.

Here, inspired by the original protocol in [16], we propose an efficient quantum digital signature protocol without symmetrization step. A novel classical post-processing operation called post-matching method is exploited in our protocol. With the help of the post-matching method, the requirement of coincidence detection is removed. Given that the signer sends $N$ quantum states to receivers, there will be $\eta N$ valid events. Therefore the signature rate decays linearly with the probability of detection events. Simulation results show that the signature rate of our scheme is $2$ or even $3$ orders of magnitude higher than that of Ref. [16] in large attenuation case, and is comparable to orthogonal encoding based protocol.

2. Protocol description

There are three participants in our protocol, namely the signer Alice and the receiver Bob and Charlie. As determined by Alice, either Bob or Charlie can be the authenticator of the signature, and the other becomes the verifier. There are noisy insecure quantum channels connecting Alice-Bob and Alice-Charlie, and authenticated classical channels between the three participants. There are three stages in our protocol: key generation, estimation and messaging. In our protocol, the three stages can be performed separately, which means they can generate raw keys and store them for a long time, and continue the estimation and messaging stage whenever Alice wants to sign the message. This makes our protocol more practical.

Our protocol exploits non-orthogonal encoding to generate logical bits [30]. There are four quantum states: ${\left |{H}\right \rangle }$, ${\left |{V}\right \rangle }$, ${\left |{+}\right \rangle }$ and ${\left |{-}\right \rangle }$, where ${\left |{H}\right \rangle }$ and ${\left |{V}\right \rangle }$ are the eigenstates of the Pauli Z operator and ${\left |{+}\right \rangle }$ and ${\left |{-}\right \rangle }$ ( ${\left |{\pm }\right \rangle }=\frac {1}{\sqrt {2}}($|H〉$\pm$|V 〉$)$) are the eigenstates of the Pauli X operator. These four quantum states can be arranged into four sets: $\{{\left |{H}\right \rangle }, {\left |{+}\right \rangle }\}$, $\{{\left |{+}\right \rangle }, {\left |{V}\right \rangle }\}$, $\{{\left |{V}\right \rangle }, {\left |{-}\right \rangle }\}$, $\{{\left |{-}\right \rangle }, {\left |{H}\right \rangle }\}$, where the first state in each set is encoded with bit value 0 and the second is encoded with 1. Alice randomly sends quantum states to receivers and assigns each quantum state to a set. The receivers randomly choose Z or X basis to perform polarization measurement on each quantum state. If the measurement outcome is orthogonal to one of the states in the set, the receiver obtains a conclusive result with bit value 0 or 1, otherwise the receiver obtains an inconclusive result, denoted by $\bot$. Note that the set assigned by Alice should contain the quantum state she sent. For example, if Alice sends ${\left |{H}\right \rangle }$, she should assign it to set $\{{\left |{H}\right \rangle }, {\left |{+}\right \rangle }\}$ or $\{{\left |{-}\right \rangle }, {\left |{H}\right \rangle }\}$. When she assigns it to the set $\{{\left |{H}\right \rangle }, {\left |{+}\right \rangle }\}$ and Bob’s measurement outcome is ${\left |{-}\right \rangle }$ (${\left |{V}\right \rangle }$), Bob obtains a conclusive result with bit value $0$ $(1)$.

The decoy-state method [31,32] with three intensities is exploited to deal with photon-number-splitting attack for coherent state source. Data from the decoy state and vacuum state will be used for parameter estimation, and only data from the signal state will be used as test bits and secret keys. The setup for our QDS protocol is presented in Fig. 1. In the following part of the paper, we use superscripts $c$, $u$, $t$, $*$, overline (underline), to denote conclusive results, untest bits, test bits, expected value and the upper bound (lower bound) of expected value, respectively. We also use subscripts $P$ ($P\in \{A, B, C\}$), $11$ and $\lambda$ ($\lambda \in \{\mu , \nu , 0\}$) to denote Alice (Bob, Charlie), single-photon pair components and intensity respectively. Detailed descriptions of our protocol are given below.

 

Fig. 1. Schematic diagram of a setup for our QDS protocol. Alice randomly prepares one of the four Bennett-Brassard 1984 [4] (BB84) states with phase-randomized weak coherent-state source and sends them to Bob (Charlie). Bob (Charlie) performs polarization measurement in the $Z$ or $X$ basis. PM: polarization modulator; AM: amplitude modulator; PBS: polarization beam splitter; D1-D2: single photon detectors;

Download Full Size | PDF

1. Key generation. (1) Alice randomly selects a quantum state $\{{\left |{H}\right \rangle }, {\left |{V}\right \rangle }, {\left |{+}\right \rangle }, {\left |{-}\right \rangle }\}$ with the same possibility and an intensity $\{\mu , \nu , 0\}$ (signal, decoy and vacuum state) with possibilities $p_{\mu }$, $p_{\nu }$ and $p_0$ respectively. For each possible message $m$ ($m=0$ or $1$), Alice prepares two different quantum state sequences with length $N$, namely $A_{B,m}$, and $A_{C,m}$. Alice sends $A_{B,m}$ to Bob and $A_{C,m}$ to Charlie through insecure quantum channels.

(2) For each quantum state, Bob and Charlie randomly choose X or Z basis to perform polarization measurement. Bob announces all the click events in $A_{B,m}$ through authenticated classical channel. Alice and Bob discard all the data that has no click. They keep the left data of length $n$, denote as $S_{AB,m}$ (kept by Alice) and $S_{B, m}$ (kept by Bob). Alice and Charlie perform the same step. As a result, Alice has four data strings $S_{AB,0}$, $S_{AB,1}$, $S_{AC, 0}$ and $S_{AC, 1}$, Bob (Charlie) has two strings $S_{B, 0}$($S_{C, 0}$) and $S_{B, 1}$($S_{C, 1}$). Since Alice randomly and independently chooses quantum states, the quantum states that Bob and Charlie receive are uncorrelated.

(3) Alice announces the intensity information of all pulses. According to the intensity information, the three participants divide each of their data strings into three strings, namely $\mu$ string, $\nu$ string and $0$ string. For example, Bob divides $S_{B, m}$ into $S_{B, m}^{\mu }$, $S_{B, m}^{\nu }$ and $S_{B, m}^{0}$.

(4) For the data strings corresponding to each intensity $\lambda$ ($\lambda \in \{\mu , \nu , 0\}$), Alice takes $S_{AB,m}^{\lambda }$ as the reference and changes the order of elements in $S_{AC,m}^{\lambda }$. Denote the changing result as $S'^{\lambda }_{AC,m}$, Alice should make $S^{\lambda }_{AB,m}$ and $S'^{\lambda }_{AC,m}$ identical. Without loss of generality, she requests Charlie to change the order of elements in $S_{C,m}^{\lambda }$ into the same order. We call this the post-matching method. After post-matching, the data obtained by Bob and Charlie can be correlated. Detailed description of post-matching method is given in Fig. 2.

 

Fig. 2. Schematic diagram of the post-matching method. For simplicity, we temporarily omit the superscript $\lambda$. (a) Alice sends $A_{B,m}$ to Bob and sends $A_{C,m}$ to Charlie. Only part of quantum states can be detected due to channel loss and imperfect detection. We use ‘$\checkmark$’ (‘$\times$’) to denote the detector has click (no click). They discard the data that has no click and keep the remaining data. (b) Alice changes the order of $S_{AC,m}$ into $S'_{AC,m}$. Alice informs Charlie about the procedure of changing the order of data. For example, if $S_{AB, m}= \{s_{AB,m}^1, s_{AB,m}^2, s_{AB,m}^3, s_{AB,m}^4\}=\{{|H\rangle}, {|V\rangle}, {|+\rangle} {|-\rangle}\}, S_{AC, m}=\{s_{AC,m}^1, s_{AC,m}^2, s_{AC,m}^3, s_{AC,m}^4\} =\{{\left |{+}\right \rangle }, {\left |{H}\right \rangle }, {\left |{V}\right \rangle }, {\left |{-}\right \rangle }\}$, Alice should change the order of elements in $S_{AC,m}$ into $\{s_{AC, m}^{2}$, $s_{AC, m}^{3}$, $s_{AC, m}^{1}$, $s_{AC, m}^{4}\}$. She also asks Charlie to change the order of elements in $S_{C, m}$ into $\{s_{C, m}^{2}$, $s_{C, m}^{3}$, $s_{C, m}^{1}$, $s_{C, m}^{4} \}$. (c) Charlie changes the order of $S_{C,m}$ as instructed by Alice. Note that $S_{C,m}$ is the measurement result of $S_{AC,m}$. Since the order of elements in $S_{C,m}$ and $S_{AC,m}$ are changed with the same procedure, $S'_{C,m}$ is the measurement result of $S'_{AC,m}$. As a result, although Alice sends different quantum state sequences $A_{B,m}$ and $A_{C,m}$, after post-matching, it is equivalent to two identical sequences $S_{AB,m}$ and $S'_{AC,m}$ arrive at Bob and Charlie.

Download Full Size | PDF

(5) Using the rules for generating logical bits, Alice randomly assigns each element in $S_{AB, m}^{\lambda }$ a set. The three participants ‘translate’ their data strings into raw key strings denoted as $K_{A, m}^{\lambda }$, $K_{B, m}^{\lambda }$ and $K_{C, m}^{\lambda }$. Note that they do not announce which bits are conclusive results.

2. Estimation. (1) The signer Alice chooses the desired authenticator of the signature, and the other participant automatically becomes the verifier. Here we assume Bob is the authenticator. The three participants publicly announce all data of $\nu$ strings and $0$ strings and the value of $n_\lambda$ (the length of $\lambda$ string). They estimate bit error rate of single-photon pair components in $\mu$ strings using decoy state method. The verifier Charlie randomly selects a proportion of $t$ in the $\mu$ string as test bits and asks Alice to publicly announce the value of these bits. We denote test bit strings as $K_{A,m}^{t}$, $K_{B,m}^{t}$ and $K_{C,m}^{t}$. Let $E_B^{ct}$ ($E_C^{ct}$) be the mismatch rate of conclusive results between $K_{A,m}^{t}$ and $K_{B,m}^{t}$ ($K_{A,m}^{t}$ and $K_{C,m}^{t}$). Bob and Charlie calculate $E_B^{ct}$ and $E_C^{ct}$. Note that when $E_B^{ct}$ or $E_C^{ct}$ gets too high, the signing process of this round is highly possible to fail. In this case they abort the protocol. In addition, Bob and Charlie calculate the proportion of conclusive results in $K_{B,m}$ and $K_{C,m}$ , denoted as $P_B^{c}$ and $P_C^{c}$, respectively. If $P_B^{c}$ or $P_C^{c}$ shows a big deviation from the ideal value $\frac {1}{4}$, they will also abort the protocol. The three participants discard the test bits and keep the remaining untest bits in $\mu$ strings with length $n^{u}$. We denote these untest bit strings as $K_{A,m}^{u}$, $K_{B,m}^{u}$ and $K_{C,m}^{u}$. They will be used as secret keys to sign the message in the messaging stage.

(2) Bob and Charlie announce $\{E_B^{ct}$, $P_B^{c}\}$ and $\{E_C^{ct}$, $P_C^{c}\}$. The three participants publicly negotiate to determine the values of authentication security threshold $T_a$ and verification security threshold $T_v$.

3. Messaging. (1) To sign a one-bit message $m$, Alice sends the message and the corresponding secret key $\{m, K_{A,m}^{u}\}$ to the authenticator Bob. Bob calculates the mismatch rate of conclusive results between $K_{A,m}^{u}$ and $K_{B,m}^{u}$, which is denoted as $E_B^{cu}$. If $E_B^{cu}< T_a$, Bob accepts the message and forwards $\{m, K_{A,m}^{u}\}$ to Charlie, otherwise he rejects the message and announces to abort the protocol.

(2) After receiving $\{m, K_{A,m}^{u}\}$ forwarded by Bob, Charlie calculates the mismatch rate of conclusive results $E_C^{cu}$ between $K_{A,m}^{u}$ and $K_{C,m}^{u}$. Charlie accepts the message if $E_C^{cu}<T_v$. When both Bob and Charlie accept the message, Alice successfully signs the message.

3. Security analysis

In our protocol, Alice randomly chooses unrelated quantum states to send to Bob and Charlie. After post-matching, it is equivalent to Alice simultaneously sending the same quantum states to Bob and Charlie. To perform post-matching, Alice exposes information of order, but does not leak information of quantum states. In this case, eavesdroppers can not obtain more information of quantum states compared with the case where Alice actually sends two copies of quantum states. Thus the security analysis of our protocol can directly follow the lines in Ref. [16]. In the three-participant scenario, transferability and nonrepudiation are equivalent. Accordingly, there are three security criteria: robustness, security against forging and security against repudiation. For simplicity, we just briefly present our results. For more detail, refer to Ref. [16].

1. Robustness. The robustness means the probability of an honest abort $\epsilon _{rob}$. In messaging stage, Bob rejects the message sent by Alice when $E_B^{cu}>T_a$. In the case of finite sample size, the robustness can be quantified by exploiting random sampling without replacement theorem [33].

2. Security against forging. In a forgery attack, Bob sends the message he wishes to forge and its corresponding secret key $\{m, K_{BF,m}\}$ to Charlie. The forgery attack is successful if Charlie accepts Bob’s forged message. An honest Bob knows only about $\frac {1}{4}$ of conclusive results in $K_{A,m}^{u}$. If Bob is an adversary, his optimal strategy is to acquire information of quantum states Charlie receives as much as possible, which is equivalent to the eavesdropping attack of Eve in four-state Scarani-Acin-Ribordy-Gisin 2004 (SARG04) QKD with two-photon source [30,34,35].

We assume only single-photon pairs that Alice sends to Bob and Charlie are secure. In this case, Bob and Charlie both receive a single-photon. Using Chernoff bound [36], the probability of a successful forgery attack $\varepsilon _{for}$ can be given by

To obtain the value of $E_{BF11}^{*}$, one should exploit decoy state method to estimate $s_{C11}^{c\mu }$ and $t_{C11}^{c\mu }$, where $t_{C11}^{c\mu }$ is the number of events that Bob and Charlie both receive a single-photon in $\mu$ string, Charlie has a conclusive result, and his classical bit is mismatching with Alice’s. We use $n_{P\lambda }$ to denote the number of detection events of the participant $P$ of intensity $\lambda$ and $m_{P\alpha }$ to denote the number of mismatching bits. The expected value of parameter $x$ can be acquired by the variant of Chernoff bound [33]: $\overline {x}^{*}=x+\beta +\sqrt {2\beta x +\beta ^{2}}$ and $\underline {x}^{*}=x-\frac {\beta }{2}-\sqrt {2\beta x +\frac {\beta ^{2}}{4} }$ with $\beta =\ln \frac {1}{\varepsilon _1}$, where $\epsilon _1$ is the failure probability of the Chernoff bound.

Separately consider the process that Alice sends pulses to Bob and to Charlie, we have

Bring in Eqs. (2) and (3), we have

We also have

Bring in Eqs. (6) and (7), we have

The overall secrecy is:

4. Performance

In order to show the performance of our protocol, we simulate a fiber-based QDS system. Define signature rate $R:=\frac {1}{2N}$, where $2N$ is the minimum number of pulses required to securely sign a one-bit message. Figure 3 shows the signature rate $R$ as a function of transmission distance. We consider the case where channels between Alice-Bob and Alice-Charlie are symmetric.

 

Fig. 3. Simulation of our QDS protocol. Numerically optimized signature rates are presented in logarithmic scale. The detection efficiency is $52\%$, the dark counting rate is $1.3 \times 10^{-7}$, the basis misalignment rate is $0.15\%$, the insert loss is $1.2$ dB, and the loss coefficient of fiber is $0.194$ dB/km.

Download Full Size | PDF

The security bounds are set to $\varepsilon _{for} \le 10^{-10}$, $\varepsilon _{rob}\le 10^{-10}$, $\varepsilon _{rep}\le 10^{-10}$ and $\varepsilon _1=\varepsilon _2\le (10^{-9}-3\times 10^{-10})/12$. We numerically optimize the minimum number of pulses required to securely sign a one-bit message with the free parameters $\{\mu , \nu , p_{\mu }, p_{\nu }, t\}$ by global search algorithm. For a fair comparison, we simulate the performance of the original protocol in Ref. [16] with the same experimental parameters. As shown in Fig. 3, the solid red line represents the signature rate of this work and the blue dashed line represents the original QDS protocol. Obviously, our protocol requires far less number of pulses to sign a one-bit message. Specifically, at $50$ km and $100$ km, our protocol requires $3.3 \times 10^{8}$ and $3.4 \times 10^{9}$ pulses to sign a one-bit message, but the protocol in Ref. [16] requires $3.8 \times 10^{10}$ and $3.7 \times 10^{12}$ pulses. The signature rate of our protocol is 2 or even 3 orders of magnitude higher than the original protocol at long distance.

We also simulate the performance of orthogonal encoding based protocol [17] with the cost of symmetrization taken into consideration. Assume Bob and Charlie utilize three-intensity decoy-state BB84 QKD protocol to perform symmetrization. Define the effective signature rate $R_{\textrm{eff}}:=\min \{\frac {1}{2N}, \frac {R_{QKD}}{6L}\}$, where $L$ is the length of key generated by key generation protocol in [17] and $R_{QKD}$ is the secret key rate of QKD. Note that $\frac {6L}{R_{QKD}}$ is the number of pulses required for QKD to perform symmetrization [21]. $R_{QKD}$ is simulated by the key rate formula in [37], where we choose error-correction efficiency $f=1.22$, data post-processing block size $N=10^{10}$, secrecy $\varepsilon _{sec}=10^{-10}$ and the same experimental parameters as Fig. 3.

Denote the angle between Alice-Bob and Alice-Charlie as $\theta$, the distance between Alice and Bob (Charlie) as $D_{AB}$ ($D_{AC}$), and the distance between Bob and Charlie as $D_{BC}$. In symmetric case, $D_{AB}=D_{AC}$, and $D_{BC}=2 \sin (\frac {\theta }{2}) D_{AB}$. At short distance where $R_{QKD}$ is very high, $R_{\textrm{eff}}$ is mainly determined by $\frac {1}{2N}$. When $\theta$ is close to $\pi$, the transmission distance of QKD ($D_{BC}$) increases much faster than $D_{AB}$. In this case, $R_{\textrm{eff}}$ is determined by $\frac {R_{QKD}}{6L}$ at long distance. We simulate the case of $\theta =\frac {2}{3} \pi$ and $\theta =\pi$. As shown in Fig. 4, the signature rate of [17] is higher than that of our protocol at short distance, but when distance between the two receivers is large, the signature rate will be severely limited by the low secret key rate of QKD in the symmetrization step. By contrast, our protocol decays much slower and has a significantly longer transmission distance.

 

Fig. 4. Comparison of our QDS protocol and orthogonal encoding based protocol [17]. The security bounds and experiment parameters are the same as Fig. 3.

Download Full Size | PDF

In addition, the typical experimental parameters and corresponding signature rate of some recent QDS experiments are listed in Table 1. This work shows a comparable performance with orthogonal encoding based protocol [25] even though the latter does not execute the symmetrization step. We remark that the symmetrization step is essential to the complete protocol, as demonstrated in experiments [21,22].

Table 1. Comparison of Parameters of Recent QDS Experiments

View Table

5. Conclusion

In this paper, we have proposed a non-orthogonal encoding based efficient quantum digital signature protocol. A novel method called post-matching is applied, which can increase the signature rate from decaying with $\eta ^{2}$ to $\eta$. Our protocol has a high signature rate and does not require the symmetrization operation thereby overcomes the major obstacles of existing QDS protocols. This protocol can be directly implemented with current commercially available QKD devices. Therefore, it should be the preferred solution to the application of QDS. This work is a great step for the development of quantum network with QDS. Moreover, we believe the key idea of post-matching method has the potential to be applied in various cryptographic tasks that require to establish multiparty correlations, such as multiparty quantum communication [38].