基于LDPC碼的信息調(diào)和協(xié)議

武登杰

（西南大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院 重慶 400715）

基于LDPC碼的信息調(diào)和協(xié)議

武登杰

（西南大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院 重慶 400715）

考慮到LDPC碼的譯碼特性可以逼近Shannon信道容量限，本文給出了基于LDPC碼的信息調(diào)和協(xié)議。它具有交互次數(shù)少，糾錯能力強(qiáng)的特點。

LDPC碼；信息調(diào)和協(xié)議；BSC信道

1 引言

信息調(diào)和是QKD的一個重要組成部分，也是密碼學(xué)研究的一個熱門領(lǐng)域。1992年，Bennett et al.[1]提出了“二分法糾錯”的信息調(diào)和協(xié)議，但它不能發(fā)現(xiàn)偶數(shù)個錯誤，交互次數(shù)頻繁。2003Buttler et al.[3]提出基于漢明碼的“Winnow”信息調(diào)和協(xié)議，效率比較高，但糾錯能力有限。鑒于此，本文提出了基于LDPC碼的信息調(diào)和協(xié)議。該協(xié)議具有交互次數(shù)少，糾錯能力強(qiáng)的特點。

2 LDPC碼的背景知識

LDPC碼的定義：

一個碼長為n、信息位個數(shù)為k的線性分組碼可以由一個生成矩陣G來定義，信息序列i1×k通過G被映射到碼字x=i·G。線性分組碼也可以由一個一致校驗矩陣 H（n-k）×n來等效描述，所有碼字均滿足 x·HT（n-k）×n。LDPC碼是一種線性分組碼，它的名字來源于其校驗矩陣的稀疏性，即校驗矩陣中只有數(shù)量很少的元素為“1”，大部分都是“0”。Gallager最早給出了正則LDPC碼的定義，具體來講正則LDPC碼的校驗矩陣H滿足下面三個條件：

（1）H 的每行有 ρ 個“1”；

（2）H 的每列有 λ 個“1”，λ＞3；

（3）與碼長和H矩陣的行數(shù)相比，ρ和λ都很小。

3 LDPC的譯碼

關(guān)于LDPC的譯碼方法有很多，本文只考慮基于BSC信道下的置信傳播算法。設(shè)發(fā)端發(fā)送的碼字序列為x=｛x1，x2，…，xn｝∈GF（n2），在接收端接收到的序列為y=｛y1，y2，…，yn｝∈GF（n2），M（j）表示與變量節(jié)點j相連的所有校驗節(jié)點所構(gòu)成的集合，M（j）i表示M（j）中除去其中的校驗節(jié)點i后剩下的集合；N（j）表示與校驗節(jié)點i相連的所有變量節(jié)點構(gòu)成的集合，N（i）j表示N（i）中除去其中的變量節(jié)點j后剩下的集合。BSC信道下LDPC碼的硬判決譯碼算法流程如下：

（1）初始化：所有變量節(jié)點賦初值fj=yj，對所有Qij賦初值

4 基于LDPC碼的信息調(diào)和協(xié)議

結(jié)合[2]中非交互式的信息調(diào)和協(xié)議，基于LDPC碼的信息調(diào)和協(xié)議步驟如下：

（1）Alice隨機(jī)生成一個比特串x；

（2）Alice用公開的LDPC碼的生成矩陣G編碼x得到碼字c；

（3）Alice再用她的初始密鑰KA與碼字c做異或，得到KA⊕c，并將它發(fā)給Bob；

（4）Bob將收到的比特串與他的初始密鑰KB進(jìn)行相同的運(yùn)算，得到（KA⊕c）⊕KB=c⊕e，Bob用LDPC碼的校驗矩陣H進(jìn)行譯碼，得到碼字c^=c，最后再將c^與收到的KA⊕c做異或得到KA，KA就是最終的密鑰。

5 結(jié)束語

本文主要介紹了基于LDPC碼的信息調(diào)和協(xié)議，利用了BSC信道下LDPC碼的硬判決譯碼算法。這個譯碼算法具有復(fù)雜度低，利于操作，適用于信息調(diào)和。

[1]C.Bennett，F(xiàn).Bessette，G.Brassard，L.Salvail，J.Smolin，Experimental Quantum Cryptography.Journal of Cryptology，1992.

[2]D.Mayers，Unconditional security in quantum cryptography.Jounal of the ACM，48（3）：351～406，2001.

[3]W.Buttler et al，F(xiàn)ast，efficient error reconciliation for quantum cryptography.Jounal of the ACM，Phys.Rev.A.67:052303，1～8，2003.

TN918

A

1004-7344（2016）08-0024-01

2016-3-1