□ 張薇薇

一、引言

量子密鑰與經(jīng)典密鑰體系的根本不同在于，其采用微觀粒子的不同量子態(tài)作為密鑰的載體，由量子力學(xué)的基本原理保證了該過程的不可竊聽、不可破譯性，從而提供了一種更為安全的密鑰體系。但在量子密鑰分發(fā)(Quantum Key Distribution，QKD)過程中，由于系統(tǒng)自身暗噪聲和外界干擾的存在，使進(jìn)行QKD的雙方產(chǎn)生的量子密鑰存在一定的誤碼。所以一般在QKD系統(tǒng)中會增加一個糾錯過程來消除密鑰中存在的誤碼。QKD系統(tǒng)的糾錯過程一般基于經(jīng)典通信領(lǐng)域中的編譯碼算法，加以流程上的少量變通。

在QKD系統(tǒng)的糾錯過程中，進(jìn)行QKD的雙方之一，暫定為Alice，以一定的算法作用于糾錯之前的密鑰，從而產(chǎn)生校驗(yàn)信息，并將校驗(yàn)信息通過經(jīng)典通信方式發(fā)送給進(jìn)行QKD的另外一方，暫定為Bob。Bob可以依據(jù)接收到的校驗(yàn)信息來判定Alice方的密鑰位是邏輯“1”還是邏輯“0”，或者是一個概率，用來表示Alice方的密鑰位是邏輯“1”或邏輯“0”的概率，再通過軟判決方式判定Alice方的密鑰位是邏輯“1”還是邏輯“0”。

本文將討論的內(nèi)容涉及編解糾錯碼領(lǐng)域，具體涉及一種適用于QKD系統(tǒng)的低密度奇偶校驗(yàn)碼(Low Density Parity Check Code，LDPC)糾錯算法。

二、LDPC算法介紹

在QKD領(lǐng)域常見的糾錯算法有Cascade算法及其變種算法、Winnow算法，還有低密度奇偶校驗(yàn)碼(Low Density Parity Check Code，LDPC)的算法。由于LDPC算法在性能上被證明優(yōu)于Winnow算法，所需交互次數(shù)少于標(biāo)準(zhǔn)Cascade算法，所以LDPC算法已經(jīng)成為當(dāng)前該領(lǐng)域研究的熱點(diǎn)。目前LDPC譯碼算法主要分為兩類，即基于校驗(yàn)和統(tǒng)計(jì)迭代的比特翻轉(zhuǎn)(Bit Flip，BF)算法和基于概率的置信傳播(Belief Propagation，BP)迭代譯碼算法。

(一)基于校驗(yàn)和統(tǒng)計(jì)迭代的比特翻轉(zhuǎn)算法。B方收到校驗(yàn)序列 P1×(n-k)后與自身持有的密鑰 TB1×k按照［TB1×k，P1×(n-k)］的形式組合成碼字 S1×n，即 S1×n={s0，s1，s2，…sn-1}=［T1B×k，P1×(n-k)］。然后按照下列公式計(jì)算校驗(yàn)伴隨序列 B1×(n-k)={b0，b1，b2，…，bn-k-1}。

如果伴隨序列 B1×(n-k)為全0序列，則說明碼字 S1×n沒有錯誤，否則按照下式可計(jì)算出校驗(yàn)統(tǒng)計(jì)數(shù)值序列F1×n。

找出校驗(yàn)統(tǒng)計(jì)數(shù)值列F1×n中值最大的元素fj的位置j，然后翻轉(zhuǎn)碼字S1×n中對應(yīng)位置的元素sj，到一次修正后的碼字序列S'1×n，將修正后的碼字序列 S'1×n代替原碼字序列S1×n，按照以上步驟處理，直到伴隨序列 B1×(n-k)為全0時(shí)截止，則經(jīng)過多次修正之后的碼字序列S'1×n即為譯碼結(jié)果，截取其前k比特即為糾錯之后的密鑰數(shù)據(jù)T1B×k，且此時(shí)T1B×k=TA1×k。

該算法簡單易于硬件實(shí)現(xiàn)，但性能較差，所以不常用。

(二)基于概率的置信傳播算法。基于概率的置信傳播算法可以基于不同的量度而衍生出不同的置信傳播算法，例如概率差BP譯碼、概率比BP譯碼或?qū)?shù)似然比BP譯碼。但這些算法操作步驟以及本質(zhì)原理是等價(jià)的，這里僅以對數(shù)似然比BP譯碼算法為例介紹。

