基于差分進(jìn)化的量子密鑰分發(fā)數(shù)據(jù)協(xié)調(diào)優(yōu)化

王曉凱，閻　金，郭大波，劉紹婷，張　津，蔡　妍

(1. 山西大學(xué) 物理電子工程學(xué)院，山西 太原 030006； 2. 中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山西 太原 030051)

?

基于差分進(jìn)化的量子密鑰分發(fā)數(shù)據(jù)協(xié)調(diào)優(yōu)化

王曉凱1，閻金1，郭大波1，劉紹婷1，張津2，蔡妍2

(1. 山西大學(xué) 物理電子工程學(xué)院，山西 太原 030006； 2. 中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山西 太原 030051)

摘要:針對(duì)量子密鑰分發(fā)中的數(shù)據(jù)協(xié)調(diào)技術(shù)，引入差分進(jìn)化算法優(yōu)化非規(guī)則低密度奇偶校驗(yàn)碼，并結(jié)合高斯近似得到在較大門(mén)限值下校驗(yàn)矩陣的度分布. 為了提高搜索效率，避免門(mén)限值在進(jìn)行差分變異時(shí)陷入局部最優(yōu)，引入模擬退火算法重新更新門(mén)限值. 通過(guò)將優(yōu)化后的校驗(yàn)矩陣應(yīng)用于多維密鑰分發(fā)的數(shù)據(jù)協(xié)調(diào)中，能夠有效降低收斂信噪比，并且提高數(shù)據(jù)協(xié)調(diào)效率. 計(jì)算機(jī)仿真結(jié)果表明： 分組碼長(zhǎng)為2×105，碼率為0.5時(shí)，在收斂信噪比SNR=1.15 dB下8維數(shù)據(jù)協(xié)調(diào)效率可達(dá)90.55%.

關(guān)鍵詞:量子密鑰分發(fā)； 差分進(jìn)化； 度分布； 模擬退火； 協(xié)調(diào)效率

隨著信息安全技術(shù)不斷發(fā)展，量子保密通信受到人們的普遍關(guān)注. 量子保密通信技術(shù)利用了傳輸系統(tǒng)中的量子不可克隆的特性，保證了通信雙方在密鑰分配過(guò)程中能夠?qū)崿F(xiàn)無(wú)條件的安全性. 目前，根據(jù)光源信號(hào)的特征,量子密鑰分發(fā)技術(shù)(Quantum Key Distribution)分為單光子變量和連續(xù)變量[1]. 由于單光子光源的制備較為困難，實(shí)際實(shí)驗(yàn)系統(tǒng)中采用弱脈沖代替單光子，該方法使得通信系統(tǒng)中引入了不安全因素，而且弱脈沖的轉(zhuǎn)化效率較低. 連續(xù)變量是利用相干態(tài)、 雙模糾纏態(tài)等高斯量子態(tài)作為信號(hào)的載波[2]，采用零拍探測(cè)技術(shù)對(duì)光場(chǎng)的相位和振幅進(jìn)行調(diào)制編碼從而進(jìn)行信息傳輸[3]，而且實(shí)際實(shí)驗(yàn)裝置能夠采用經(jīng)典光信息傳輸系統(tǒng)，因而具有較高的密鑰分發(fā)效率和傳輸距離，引起國(guó)內(nèi)外專(zhuān)家的重視.

在連續(xù)變量量子密鑰分發(fā)(Continuous-Variable-QKD)技術(shù)中，當(dāng)量子高斯態(tài)信息由發(fā)送端Alice傳到接收端Bob后，由于信道噪聲的干擾以及第3方的竊聽(tīng)行為，導(dǎo)致通信過(guò)程中傳遞的密鑰串存在不一致的序列，因而還需要后處理中數(shù)據(jù)協(xié)調(diào)技術(shù)糾正不一致的信息序列，才能完成最終的密鑰提取[4]. 目前數(shù)據(jù)協(xié)調(diào)方案主要采用Assche等人提出的分層糾錯(cuò)協(xié)議[5]，并結(jié)合Bloch等提出的利用低密度奇偶校驗(yàn)碼(LDPC)作為糾錯(cuò)碼型[6]. 實(shí)際數(shù)據(jù)協(xié)調(diào)過(guò)程中，通過(guò)校驗(yàn)矩陣對(duì)光源信息進(jìn)行壓縮編碼以及解碼，因此LDPC碼的性能是影響數(shù)據(jù)協(xié)調(diào)效率的重要因素.

