2.1

Encoding

Polar code is an error-correcting code (ECC) introduced by E. Arikan in 2009 [6]. It is shown that polar code achieves encoding and decoding with low complexity of O(N log N) for a code length of N = 2ⁿ, where n is a natural number. The encoding exploits a property called channel polarization, which is outlined below.

We consider that we input a sequence with a length of N = 2ⁿ bits into a stationary memoryless binary symmetric channel (BSC) W. Let I(W) denote the mutual information of the BSC. The input sequence is subject to the following matrix operations:

where I_N is the identity matrix of order N, ⨂ denotes the Kronecker product, and R_N is a reverse shuffle matrix that rearranges the input bit sequence with even numbers in the first half and odd numbers in the second half. The matrix F is defined by

By applying the inverse operation of G_N onto the output sequence results, a I(W) fraction of the sequence is retrieved correctly, whereas a 1 – I(W) fraction will results in an error with a probability 1/2 in the limit of N → ∞. This phenomenon, known as channel polarization, allows polar codes to achieve error correction performance close to the Shannon limit.

A sender allocates the transmission data into the I(W) fraction of the sequence (message bits). She fills the 1 – I(W) fraction of the sequence (frozen bits) with random bits, and announces their values and locations to the receiver in advance.

The code rate, the ratio of the message bits to the total bits, becomes I(W), which is the channel capacity of BSC.

2.2

Decoding

The decoding method for polar codes is called successive cancellation decoding (SCD). In SCD, recursive estimation of codewords based on the log-likelihood ratio (LLR) is performed in the ascending order of every bit. When the vertical index is φ, and the horizontal index is Λ, the LLR at each point is and the estimated bit is . Here, φ and Λ satisfy the following conditions:

The first step of decoding is to convert the received value of each bit r_φ into the LLR λ_φ. For a BSC with crossover probability P_e, λ_φ is given as

Then, the LLR at each point can be computed as follows

where α, β, and и are defined by

Finally, the estimated bit at each point is calculated by

where Ф denotes (φ mod 2^⋀+1) and 𝓕_φ returns 1 if the index φ is a frozen bit, and 0 otherwise. After LLR calculations, the estimated codeword is outputted.

For the decoding of polar codes, SCD was first proposed, and its improved version, successive cancellation list decoding (SCLD) [9], was also proposed. In addition, CRC-aided SCLD (CA-SCLD) [10], which is concatenated with cyclic redundancy check (CRC) codes, has been proposed as an improved version of SCLD, and it can outperform low-density parity-check (LDPC) codes.

3.1

The flow of the QKD protocol

We briefly review the flow of QKD based on the Bennett-Brassard 1984 protocol (BB84) [1], which was the first proposed QKD protocol. In BB84, random numbers are encoded into a single photon’s polarization state. A sender (Alice) generates a random bit sequence, selects one of two pairs of polarization directions, (0, π/2) or (π/4, 3π/4), and rotates the photon polarization to the corresponding direction. For example, to transmit bit 0, the photon polarization is rotated to 0 or π/4. Bob also randomly selects the basis from (0, π/2) or (π/4, 3π/4) when he receives a photon from Alice. If the Alice’s and Bob’s basis match, the bit is retrieved correctly, but if a different basis is selected, an error occurs with a probability of 50%. Such random selection of basis is necessary to ensure security against Eve. For example, Eve would tap a photon sent by Alice, obtain the random bit from it, and retransmit a copy of the photon to Bob. However, Eve needs to select Alice’s basis randomly, just as Bob does. Therefore, even if Alice and Bob’s bases are identical, this operation will induce errors in the bit values. After completing random number transmission, the sifted-keys are created by notifying the receiving time and matching Alice’s and Bob’s bases via an authenticated public channel. When this operation is performed, the bit positions that were in different bases between the sender and receiver are notified, and the bits are eliminated. If the protocol is implemented under ideal conditions, the sifted-keys are identical, but errors are caused by imperfections in the optical system, bit errors due to dark counting in photon detectors, and Eve’s attack. Therefore, by exchanging information over the authenticated public channel, the error is corrected and the leakage information is removed. This sequence of operations is called the key-distillation processing.

The key-distillation processing roughly consists of (A) QBER estimation, (B) information reconciliation, and (C) privacy amplification. First, in (A), the QBER is estimated using a test bit sequences composed by random sampling from the sifted-keys. If the error rate exceeds the specified value, the session is discarded because the information leakage to Eve is too large to be removed by this key-distillation process. Then, in (B), the sifted-keys of Alice and Bob are error-corrected. Alice and Bob calculate the parity bits for error correction from their sifted-keys and exchange them on the public channel. Finally, in (C), privacy amplification, the final key is obtained by compressing the sifted-key after information reconciliation by the amount of leakage information estimated from the QBER.

3.2

Information Reconciliation

