基于LDPC硬判決算法的高效數據協(xié)調方法

屠亮亮，徐榮青

(南京郵電大學 科學與工程學院，江蘇 南京 210003)

?

基于LDPC硬判決算法的高效數據協(xié)調方法

屠亮亮，徐榮青

(南京郵電大學 科學與工程學院，江蘇 南京 210003)

摘要：數據協(xié)調是量子密鑰分發(fā)中必不可少的一個環(huán)節(jié)，其主要目的是糾正量子通信篩選后信息的錯誤圖案，使合法通信雙方獲得一致的密鑰信息。為了提高協(xié)調算法的糾錯效率，選擇了一種基于硬判決迭代譯碼算法的LDPC碼對QKD中的密鑰序列進行數據協(xié)調，相較于傳統(tǒng)的協(xié)調方法如級聯(lián)碼、卷積碼、Winnow方案，采用低復雜度的LDPC比特翻轉算法的正向協(xié)調方案具有較強的時效性，尤其是在0.4～0.6的碼率時協(xié)調效率達到最高。

關鍵詞：量子密鑰分發(fā)；數據協(xié)調；LDPC

引用格式：屠亮亮，徐榮青. 基于LDPC硬判決算法的高效數據協(xié)調方法[J].微型機與應用，2016,35(12)：67-69.

0引言

量子密鑰分發(fā)(QKD)[1]是近幾年來信息安全領域中發(fā)展極為迅速的一個課題，有別于采用數學算法保護密鑰安全的傳統(tǒng)密鑰體系，量子密鑰分發(fā)是通過量子力學的物理性質來達到理論上的密鑰絕對安全。

本文采用傳統(tǒng)稱謂，即定收發(fā)雙方分別為Alice和Bob。QKD是由合法通信雙方通過量子信道傳送量子態(tài)信號，并通過經典信道實現(xiàn)密鑰后處理，最終提取出二進制密鑰序列以實現(xiàn)密鑰通信的過程?？梢詫⒘孔用荑€分發(fā)流程歸納為4個步驟，分別是量子傳輸過程、信道參數估計、數據協(xié)調、密鑰放大。數據協(xié)調的作用是糾正雙方對應位置的不一致信息，使用的是經典公開信道，適用于所有經典信道的信息理論。

本文的重點聚焦在協(xié)議的數據協(xié)調部分，即假定在Alice和Bob端已經完成了4步流程的前兩步，各自建立了等長且具有一定相關性的密鑰，密鑰序列的數量和順序大致相同且具有一定的差錯率。在QKD中，可以把這個差錯率叫做量子誤碼率(QBER)，理論上只要該值不大于11%，就認為Alice和Bob的通信沒有被竊聽，即可以實現(xiàn)理論上的安全傳輸。

常見的量子密鑰分發(fā)技術可以分為離散變量量子密鑰分發(fā)(DVQKD)[2]和連續(xù)變量量子密鑰分發(fā)(CVQKD)兩種，其中前者在理論上可以實現(xiàn)更遠的傳輸距離，不過，DVQKD也存在著單光子信源難以制備、檢測設備裝置復雜的缺點。在單光子信源研究領域，超導材料作為光敏感器件的單光子探測技術的發(fā)現(xiàn),使得量子效率、暗計數率和計數率大幅度提高。另外，潘建偉等人首次在類石墨烯材料中發(fā)現(xiàn)一種非經典單光子發(fā)射器，為光量子器件發(fā)展開辟了一個新的重要領域。這些單光子制備工藝的發(fā)展，也在推動DVQKD進一步走向實際應用。

1數據協(xié)調方案

CVQKD系統(tǒng)一般都是將數據協(xié)調和密鑰放大結合在一起實現(xiàn)，事實上對于DVQKD系統(tǒng)，單獨考慮數據協(xié)調更有利于觀測不同協(xié)調方法的性能。本文拋開密鑰放大對糾錯過程的影響，側重于各自協(xié)調方案的研究。

由于數據協(xié)調過程使用的是經典信道，因此常見的經典信道編碼方法[3]都可以應用于數據協(xié)調過程。綜合以往文獻，數據協(xié)調的性能主要由協(xié)調效率和泄露信息百分比來衡量。目前廣泛使用的級聯(lián)碼協(xié)調方法難以避免合法通信雙方的交互延遲。而Winnow協(xié)調方法借助漢明碼糾錯技術對此有所改進，不過也是以犧牲糾錯率和泄露更多密鑰信息為代價。本文提出的LDPC[4]協(xié)調技術只需要Alice和Bob進行一次信息交互，并且可以通過校驗矩陣參數有效地控制泄露信息的數量。另一方面，LDPC作為最接近香農限的信道編碼技術，采用硬判決算法可以顯著地降低糾錯算法的時間復雜度，有效提高系統(tǒng)的時效性。