通過(guò)設(shè)計(jì)優(yōu)化LDPC碼校驗(yàn)矩陣的度分布和譯碼門(mén)限值能夠使其性能接近香農(nóng)極限. Richardson等人提出一種基于無(wú)環(huán)圖情況下的密度進(jìn)化理論[7]，并采用密度進(jìn)化理論計(jì)算出基于消息傳遞譯碼(BP)下的最佳譯碼門(mén)限值. 由于在計(jì)算消息概率密度時(shí)復(fù)雜度較高，隨后Chung等人提出高斯近似分析方案[8]，將信息傳遞過(guò)程中的多維的消息密度計(jì)算簡(jiǎn)化為一維的均值計(jì)算，降低了計(jì)算復(fù)雜度. 差分近化(Differential Evolution)是一種基于群體差異的并行搜索技術(shù)[9]，該算法能夠克服碼參數(shù)優(yōu)化過(guò)程中的錯(cuò)誤收斂的現(xiàn)象，但是容易陷入局部最優(yōu)解，導(dǎo)致過(guò)早收斂現(xiàn)象的發(fā)生.

數(shù)據(jù)協(xié)調(diào)效率是制約CVQKD技術(shù)發(fā)展的瓶頸，本文通過(guò)高斯近似分析LDPC碼的門(mén)限值，同時(shí)為了解決差分進(jìn)化過(guò)早收斂問(wèn)題，推導(dǎo)出基于模擬退火的優(yōu)化算法. 在改進(jìn)的差分進(jìn)化算法的基礎(chǔ)上，對(duì)不同碼率下的LDPC碼校驗(yàn)矩陣度分布進(jìn)行優(yōu)化設(shè)計(jì). 在多維連續(xù)變量量子密鑰分發(fā)實(shí)驗(yàn)中，采用經(jīng)過(guò)優(yōu)化處理的校驗(yàn)矩陣，能夠降低數(shù)據(jù)協(xié)調(diào)的收斂信噪比，并提高數(shù)據(jù)協(xié)調(diào)效率，實(shí)現(xiàn)安全可靠的密鑰提取.

1數(shù)據(jù)協(xié)調(diào)技術(shù)

在量子密鑰分發(fā)的過(guò)程中，接收信息的Bob一方要從發(fā)送信息的Alice一方收到可靠信息序列. 實(shí)際的通信過(guò)程中，由于傳輸介質(zhì)的性質(zhì)、 信道的噪聲干擾，損失以及第3方的竊聽(tīng)，導(dǎo)致通信雙方獲得的信息序列仍存在一定的誤碼率. 數(shù)據(jù)協(xié)調(diào)技術(shù)通過(guò)接受方Bob在對(duì)發(fā)送端Alice的原始數(shù)據(jù)進(jìn)行量子測(cè)量后得到經(jīng)典信息，并利用公共的經(jīng)典信道對(duì)接受的信息進(jìn)行協(xié)調(diào)、 糾錯(cuò).

圖1　基于BB84協(xié)議的數(shù)據(jù)協(xié)調(diào)模型圖Fig.1　The model of data reconciliation based on BB84 protocol

通信雙方Alice和Bob基于BB84協(xié)議的規(guī)定進(jìn)行信息的交換[10]. 相關(guān)的數(shù)據(jù)協(xié)調(diào)采用LDPC碼為糾錯(cuò)碼型，并結(jié)合校驗(yàn)子(Syndrome)的壓縮編碼方案對(duì)數(shù)據(jù)進(jìn)行處理. 其數(shù)據(jù)協(xié)調(diào)模型如圖1 所示.

具體的協(xié)調(diào)步驟如下：

Step 1發(fā)送端Alice將原始的密鑰數(shù)據(jù)X經(jīng)過(guò)相干調(diào)制后，通過(guò)量子信道發(fā)送給接受端Bob.

