Fast Privacy Amplificationon GPUs

Nico Bosshard, Roland Christen, Esther Hänggi, Jörg Hofstetter

Published Feb 5, 2021• 1 citation

Abstract

Quantum key distribution protocols typically proceed in several phases: in a first phase, the honest parties exchange signals over the quantum channel. Then, there is a classical post-processing phase, where the honest parties communicate over the classical authentic channel to discard superfluous signals (sifting), estimate the error in the communication channel and the amount of eavesdropping (parameter estimation), correct the errors in their raw key (information reconciliation) and finally create a shorter but highly secure key (privacy amplification). This post-processing phase is often the limiting factor for the secure key rate of quantum key distribution implementations. Significant research effort is therefore made to find better algorithms and create better implementations. Here we propose a fast implementation of privacy amplification. The currently known algorithm with the best asymptotic time-complexity is modified Toeplitz hashing, running at O(n log n) using Fast-Fourier-Transform for fast matrix multiplication. We implement this algorithm on common GPUs using a very efficient and highly parallel CUDA algorithm. For large block sizes of approximately 10^8 bits - needed to limit the finite key effects - we achieve an input throughput of 3.7 Gbit/s with a dynamic Toeplitz seed and 5.7 Gbit/s using a fixed seed. This is several times faster than previously known implementations and can increase the total key-rate of practical quantum key distribution systems significantly.

DOI: 10.5281/zenodo.4551774

Related papers

High-speed Implementation of FFT-based Privacy Amplification on FPGA in Quantum Key Distribution

Qiong Li, Bingze Yan, Haokun Mao +1 more

Privacy amplification (PA) is a vital procedure in quantum key distribution (QKD) to generate the secret key that the eavesdropper has only negligible information from the identical correcting key for the communicating parties. With the increase of repeat frequency of discrete-variable QKD (DV-QKD) system, the processing speed of PA has become the bottle neck restricting DV-QKD's secure key rate. The PA using Toeplitz-based Hash function is adopted widely because of its simplicity and parallel feature. Because this algorithm can be accelerated with Fast Fourier Transform (FFT), an improved scheme PA for Field-programmable Gate Array (FPGA) based on this is proposed. This paper improves the custom FFT-based algorithm by reducing the number of computations and read/write memory operations significantly. The correctness is verified when implemented in a Xilinx Virtex-6 FPGA. Meanwhile, the processing speed of improved scheme can nearly double the classical Toeplitz Hashing scheme on FPGA through the actual experiment.

arXiv:1809.07592Sep 20, 20182 citations

High-speed and Large-scale Privacy Amplification Scheme for Quantum Key Distribution

Bang-Ying Tang, Bo Liu, Yongping Zhai +2 more

State-of-art quantum key distribution (QKD) systems are performed with several GHz pulse rates, meanwhile privacy amplification (PA) with large scale inputs has to be performed to generate the final secure keys with quantified security. In this paper, we propose a fast Fourier transform (FFT) enhanced high-speed and large-scale (HiLS) PA scheme on commercial CPU platform without increasing dedicated computational devices. The long input weak secure key is divided into many blocks and the random seed for constructing Toeplitz matrix is shuffled to multiple sub-sequences respectively, then PA procedures are parallel implemented for all sub-key blocks with correlated sub-sequences, afterwards, the outcomes are merged as the final secure key. When the input scale is 128 Mb, our proposed HiLS PA scheme reaches 71.16 Mbps, 54.08 Mbps and 39.15 Mbps with the compression ratio equals to 0.125, 0.25 and 0.375 respectively, resulting achievable secure key generation rates close to the asymptotic limit. HiLS PA scheme can be applied to 10 GHz QKD systems with even larger input scales and the evaluated throughput is around 32.49 Mbps with the compression ratio equals to 0.125 and the input scale of 1 Gb, which is ten times larger than the previous works for QKD systems. Furthermore, with the limited computational resources, the achieved throughput of HiLS PA scheme is 0.44 Mbps with the compression ratio equals to 0.125, when the input scale equals up to 128 Gb. In theory, the PA of the randomness extraction in quantum random number generation (QRNG) is same as the PA procedure in QKD, and our work can also be efficiently performed in high-speed QRNG.

Scientific ReportsOct 31, 201949 citations

An efficient large-scale privacy amplification scheme exceeding 10G bits for quantum key distribution

Xi Cheng, Haokun Mao, Hongwei Xu +1 more