B方收到校驗(yàn)序列P1×(n-k)后與自身持有的密鑰T1B×k按照［T1B×k，P1×(n-k)］的形式組合成碼字 S1×n，即 S1×n={s0，s1，s2，…sn-1}=［T1B×k，P1×(n-k)］。碼字 S1×n中的每一個元素都被稱作信息節(jié)點(diǎn)。

計(jì)算校驗(yàn)伴隨序列的公式 B1×(n-k)=S1×n·［Hn-k)×n］T由(n-k)個線性方程組成，每個方程對應(yīng)一個校驗(yàn)節(jié)點(diǎn)。

那么對數(shù)似然比量度下的BP譯碼算法迭代步驟如下:

1.初始化信息節(jié)點(diǎn)。如果初始密鑰錯誤率為e，那么用fi初始化信息節(jié)點(diǎn)，fi的計(jì)算公式如下:

2.更新校驗(yàn)節(jié)點(diǎn)消息。按照下列計(jì)算公式逐個更新所有校驗(yàn)節(jié)點(diǎn)的值。

上式中，Rij表示第i個校驗(yàn)節(jié)點(diǎn)傳遞給第j個信息節(jié)點(diǎn)的置信消息，l表示迭代次數(shù)，Rlij表示在第l次迭代中第i個校驗(yàn)節(jié)點(diǎn)傳遞給第j個信息節(jié)點(diǎn)的置信消息。Qik表示第i個信息節(jié)點(diǎn)傳遞給第j個校驗(yàn)節(jié)點(diǎn)的置信消息，Qlik表示在第l次迭代中第i個信息節(jié)點(diǎn)傳遞給第j個校驗(yàn)節(jié)點(diǎn)的置信消息，Q0ik=fi。N(i)表示與校驗(yàn)節(jié)點(diǎn)i相連的所有信息節(jié)點(diǎn)所構(gòu)成的集合，N(i)j表示N(i)中除去信息節(jié)點(diǎn)j后剩下的集合。

3.更新信息節(jié)點(diǎn)消息。按照下列計(jì)算公式逐個更新所有信息節(jié)點(diǎn)的值。

上式中，M(j)表示與信息節(jié)點(diǎn)j相連的所有校驗(yàn)節(jié)點(diǎn)所構(gòu)成的集合，M(j)i表示M(j)中除去校驗(yàn)節(jié)點(diǎn)i剩下的集合。

4.判決。對所有的信息節(jié)點(diǎn)按照下式計(jì)算Qlj。

判決規(guī)則為

5.校驗(yàn)。按照下式計(jì)算校驗(yàn)伴隨序列B1×(n-k)。

B1×(n-k)=S1×n·［H(n-k)×n］T

如果B1×(n-k)為全零序列，則說明譯碼完全正確，如果不全為0則說明碼字S1×n仍有錯誤，此時(shí)如果還沒有超過設(shè)定的迭代次數(shù)上限，則回到第2步進(jìn)行下一輪迭代，否則認(rèn)為譯碼失敗。

在譯碼成功后截取S1×n的前k比特即為糾錯之后的密鑰數(shù)據(jù) TB1×k，且此時(shí) TB1×k=TA1×k。

該算法硬件實(shí)現(xiàn)非常不易，但性能非常不錯。

圖1 一個Tanner圖實(shí)例

現(xiàn)有技術(shù)方案會以Tanner圖來描述一個LDPC碼，圖1是一個具體的Tanner圖，后面的介紹也基于此圖。Tanner圖有節(jié)點(diǎn)和邊組成，上面圓形節(jié)點(diǎn)代表校驗(yàn)節(jié)點(diǎn)，下面方形節(jié)點(diǎn)代表變量節(jié)點(diǎn)。正如圖1中所示，某校驗(yàn)節(jié)點(diǎn)通過邊①、②、③和④與另外4個變量節(jié)點(diǎn)相連。

足跡深度表征區(qū)域內(nèi)人類活動對自然資源存量占用程度，足跡深度越大表示區(qū)域自然資本存量加速減少，生態(tài)承載力下降。

當(dāng)前QKD系統(tǒng)中LDPC糾錯中BP譯碼算法，依舊采用了經(jīng)典通信中類似做法，并未利用QKD系統(tǒng)的特點(diǎn)，導(dǎo)致譯碼迭代次數(shù)偏高，譯碼計(jì)算量大。

三、一種改進(jìn)型LDPC譯碼算法

(一)算法執(zhí)行過程。QKD系統(tǒng)出于安全考慮允許在糾錯過程中舍棄部分密鑰，通常這種舍棄過程發(fā)生在隱私放大處理步驟，如果在糾錯過程中有密鑰被舍棄，則通過修正隱私放大因子即可達(dá)到等價(jià)效果。本提案正是利用QKD系統(tǒng)的這一特點(diǎn)，在LDPC譯碼過程中拋棄可疑密鑰，以減少譯碼迭代次數(shù)，降低譯碼計(jì)算量。