Step 2接受端Bob經(jīng)過(guò)量化編碼方法將連續(xù)信息Y轉(zhuǎn)化成二進(jìn)制序列Y′，并通過(guò)信道編碼方法生成校驗(yàn)矩陣H, 根據(jù)H計(jì)算得到校驗(yàn)子S=Y′HT. 此時(shí)Bob將校驗(yàn)子S通過(guò)經(jīng)典信道返回給Alice端.

Step3Alice端將原有的邊信息結(jié)合上一步得到的校驗(yàn)子S，采用對(duì)數(shù)似然比LLR-BP算法進(jìn)行迭代譯碼，最終恢復(fù)Bob端的二進(jìn)制序列Y′.

2基于高斯近似優(yōu)化門(mén)限值

2.1高斯近似

(1)

校驗(yàn)節(jié)點(diǎn)信息更新表示為

(2)

(3)

(4)

式中：mu0為初始變量消息的均值. 在第l次消息迭代校驗(yàn)節(jié)點(diǎn)消息均值表示為

(5)

式中：φ(x) 函數(shù)定義為

(6)

圖2　非規(guī)則LDPC碼高斯近似流程圖Fig.2　The flow chart of Irregular LDPC codes Gaussian approximation

(7)

(8)

根據(jù)式(3)，在第l次消息迭代時(shí)，度數(shù)為i的變量節(jié)點(diǎn)的均值表示為

(9)

度數(shù)為j的校驗(yàn)點(diǎn)消息輸出均值可以表示為

(10)

由于校驗(yàn)節(jié)點(diǎn)所接受的消息密度為

(11)

代入式(10)可得校驗(yàn)節(jié)點(diǎn)的消息均值更新

(12)

將式(12)代入式(9)就能得到非規(guī)則LDPC碼在高斯近似下的概率消息迭代公式. 圖2 為非規(guī)則LDPC碼在AWGN信道下的高斯近似流程圖.

2.2門(mén)限值計(jì)算

1) 初始化參數(shù). 設(shè)定信道參數(shù)δ初始值，變化步長(zhǎng)Δδ，最大迭代次數(shù)lmax，并設(shè)定目標(biāo)錯(cuò)誤概率Pe以及非規(guī)則LDPC的度數(shù)分布.

3) 停止迭代. 當(dāng)達(dá)到最大迭代次數(shù)時(shí)停止迭代并輸出門(mén)限值δ*=δ-Δδ.

3基于差分進(jìn)化的碼參數(shù)優(yōu)化算法

非規(guī)則LDPC碼在給定碼率下，不同碼的度分布在設(shè)定目標(biāo)錯(cuò)誤概率和迭代次數(shù)的情況下，所計(jì)算得到的信道門(mén)限值都不同. 因此需要對(duì)碼的度分布進(jìn)行設(shè)計(jì)，使所求得信道門(mén)限值達(dá)到最大，此時(shí)得到的碼型為最優(yōu)碼型. 而差分進(jìn)化算法能夠通過(guò)隨機(jī)初始化一個(gè)樣本序列，并借助進(jìn)化算子對(duì)最優(yōu)度數(shù)分布進(jìn)行搜索[14]. 傳統(tǒng)的差分進(jìn)化算法通過(guò)群體樣本的差分矢量來(lái)修正個(gè)體值，然而在后期收斂時(shí)容易陷入局部最優(yōu)，使得算法過(guò)早收斂. 本文在傳統(tǒng)差分進(jìn)化算法中加入模擬退火算法，使得優(yōu)化后算法能夠跳出局部最優(yōu). 設(shè)序列L表示度分布中自由參數(shù)，因此最大門(mén)限的度分布優(yōu)化轉(zhuǎn)化為優(yōu)化的一個(gè)L維向量p=(λi,…,λdv,ρj,…,ρdc). 具體算法步驟描述如下：

1) 初始化

2) 差分進(jìn)化

經(jīng)過(guò)G+1迭代后，在樣本序列[0,NP-1]中隨機(jī)選取4個(gè)樣本值r1,r2,r3,r4, 組成新的向量

(13)

3) 模擬退火

Step1： 設(shè)定初始溫度T0，迭代次數(shù)以及退火速率α(0<α<1)，將上述得到的最佳門(mén)限pbest,G+1設(shè)為初始值.

(14)

式中： f(x)為適應(yīng)函數(shù)； ηGuass服從N(0,δ′)的高斯分布.