數據協(xié)調方案的選取應該滿足3個基本要求[5]：誤碼率應足夠低，盡量不舍棄初始信息，盡量保證時效性。假設Alice和Bob在經過了量子傳輸和信道參數估計之后分別獲得了初始密鑰序列X和Y，其中X、Y同為二進制信息序列，序列X為標準密鑰，序列Y與序列X的錯誤圖案為E，即Y=X+E；Bob則通過接收到的序列Y和理想的無差錯經典信道與X協(xié)商糾錯，并得到X的估計，如圖1所示。雙方的信息協(xié)商有可能會泄露原始密鑰的相關信息，因此在協(xié)商之后還應該按適當比例刪除序列X與Y的部分信息比特，保證系統(tǒng)的安全性。

圖1　公開經典信道下的數據協(xié)調

1.1Slepian-Wolf編碼定理

LDPC是一種高效的信道編碼技術，其本質是給碼字信息增加監(jiān)督位來提高信息傳輸的抗信道噪聲能力。數據協(xié)調過程可以看作是一對相關信源的信源壓縮編碼，即一個雙信源的分布式信源編碼過程(DSC)，該方法在滿足SW(Slepian-Wolf)定理所定義的熵條件下，將信道編碼技術運用于信源編碼，實現(xiàn)信源的無失真編碼。SW定理有兩個要求：一是需要將一個信源作為主信源，另一個信源作為邊信息，即完全邊信息問題；二是兩個信源應有一定的相關性。

1.2校驗位和校驗子檢測方法

傳統(tǒng)的LDPC編碼糾錯方法是在發(fā)送端借助LDPC生成矩陣G進行編碼，并在接收端使用對應的校驗矩陣H和迭代譯碼算法實現(xiàn)相應的譯碼，最終實現(xiàn)糾錯檢錯，使用這種方法的數據協(xié)調方法也叫校驗位糾錯方法。該方法的弊端是根據LDPC的監(jiān)督矩陣H獲得生成矩陣G的方法比較復雜，并且需要對全碼長序列進行信道譯碼，因此還需要更長的譯碼時間。

2003年，SARTIPI等人提出了一種結合LDPC碼的校驗子糾錯方法，之后，PRADHAN等人將校驗子糾錯方法運用到了分布式信源編碼，使用這種方法的優(yōu)點是：(1)有效地壓縮信源，減少協(xié)商泄露的信息長度；(2)直接使用LDPC的稀疏矩陣H進行糾錯，避免了計算LDPC的生成矩陣，極大地提高了系統(tǒng)的協(xié)調效率；(3)迭代譯碼的時間復雜度因為信源的壓縮而線性減少。

本文采用基于校驗子檢測的完全邊信息協(xié)商方法，簡要的信息流程框圖如圖2所示。

圖2　基于校驗子檢測的完全邊信息協(xié)調方法

1.3LDPC比特翻轉算法

現(xiàn)今LDPC的譯碼器大多采用概率域的和積譯碼算法，借助無短環(huán)和大碼長特性能夠達到接近香農限的糾錯能力。比特翻轉算法是一種硬判決算法，特點是算法時間復雜度很低，僅適用于BSC信道，可以看作是置信傳播算法的簡化形式。首先將待譯碼序列進行硬判決，將所得0/1序列代入伴隨式的校驗方程，找到使校驗方程不成立數目最多的變量節(jié)點，將該節(jié)點所對應的比特位翻轉，通過如此不停地迭代，直到滿足系統(tǒng)設定的檢驗方程或達到最大的迭代次數。

由于該算法的時間復雜度很低，非常適用于對協(xié)調效率要求較高的系統(tǒng)。該算法只進行了比特翻轉等幾種常見的邏輯運算，硬件實現(xiàn)非常容易，在對性能要求較低的場合具有重要的應用前景。

2使用比特翻轉譯碼方法的數據協(xié)調過程

本文采用一種基于LDPC比特翻轉譯碼方法和校驗子驗證的正向協(xié)調方案，滿足SW編碼的完全邊信息條件。該方案的實現(xiàn)方法主要可以分為4個模塊：密鑰生成、編碼、校驗子計算、比較譯碼。在編碼端，需要對主信息序列X進行兩步處理，首先是對序列X進行DSC壓縮，即利用LDPC校驗矩陣對X進行編碼，此處壓縮率應為n-m/n；第二步是對校驗子S進行LDPC信道編碼，將該信道碼序列M傳送給B。在解碼端，要先對M進行信道譯碼，濾除BSC信道噪聲的影響，再對譯碼后的序列結合邊信息序列Y進行最后的聯(lián)合譯碼。