In this paper, we apply polar codes to (B) information reconciliation step in the above key-distillation processing. Although there are several methods for calculating the parity bits disclosed in this step, we adopt Dodis’s method [11]. In this method, a codeword c_EC is randomly generated by an ECC encoder of C_EC, and the exclusive-OR (XOR) of the codeword and the sifted-key is transmitted to the other party via the public channel. This method has been implemented in various systems [12, 13] because of its simplicity. Also, the cost of authentication is low because the authenticated public channel is used only once. Figure 1 shows the flowchart of Dodis’s method. First, Bob determines an appropriate code rate R’ based on the QBER P_e’ and transmits R’ value to Alice. Next, Bob generates a random bit sequence of K(= [NR’]) bits, where [·] is the ceiling function and N is the length of the sifted-key. Then, these К bits are encoded into N bits codeword c_EC by an ECC with the code rate of R’, and XORed into Bob’s sifted-key k_b as k_b ⨁ c_EC. Alice obtains the bit sequence (k_B ⨁ c_EC) ⨁ k_A by XORing her sifted-key k_A with the received codeword, resulting in the error pattern k_A ⨁ k_B onto c_EC. This error can be removed by decoding the received sequence (k_A ⨁ k_в) ⨁ c_EC because of R’ encoding, and the random number generated at Bob can be correctly transmitted to Alice. This [NR’] bits are the reconciled key. Note that we consider the case where Bob transmits the parity bits, and this method is generally called reverse reconciliation. It can generate keys more efficiently than the case of direct reconciliation in which Alice transmits keys. Therefore, it is widely used in continuous-variable QKD [14, 15] and other similar protocols [12, 16] as well as BB84.

Figure 1.

Flow chart for information reconciliation.

4.1

Performance indicator

In this paper, we construct an efficient transmission scheme that makes the ratio of the length of the successfully information-reconciled bit sequence N_corr to the length of the sifted-key N_sift, N_corr/N_sift, as large as possible. At first, instead of encoding a random bit sequence of length N_sift with a single codeword, we consider dividing it into В blocks of length N_B and encoding them. The following equation holds:

Then, we define block error rate (BLER) as the ratio of unsuccessful decoding to В expressed by

where B_fail is the number of unsuccessfully decoded blocks. Because N_corr is the product of the information length K_B and the number of successfully transmitted blocks, it can be denoted by

Then, N_corrr/N_Sift can be transformed as follows.

where R is the code rate defined by K_B/N_B. In this paper, we specify R(1 – BLER) as the evaluation function called throughput. In numerical simulations, we assumed that the errors in the sifted-key are symmetric for the bit 0 or 1, that is, BSC. Furthermore, the QBER estimation is assumed to be perfect.

4.2

Performance of polar codes

We simulated the polar code transmission in information reconciliation described in Section 3, in which the simulation conditions are shown in Table 1. Figure 2 shows the results of the throughput performances when the code rate R_polar(= R in (12)) and the crossover probability P_e are changed. It can be seen that the throughput performances of high-rate polar codes are superior when P_e is small, and those of low-rate polar codes are superior in high P_e region. As shown in the figure, the crossover probability region with superior throughput differs depending on the code rate, and it is necessary to change the code rate according to P_e for more efficient transmission.

Figure 2.

Throughput performances of polar codes.

Table 1.

Simulation conditions of polar codes.

4.3

Optimization of information reconciliation applied polar codes

Based on the discussion in the previous section, we derive an equation relating the code rate R_polar and the crossover probability P_e to obtain the best throughput for polar codes. First, Figure 3 shows the throughput performances when R_polar is changed by gradually increasing the number of frozen bits with a fixed crossover probability. This figure shows that for each crossover probability, there is an optimal code rate that maximizes throughput. Figure 4 shows a graph rearranging these points, with the crossover probability on the horizontal axis and the code rate on the vertical axis. We derived the following approximation equation as the selection rule for the code rate R_polar from the curve in Figure 4.

Figure 3.

Throughput performances versus code rate R_polar.

Figure 4.

Proposing rule to select the optimal code rate of polar codes.

4.4

Application of LDPC codes in the conventional method

As a benchmark against polar codes, we calculated LDPC codes’ performance under the conditions shown in Table 2. Figure 5 shows the throughput performances of the LDPC codes versus P_e with the parameter of code rate R_LDPC(= R in(12)). Using the five LDPC codes shown in the figure, the selection rule for the code rate R_LDPC optimizing the throughput performances can be derived as

Table 2.

Simulation conditions of LDPC codes.

Figure 5.

Throughput performances of LDPC codes.

It can be seen that the throughput performances are superior for high-rates in the small crossover probability region and low-rates in the large crossover probability region, as well as in Figure 2.

4.5

Performance comparison of the proposed method to LDPC codes

Figure 6 compares the throughput performances of LDPC codes and polar codes based on the selection rules obtained above. It is shown that the throughput performances of polar codes are higher than those of LDPC codes in all areas. Therefore, the application of polar codes to satellite QKD is expected to improve information reconciliation efficiency. LDPC codes can also have finer coding ratios, but it is necessary to share the parity-check matrices for all code rates in advance. However, polar codes have the advantage that no matrix share is needed.

Figure 6.

The comparison of optimized throughput performances.