4) 停止準(zhǔn)則

當(dāng)計(jì)算得到的門(mén)限值滿足δ*>δ，則輸出度數(shù)分布矢量p=(λi,…,λdv,ρj,…,ρdc)，則返回第2步繼續(xù)迭代搜索. 經(jīng)過(guò)上述的有限次的迭代，門(mén)限值的解空間差異性縮小. 對(duì)于每次搜索到接近最優(yōu)門(mén)限值時(shí)，繼續(xù)迭代計(jì)算得到門(mén)限值變化不大，因此通過(guò)門(mén)限值比較可以及時(shí)跳出循環(huán)，減小計(jì)算量.

經(jīng)過(guò)上述計(jì)算篩選出的值為高斯信道下的最佳門(mén)限值的度分布(λ,ρ). 在模擬退火更新最佳門(mén)限值時(shí)，需要保證在其領(lǐng)域中產(chǎn)生新值，因此需要引入高斯變異的波動(dòng)方差值δ′來(lái)控制，從而避免新產(chǎn)生的門(mén)限值過(guò)度偏離原值. 根據(jù)相應(yīng)的約束條件，本文取δ′=0.2.

4數(shù)值仿真結(jié)果及分析

4.1校驗(yàn)矩陣度分布優(yōu)化

選擇碼率分別為0.5，0.6和0.7在最大變量節(jié)點(diǎn)度數(shù)dv分別為4, 6, 8, 10, 20時(shí)采用改進(jìn)的差分進(jìn)化方法所得到的度分布值，并利用高斯近似計(jì)算其門(mén)限值. 在AWGN信道下,最大迭代次數(shù)為100，通過(guò)比較門(mén)限值的大小得出度數(shù)分布及相應(yīng)門(mén)限值如表1～表3.

表1　碼率為0.5的碼參數(shù)

表2　碼率為0.6的碼參數(shù)

表3　碼率為0.7的碼參數(shù)

4.2量子密鑰分發(fā)數(shù)據(jù)協(xié)調(diào)優(yōu)化

本文采用連續(xù)變量量子密鑰多維數(shù)據(jù)數(shù)據(jù)協(xié)調(diào)算法[15]，通過(guò)差分進(jìn)化的優(yōu)化方法，結(jié)合高斯近似門(mén)限值的分析，對(duì)LDPC碼的校驗(yàn)矩陣H的度數(shù)分布進(jìn)一步優(yōu)化. 本文采用的仿真硬件實(shí)驗(yàn)平臺(tái)基于CPU為InterXeonE5620 2.4GHz和32G內(nèi)存的雙核服務(wù)器，LDPC碼度分布分別采用表1～表3 中的第5組實(shí)驗(yàn)數(shù)據(jù). 碼長(zhǎng)選用2×105，最大迭代次數(shù)為100，共100個(gè)分組進(jìn)行統(tǒng)計(jì)實(shí)驗(yàn).

為了便于比較，選用文獻(xiàn)[13]中對(duì)應(yīng)碼率下的相應(yīng)數(shù)據(jù). 表4 給出了與文獻(xiàn)[13]數(shù)據(jù)協(xié)調(diào)方案一致情況下，LDPC碼的性能與協(xié)調(diào)效率的比較. 數(shù)據(jù)協(xié)調(diào)效率定義的公式[16]為

(15)

表4　數(shù)據(jù)協(xié)調(diào)方案的實(shí)驗(yàn)結(jié)果比較

在碼率為0.5的情況下，本文所采用的方案在4維、 8維數(shù)據(jù)協(xié)調(diào)時(shí)的收斂信噪比RSN為1.32和1.15，比文獻(xiàn)[13]中相同實(shí)驗(yàn)條件下的收斂信噪比降低了12.0%和4.1%，而且協(xié)調(diào)效率分別提高了8.9% 和3.0%. 在碼率為0.6的情況下，本文實(shí)驗(yàn)采用的方案中收斂信噪比比文獻(xiàn)中降低了11.8%和7.6%，而協(xié)調(diào)效率分別提高了7.9%和5.2%. 當(dāng)碼率增加到0.7的時(shí)，本文采用的實(shí)驗(yàn)方案比文獻(xiàn)中實(shí)驗(yàn)的收斂信噪比SSN分別降低了1.9%和1.7%，而協(xié)調(diào)效率分別增加了1.1%和1.0%. 隨著碼率的增加，3種方案下的收斂信噪比以及協(xié)調(diào)效率的差距逐漸縮小，根據(jù)置信息傳遞規(guī)律碼率越高校驗(yàn)節(jié)點(diǎn)數(shù)越少，而此時(shí)校驗(yàn)矩陣可優(yōu)化的空間也就越小. 較低的收斂信噪比，能夠保證密鑰在一定誤碼率的情況下安全傳輸，因此優(yōu)化后的協(xié)調(diào)方案抵御噪聲能力增強(qiáng)，延長(zhǎng)了光纖通信的距離.