需要注意的是，對于校驗子S的信道編碼和譯碼，考慮到BSC信道的不穩(wěn)定性，本文并沒有使用數據協(xié)調所用的硬判決譯碼算法，而是使用相對成熟的LLR-BP算法。將其獨立出來考慮是為了方便采用其他的信道編碼技術來適應不同的協(xié)調信道。如果所用的經典信道是AWGN信道，其譯碼步驟仍然是初始化、變量節(jié)點信息迭代、校驗節(jié)點信息迭代、譯碼判決4個步驟，唯一的不同是需修改LLR-BP算法的初始化過程。此處設BSC信道的轉移概率為p，則譯碼時概率似然比消息初始化為：

3數值仿真結果與分析

本次仿真選擇碼長為106的初始鍵值，原始密鑰信息完全隨機產生，并根據設定的量子誤碼率得到對應邊信息。該迭代過程的最大迭代次數設置為100。糾錯所選用的編碼方法為基于PEG算法的準循環(huán)LDPC碼，并用四六環(huán)檢測程序排除短環(huán)的影響，確保該方法產生的LDPC校驗矩陣的最短環(huán)長為8環(huán)且不含低碼重碼字，具有非常良好的糾錯性能。

實驗分別使用碼長固定、碼率為0.4、0.5、0.6的LDPC校驗矩陣進行數據協(xié)調，結果如圖3所示。由圖可見，隨著碼率的增加，系統(tǒng)糾錯效果顯著增強，且在低QBER的情況下正向譯碼性能明顯優(yōu)于Winnow和卷積碼方法。

圖3　各協(xié)調方法的糾錯性能

理論上的泄露信息比特數可以通過公式d=1-I(e)計算，其中e是量子誤碼率。本文所采用的LDPC協(xié)調方案所產生的泄露信息比特數與通過公開信道發(fā)送的校驗子S的比特數相等，且在合法通信雙發(fā)之間僅需一次交互。通過與已有的方法比較可知，LDPC的泄露信息比特數完全可控，可以針對不同的系統(tǒng)選擇不同的碼率，見圖4。

圖4　不同協(xié)調方法的泄露信息比特數

4結論

本文對基于LDPC碼的QKD數據協(xié)調技術的應用進行了比較全面的分析與研究，提出了一種采用SW完全邊信息編碼方法的正向協(xié)調方案，避免了計算LDPC的生成矩陣G，采用硬判決算法降低時間復雜度，從根本上提高了譯碼速度，并著重分析了不同碼率和編碼方法對協(xié)商效果的影響。實驗表明，碼率在0.4～0.6的LDPC碼的糾錯效率最強，可以在低QBER環(huán)境下取得極佳的性能。

進一步的研究工作是針對不同的篩選后碼字優(yōu)化LDPC碼校驗矩陣的度分布，排除低碼重碼問題對于譯碼性能的影響。

參考文獻

[1] 逯志欣，于麗，李康，等.基于逆向協(xié)調的連續(xù)變量量子密鑰分發(fā)數據協(xié)調[J].中國科學(G輯),2009,39(11):1606-1612.

[2] 郭大波，劉綱，張寧，等.量子高斯密鑰分發(fā)的逆向數據協(xié)調[J].量子光學學報,2013，19(3):219-226.

[3] 劉洋,章國安,何黃燕，等.基于高效糾錯碼的無線光通信系統(tǒng)性能分析[J].電子技術應用,2014,40(12):103-106.

[4] 寧平.IEEE 802.16e標準中LDPC編碼的實現(xiàn)與仿真[J].電子技術應用,2014,40(9):101-104.

[5] 白增量，王旭陽，杜鵬燕，等.連續(xù)變量量子密鑰分發(fā)的數據逆向協(xié)調[J].量子光學學報,2012,18(1):23-26.

中圖分類號：TN911.22

文獻標識碼：A

DOI：10.19358/j.issn.1674- 7720.2016.12.021

(收稿日期：2016-01-19)

作者簡介：

屠亮亮(1989-)，男，碩士研究生，主要研究方向：信道編碼、量子通信數據后處理。

徐榮青(1966-)，男，博士，教授，主要研究方向：光電檢測技術與光電信號處理。

Efficient reconciliation using LDPC hard decision for quantum key distribution

Tu Liangliang, Xu Rongqing

(School of Electronic Science and Engineering, Nanjing Univercity of Posts and Telecommunication, Nanjing 210003, China)

Abstract:Reconciliation is a significant procedure in quantum key distribution(QKD) system.It is employed to extract secure secret key from the sifted information by correcting error codes between two legal users.In this paper, we proposed an reconciliation protocol through employing a low density parity-check (LDPC) code based on hard decision decoding algorithm in QKD system.From numerical simulation while it yields low complexity comparable to the existing LDPC-based reconciliation protocols and the performance of our proposed scheme is superior to conventional Winnow and CASCADE protocols, especially at the rate of 0.4～0.6, the reconciliation efficiency reaches the maximum value.

Key words:quantum key distribution; reconciliation; LDPC