首先為本方案取一個名稱——圈地譯碼(Enclosure Decoding，以下簡稱ED)算法，ED算法首先按照經(jīng)典BP算法迭代處理，然后按照一定規(guī)則將一部分?jǐn)?shù)據(jù)圈起來，正如圈地一樣，然后再拋棄圈內(nèi)的數(shù)據(jù)，畫圈的規(guī)則是讓盡可能多的錯誤比特被圈進(jìn)來。這樣就無需更多的計(jì)算步驟去糾正這些錯誤比特，從而降低譯碼算法的迭代次數(shù)。當(dāng)然畫圈的時(shí)候，不可隨意擴(kuò)大畫圈范圍，因?yàn)檫@樣會劣化糾錯效率。

該算法的核心思想是確定發(fā)生誤碼的大概范圍比精確確定誤碼的位置所需的計(jì)算復(fù)雜度低，然后再拋棄這些被認(rèn)定為可能發(fā)生誤碼的范圍內(nèi)的所有數(shù)據(jù)，只需保證留下來的數(shù)據(jù)是絕對正確即可。該算法具體實(shí)施步驟如下:

假設(shè)譯碼方原始碼字為C，伴隨序列S，步驟如下:

當(dāng)Si=0時(shí):

當(dāng)Si=1時(shí):

2.變量節(jié)點(diǎn)消息處理。對所有的變量節(jié)點(diǎn)i和相鄰的校驗(yàn)節(jié)點(diǎn)j∈R(i)，計(jì)算第i個變量節(jié)點(diǎn)傳向第j個校驗(yàn)節(jié)點(diǎn)的消息:

式中:Kij是校正因子。

3．判決譯碼。對所有變量節(jié)點(diǎn)計(jì)算硬判決信息，若qli(0)＜qli(1)，則=1，否則則=0。

這里需要額外說明的是拋棄規(guī)則和額外的CRC校驗(yàn)過程，如下:

(1)拋棄規(guī)則。對每個變量節(jié)點(diǎn)，計(jì)算其可信度:

設(shè)置可信度閾值為ɑ，如果pli＜0，則把該變量節(jié)點(diǎn)列入拋棄對象，可信度低的變量節(jié)點(diǎn)優(yōu)先拋棄，每次迭代結(jié)束時(shí)需要統(tǒng)計(jì)被列為拋棄對象的變量節(jié)點(diǎn)數(shù)，如果這個數(shù)低于校驗(yàn)節(jié)點(diǎn)數(shù)，則停止迭代，拋棄這些變量節(jié)點(diǎn)。

圖2 迭代次數(shù)與誤碼率關(guān)系

(2)額外的步驟。迭代結(jié)束時(shí)譯碼方可以將被拋棄的變量節(jié)點(diǎn)的位置發(fā)送編碼方，做同步拋棄。此外由于變量節(jié)點(diǎn)拋棄之后不能繼續(xù)以校驗(yàn)方程是否成立來判斷是否譯碼成功，因此譯碼方可以將拋棄之后剩余的數(shù)據(jù)計(jì)算一次CRC，將CRC發(fā)送給編碼方。編碼方通過CRC確認(rèn)驗(yàn)證譯碼方是否成功。

(二)算法性能。采用本提案的譯碼算法，對比經(jīng)典BP譯碼，我們通過軟件模擬得到在不犧牲糾錯效率的情況下，ED譯碼算法可比經(jīng)典BP譯碼算法節(jié)省約1/3的迭代次數(shù)。圖2是詳細(xì)對比曲線圖。

四、結(jié)語

本文分析了現(xiàn)有LDPC譯碼算法，提出了一種改進(jìn)型的LDPC譯碼算法，該算法利用QKD系統(tǒng)糾錯過程可拋棄密鑰的特點(diǎn)，使用經(jīng)典LDPC譯碼算法，計(jì)算出各變量節(jié)點(diǎn)可信度，然后對各變量節(jié)點(diǎn)可信度做排序，拋棄可信度低的變量節(jié)點(diǎn)，以減少迭代次數(shù)。通過實(shí)際仿真結(jié)果可知該算法比經(jīng)典BP譯碼算法節(jié)省約1/3的迭代次數(shù)。

［1］Brassard，Salvail.Secret key reconciliation by public discussion［J］.Lecture Notes in Computer Science，1994，765:410～423

［2］T.Sugimoto，K.Yamazaki.A study on secret key reconciliation protocol“cascade”［J］.IEICE Trans.Fundamentals，2000，10:1987～1991