5結(jié)論

本文針對(duì)量子密鑰分發(fā)中的數(shù)據(jù)協(xié)調(diào)，提出一種改進(jìn)的差分進(jìn)化算法,用于優(yōu)化校驗(yàn)矩陣并結(jié)合高斯近似得到了較大門(mén)限值下的度數(shù)分布. 通過(guò)實(shí)驗(yàn)仿真表明，優(yōu)化后的校驗(yàn)矩陣H在4維數(shù)據(jù)協(xié)調(diào)和8維數(shù)據(jù)協(xié)調(diào)中能夠有效降低收斂信噪比，提高協(xié)調(diào)效率，而且在8維數(shù)據(jù)協(xié)調(diào)中，本文采用實(shí)驗(yàn)方案信噪比能夠降至1.15dB，最大協(xié)調(diào)效率可達(dá)90.55%，對(duì)實(shí)際量子密鑰分發(fā)實(shí)驗(yàn)具有指導(dǎo)意義.

進(jìn)一步的研究工作是如何保證低信噪比下的數(shù)據(jù)吞吐量，以及設(shè)計(jì)校驗(yàn)矩陣結(jié)構(gòu)更為復(fù)雜的多邊類(lèi)型LDPC碼的數(shù)據(jù)協(xié)調(diào)技術(shù).

參考文獻(xiàn)：

[1]王懷勝，楊杰. 連續(xù)變量量子保密通信技術(shù)[J]. 信息安全與通信保密，2015(7)： 86-91.

Wang Huaisheng，Yang Jie. Continuous variable quantum private communication technology[J]. Information Security and Communications Privacy，2015. (7)： 86-91. (in Chinese)

[2]陳進(jìn)建，韓正甫，趙義博，等. 平衡零拍測(cè)量對(duì)連續(xù)變量量子密鑰分配的影響[J]. 物理學(xué)報(bào)，2007，56 (1)： 5-9.

Chen Jinjian，Han Zhengfu，Zhao Yibo, et al. The effect of balanced homodyne detection on continuous variable quantum key distribution[J]. Acta Physica Sinica，2007，56 (1)： 5-9. (in Chinese)

[3]Bennett C H，Brassard G. Quantum cryptography： Public key distribution and coin tossing[J]. Theoretical Computer Science，2014，560： 7-11.

[4]孫藝，王曉凱，郭大波，等. 基于粒子群的數(shù)據(jù)協(xié)調(diào)優(yōu)化算法[J]. 測(cè)試技術(shù)學(xué)報(bào)，2015，29 (2)： 149-157.

Sun Yi，Wang Xiaokai，Guo Dabo ，et al. The optimized algorithm for data reconciliation based on particle swarm optimzation.[J]. Journal of Test and Measurement Technology，2015，29 (2)： 149-157. (in Chinese)

[5]Van G A，Cardinal J ，Cerf N J. Reconciliation of a quantum-distributed Gaussian key[J]. Information Theory，IEEE Transactions on，2004，50 (2)： 394-400.

[6]Bloch M，Thangaraj A，McLaughlin W S，et.al. LDPC-based secret key agreement over the gaussian wiretap channel[C] .Information Theory，2006 IEEE International Symposium on. IEEE，2006: 1179-1183.

[7]Richardson T J，Urbanke R L. The capacity of low-density parity-check codes under message-passing decoding[J]. Information Theory，IEEE Transactions on，2001，47 (2)： 599-618.

[8]Chung S Y，Richardson T J，Urbanke R L. Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation[J]. Information Theory，IEEE Transactions on，2001，47 (2)： 657-670.