Abstract Privacy Amplification (PA) is indispensable in Quantum Key Distribution (QKD), ensuring security against eavesdropping by eliminating information leakage. For Discrete-Variable QKD (DV-QKD) protocols, a large input block size exceeding 108 bits is preferred to achieve the secure key rate approaching the asymptotic limit. However, in state-of-the-art quantum key distribution systems operating at multi-GHz pulse rates, PA becomes a critical bottleneck due to the conflicting requirements of large input block sizes and high throughput. To address this challenge, we propose a novel PA algorithm utilizing a newly constructed universal hash family DM3H and prove its cryptographic security rigorously. Based on the PA algorithm, we design and implement an efficient PA scheme which is capable of processing input block sizes up to 10 10 bits while achieving high throughput performance. For an input block size of 1010 bits, the implementation on the i9-14900 platform demonstrates a throughput of 112 Mbps with a retention ratio of 0.33. This breakthrough significantly enhances the secure key rate and maximum transmission distance of DV-QKD systems.

EPJ Quantum TechnologyDec 1, 20251 citation

Fast implementation of length-adaptive privacy amplification in quantum key distribution

Chunmei Zhang, Mo Li, Jingzheng Huang +8 more

Post-processing is indispensable in quantum key distribution (QKD), which is aimed at sharing secret keys between two distant parties. It mainly consists of key reconciliation and privacy amplification, which is used for sharing the same keys and for distilling unconditional secret keys. In this paper, we focus on speeding up the privacy amplification process by choosing a simple multiplicative universal class of hash functions. By constructing an optimal multiplication algorithm based on four basic multiplication algorithms, we give a fast software implementation of length-adaptive privacy amplification. "Length-adaptive" indicates that the implementation of privacy amplification automatically adapts to different lengths of input blocks. When the lengths of the input blocks are 1 Mbit and 10 Mbit, the speed of privacy amplification can be as fast as 14.86 Mbps and 10.88 Mbps, respectively. Thus, it is practical for GHz or even higher repetition frequency QKD systems.

Chinese Physics BSep 1, 201426 citations

An efficient hybrid hash based privacy amplification algorithm for quantum key distribution

Bingze, Yan, Qiong Li, Haokun, Mao +1 more

Privacy amplification (PA) is an essential part in a quantum key distribution (QKD) system, distilling a highly secure key from a partially secure string by public negotiation between two parties. The optimization objectives of privacy amplification for QKD are large block size, high throughput and low cost. For the global optimization of these objectives, a novel privacy amplification algorithm is proposed in this paper by combining multilinear-modular-hashing and modular arithmetic hashing. This paper proves the security of this hybrid hashing PA algorithm within the framework of both information theory and composition security theory. A scheme based on this algorithm is implemented and evaluated on a CPU platform. The results on a typical CV-QKD system indicate that the throughput of this scheme (261Mbps@2.6*10^8 input block size) is twice higher than the best existing scheme (140Mbps@1*10^8 input block size). Moreover, This scheme is implemented on a mobile CPU platform instead of a desktop CPU or a server CPU, which means that this algorithm has a better performance with a much lower cost and power consumption.

arXiv:2105.13678May 28, 20212 citations

High-Speed and Adaptive FPGA-Based Privacy Amplification in Quantum Key Distribution

Qiong Li, Bingze Yan, Haokun Mao +3 more

Privacy amplification (PA) is a vital procedure in quantum key distribution (QKD) to shrink the eavesdropper's information about the final key almost to zero. With the increase of repeat frequency of discrete variable QKD (DV-QKD) system, PA processing speed has become the bottleneck in many high-speed DV-QKD systems. In this paper, a high-speed adaptive field-programmable gate array (FPGA)-based PA scheme using a fast Fourier transform (FFT) is presented. To decrease the computation complexity, a modified 2-D FFT-based Toeplitz PA scheme is designed. To increase the processing speed of the scheme on the constraint of limited resources, a real-value oriented FFT acceleration method and a fast read/write balanced matrix transposition method are designed and implemented in our scheme. The experimental results on a Xilinx Virtex-6 FPGA demonstrate that the throughput is nearly double of the latest FPGA based Toeplitz PA scheme according to the literature. Besides, this scheme owns not only the good adaptivity to compression ratio but also the compression ratio independent resource consumption. Therefore, this scheme can fit many high-speed QKD applications.

IEEE AccessJan 1, 201930 citations