[9]楊啟文，蔡亮，薛云燦. 差分進(jìn)化算法綜述[J]. 模式識(shí)別與人工智能，2008，21 (4)： 506-513.

Yang Qiwen，Cai Liang，Xue Yuncan. A survey of differential evolution algorithms[J]. Pattern Recognition and Artificial Intelligence，2008，21 (4)： 506-513. (in Chinese)

[10]Shor P W，Preskill J. Simple proof of security of the BB84 quantum key distribution protocol[J]. Physical review letters，2000，85 (2)： 441-449.

[11]Chen Jinghu，F(xiàn)ossorier M P. Density evolution for two improved BP-based decoding algorithms of LDPC codes[J]. Communications Letters，IEEE，2002，6 (5)： 208-210.

[12]Lehmann F，Maggio G M. Analysis of the iterative decoding of LDPC and product codes using the Gaussian approximation[J]. Information Theory，IEEE Transactions on，2003，49 (11)： 2993-3000.

[13]袁東風(fēng)，張海剛. LDPC碼理論與應(yīng)用[M]. 北京： 人民郵電出版社，2008.

[14]劉慶華，劉曉琳，陳紫強(qiáng). 基于差分進(jìn)化的非規(guī)則 LDPC 碼優(yōu)化設(shè)計(jì)[J]. 計(jì)算機(jī)工程，2012，38 (2)： 267-269.

Liu Qinghua，Liu Xiaolin，Chen Ziqiang. Optimal design of irregular LDPC code based on differential evolution[J]. Computer Engineering，2012，38 (2)： 267-269. (in Chinese)

[15]王云艷，郭大波，張彥煌，等. 連續(xù)變量量子密鑰分發(fā)多維數(shù)據(jù)協(xié)調(diào)算法[J]. 光學(xué)學(xué)報(bào)，2014(8)： 289-295.

Wang Yunyan，Guo Dabo，Zhang Yanhuang, et.al. Algorithm of multidimensional reconciliation for continuous-variable quantum key distribution[J].Acta Optica Sinica，2014(8)： 289-295. (in Chinese)

[16]Leverrier A，Grangier P. Continuous-variable quantum-key-distribution protocols with a non-Gaussian modulation[J]. Physical Review A，2011，83 (4)： 042312-042319.

The Optimized Algorithm of Data Reconciliation for Quantum Key Distribution Based on Differential Evolution

WANG Xiaokai1, YAN Jin1, GUO Dabo1, LIU Shaoting1, ZHANG Jin2, CAI Yan2

(1. College of Physics and Electronic Engineering, Shanxi University, Taiyuan 030006, China；2. School of Computer Science and Control Engineering, North University of China, Taiyuan 030051, China)

Abstract:In allusion to the data reconciliation technology of quantum key distribution, differential evolution algorithm is proposed to optimize the irregular low-density parity check code ，and under larger threshold with Gaussian approximation the degree distribution is calculated. In order to improve the search efficiency and avoid the threshold falling into local optimum with differential mutating, simulated annealing algorithm is proposed to optimize the threshold. The optimized parity check matrix applies to multidimensional reconciliation which reduces convergence of signal to noise ratio and improve reconciliation efficiency.Simulation results indicate that the eight-dimensional data reconciliation efficiency is up to 90.55% under the convergence SNR=1.15 dB which the length of code is 2×105 and code rate is 0.5 .

Key words:quantum key distribution; differential evolution; degree distribution; simulated annealing; reconciliation efficiency

中圖分類(lèi)號(hào):TN309

文獻(xiàn)標(biāo)識(shí)碼:A

doi:10.3969/j.issn.1671-7449.2016.02.009

作者簡(jiǎn)介：王曉凱(1963-)，男，教授，博士，主要從事通信網(wǎng)絡(luò)管理、 控制與優(yōu)化等研究.

基金項(xiàng)目：山西省國(guó)際科技合作計(jì)劃資助項(xiàng)目(2014081027-1)； 山西省基礎(chǔ)研究資助項(xiàng)目(2014011007-2)； 山西省回國(guó)留學(xué)人員科研資助項(xiàng)目(2014-012)

收稿日期:2015-09-12

文章編號(hào):1671-7449(2016)02-0142-07