量子密鑰分發(fā)的后處理簡介

1、量子密鑰分發(fā)的后處理過程摘 要在當今的信息社會中,通信技術發(fā)揮著越來越重要的作用,同時人們對通信安全性也提出了越來越高的要求。經典密碼學是保障信息安全的有效工具,然而隨著計算機和量子計算的發(fā)展,基于數學計算復雜性假設的經典密碼體制日益受到嚴峻的挑戰(zhàn)。量子密碼學建立在量子力學原理基礎上,被證明能夠提供信息論意義上的絕對安全性。量子密鑰分發(fā)(QKD)作為量子密碼學的一種重要應用,在量子測不準原理和不可克隆性定理保障下,使合法通信雙方 Alice 和 Bob 能夠在存在竊聽者 Eve 的情況下建立無條件安全的共享密鑰。QKD 包括量子信道傳輸、數據篩選、密鑰協(xié)商和保密增強等步驟,其中密鑰協(xié)商和保密增

2、強合稱為后處理。后處理算法對 QKD 的密鑰速率和安全距離起著至關重要的作用。本文主要介紹量子密鑰分發(fā)后處理過程的基本含義，步驟和主要的算法。（量子信道傳輸的過程請參見匯報PPT。）I.簡介在量子密鑰分發(fā)實驗中,通過量子信道通信后雙方獲得的密鑰元素并不能直接作為密鑰來使用,由于信道不完善性以及竊聽者 Eve 的影響,使得雙方擁有的密鑰元素串之間存在誤差,并且有部分信息為竊聽者 Eve 所了解,我們需要引入后處理算法來獲得最終完全一致且絕對安全的密鑰串。后處理算法包括三個步驟,即數據篩選、密鑰協(xié)商和保密增強，其中主要的步驟是密鑰協(xié)商和保密增強。(1)篩選數據(Distill Data)發(fā)端Ali

3、ce 和收端Bob 先交換部分測量基（例如前10%）放棄基不同的數據后公開進行比對，測量得到誤碼率，若誤碼率低于我們的要求（例如25%），確定沒有竊聽存在，即本次通信有效，若超過這個要求值則發(fā)端Alice和收端Bob放棄所有的數據并重傳光量子序列。若通信有效，則通過對剩下的數據比較測量基后會放棄那些在傳送過程中測量基矢不一致或者是沒有收到的數據，或者是由于各種因素的影響而不合要求的測量結果，這一過程稱為篩選數據。通過這一過程也可以檢測出是否有竊聽的存在，并確定雙方的誤碼率，以便下一步進行數據協(xié)調。(2)數據協(xié)調(Error Reconciliation)經過篩選之后所得到的篩選數據(sifte

4、d key)并不能保證發(fā)端Alice和收端Bob的數據完全一致，因此要對雙方的篩選數據進行糾錯。即通過一定的算法，利用公開信道對篩后數據進行糾錯，這一過程稱之為數據協(xié)調。對數據協(xié)調的要求有：將誤碼率降低至適宜于使用；盡量減少竊聽者獲取的信息；盡量保留最多的有效數據；速度要夠快并盡量節(jié)省計算以及通信資源。這樣雖然使密鑰長度有所縮短，但保證了密鑰的安全性。(3) 密性放大(Privacy Amplification)密性放大最早是應量子保密通信的需要而提出來的，但是現在已經成為經典保密通信的重要課題之一。密性放大又稱作密性強化，它是一種通過公開信道提高數據保密性的技術。經過上述的數據協(xié)調，雙方密鑰

5、序列基本上達成一致，密性放大技術是被用來減少潛在第三者的對數據協(xié)調后得到的密鑰序列的竊聽信息。發(fā)端Alice和收端Bob隨機公開一個哈希函數h，它能映射字符串x成為一個新的串h(x)，這樣就可以是竊聽者所得到的h(x)的信息大大減少。經過上述三個步驟，Alice和Bob可以共享比較理想的密鑰，通過對BB84協(xié)議通信過程的講述，我們可以總結出量子密鑰分發(fā)的重要特點，即需要兩個信道，量子信道和經典信道，除了要在量子信道上傳遞量子信息之外，還要通過經典信道傳遞大量的輔助信息。II信息協(xié)調即使是有效的通信，篩選數據測量得到的誤碼率(QBER)一般都較大這樣的數據是不能直接用來做密鑰的，還要進行數據協(xié)調

6、糾錯及密性放大，使雙方的誤碼率達到一定的數量級才能用于可靠的保密通信系統(tǒng)中。數據協(xié)調通過公開信道進行糾錯，既然公開就一定存在竊聽的可能性。我們這里討論的是信息泄露的可能性，即竊聽者Eve能夠收到Alice與Bob公開的內容。假設Alice利用量子態(tài)向Bob傳送經典數據的過程是有噪聲的二元對稱信道，這一過程可得到篩選數據長度為n，量子誤碼率(QBER)為q，Alice與Bob的互信息 I ( A, B ) = n 1 H ( q)式中H ( q)是以q為參量的二元熵。假設數據協(xié)調后全部錯誤被改正，若長度仍為n，則有 I ( A, B ) = n亦即互信息I ( A, B)增加了nH ( q)。互

7、信息的增加是通過公開通信而獲得的，公開披漏的信息也可以為竊聽者所獲得。假設在數據協(xié)調過程中不舍棄已披露的信息，竊聽者獲得的信息為I ( E , A) n H ( q)因此通常數據協(xié)調的過程都會舍棄已公開披露的數據。同時，上述的公開信道是指可以被竊聽但不能篡改的經典通信信道，經研究后提出以下幾種比較實用的方法。2.1二分法數據協(xié)調經過數據篩選步驟的誤碼率檢驗后，發(fā)送方Alice與接收方Bob留下的篩選數據長度為n，誤碼率為q。二分法糾錯數據協(xié)調(binary correcting protocol)的步驟如下：(1) Alice和Bob共享一個隨機序列，并按照此序列將它們的數據重新排序，目的是使

8、錯誤可以均勻地隨機分布； (2) Alice和Bob分別將它們的數據串分組，分組長度為k，選取k的標準是使每組的錯誤盡可能的?。ㄒ话阋竺拷M含有的錯誤個數盡可能小于1）； (3) Alice和Bob各自計算每組數據的奇偶性并且通過公開信道進行校驗比較。如果對應的數據組奇偶性不同，則表示該組數據有錯誤位，且錯誤的個數是奇數。然后將存在錯誤的數組一分為二，同時進行奇偶檢驗計算及公開比較。如此反復直到確定沒有錯誤或進行到最后一個數位，這個最后數位就是錯誤數位。為了不讓E（Eve，竊聽者）獲得信息，我們每公開披露一次奇偶性，就將該數組的最后一位舍棄，同時舍棄被發(fā)現的數組的錯誤位； (4) 經過上述步驟

9、(3)的糾錯后，各組的奇偶性雖然相同但是仍然可能存在偶數個錯誤。繼續(xù)進行糾錯，重新排列分組使每組有奇數個錯誤，這就需要新一輪的數組長度應比上一輪的數組長度要長，例如是上一輪的兩倍。然后重復步驟(1)、(2)、(3)進行下一輪的糾錯。進行數輪糾錯后，如果留下的錯誤概率已經接近我們的要求，例如接近1%，則可以進入下一步驟；(5) 這一步的目的是確保不存在錯誤（或者說錯誤很低）。從步驟(4)得到的數據里隨機得取出一個子集，計算所取的子集的奇偶性，并公開進行比較。如果Alice和Bob的數據完全相同（也就是說沒有錯誤），即奇偶性相同。當然當他們的奇偶性相同時仍有存在偶數個錯誤，這個概率是0.5，由于偶

10、數個錯誤是校驗不出來的，因此錯誤無法校驗的概率是0.5。若兩端子集的奇偶性不同，也就是存在奇數個錯誤，則繼續(xù)進行步驟(3)的糾錯。若奇偶性相同，則重復步驟(5)，直至連續(xù)許多次都不出現錯誤為止。2.2級聯(lián)糾錯“二分法糾錯”對含有偶數個錯誤的數組不能發(fā)現錯誤，只能依靠重新分組。級聯(lián)糾錯(protocol cascade)顯著改善了這方面的性能，假設篩選數據長度為n，測量得到的誤碼率為q。其步驟如下： (1)Alice和Bob端將全部數據按照同一隨機序列重新排列，目的是使錯誤均勻地隨機分布。這時首先記下每個數據的編號，例如，Al 表示 Alice 端的序號為 l 的數據，Bl 代表 Bob 端的序

11、號為 l 的數據， l 1, 2,., n。然后雙方分別將數據按照同一數據長度k1進行分組，共分為n/k1組，k1的大小取決于誤碼率 q，目的是使每組含有的錯誤個數不大于1，如可取1/2q<k1<1/q。分組中第一組的可記為K11，第v 組則記為K1v。上標 1 表示第一次分組，即分組的輪數是1，下標 v 表示該輪分組中第 v 個分組。在每個分組之內，每個數據的標號仍是采用沒有分組前的序號。舉例說明：在分組K11內數據的標號是11, 2,., k，在分組K12中數據的標號為k1+1, k1+2,., 2k。(2)Alice和Bob分別計算各分組的奇偶性，并通過公開信道將Alice的

12、校驗結果告知Bob，Bob將Alice的結果與自己的進行比較。若出現奇偶性不一致時，利用上節(jié)所描述的二分法步驟(3)進行糾錯。與上述二分法不同的是不需要舍棄數據，并且將找到的錯誤數據取反。經過本輪糾錯后，所有的分組都只存在偶數個錯誤。(3)進行第二輪的分組糾錯，首先進行第二輪分組，每數組的長度2k也要比第一次分組的長度長，如k2=2k1，與二分法隨機分組不同的是利用隨機函數f2:1.n1.n/k2，將 n 個數據分為n/k2組，以分組K2j表示順序為 j 的第二輪分組。分組K2j內數據的標號是l|f2(l)=j。這里 l 是第一輪步驟(1)已確定的序號。凡滿足f2(l)=j的編入第二輪第 j

13、組，每個分組內按 l 有小到大的順序排列。然后對各組計算奇偶性，并公開進行比較，若彼此奇偶性不一致，則進行二分法糾錯。若在K2j內發(fā)現錯誤，它的序號是 l ，糾錯后可以判斷出在第一輪的分組中含有序號l的分組K1v 內一定還存在另外的奇數個錯誤。對這些分組再使用二分法糾錯，被發(fā)現及糾錯的個數就會顯著增加。直到不能再發(fā)現新錯誤時，結束第二輪糾錯。這時第一輪及第二輪的所有分組，仍有可能含有偶數個錯誤。(4)重復步驟(3)的分組糾錯，在第i輪(i>1)中的分組糾錯中，采用隨機函數:fi:1.n1.n/ki將數據分成長度為ki的n/ki 個組。在分組Kij內數據的序號為l|fi(l)=j。Alic

14、e與Bob分別計算各分組的奇偶性并公開比較，若發(fā)現奇偶性不一致則進行二分法糾錯。在Kij中發(fā)現序號為 l 的錯誤，經二分法糾錯后必定可以在含有數據序號l數組 1Kvu（1 u < i）中發(fā)現奇數個錯誤（也就是這一組原來有偶數個錯誤）。對這些含奇數個錯誤的分組重新使用二分法糾錯。不能再發(fā)現錯誤時重復步驟(4)進行新一輪糾錯。若本輪完全沒有發(fā)現錯誤，則進入下一步驟(5)。(5)這一步的目的同上節(jié)的步驟(5)一樣，是確認沒有錯誤，即從糾錯結束后的數據中隨機地選取一個子集，計算子集的奇偶性并比較。若Alice和Bob端的奇偶性相同，則表明存在偶數個錯誤的概率是0.5。III密性放大如圖所示,經過

15、協(xié)商以后,Alice 和 Bob 擁有相同的比特串,我們用X表示。Eve 擁有的比特串為Z=ZM,M為協(xié)商中過程中公開的信息量。Z中包含X的部分信息,我們需要通過保密增強步驟來去除 Eve 從量子信道和經典認證信道上獲取的信息量,最終提取出絕對安全的密鑰。保密增強的主要思想就是以犧牲一些比特的代價,將 Eve 對協(xié)商后比特串的確定部分盡可能均勻地分散到不確定部分中,使得 Eve 對保密增強后剩下的比特串完全不確定。遵循這樣的思想,保密增強就可以歸結為設計合適的壓縮函數,壓縮函數的每個輸出比特都取決于大部分甚至全部的輸入比特。在實際的保密增強算法實現中,壓縮函數一般是利用經典密碼學中的哈希函數

16、來進行設計的,具體過程是先設計一類性能較好的哈希函數簇 ,由 Alice和 Bob 共享,然后每次保密增強時從簇里面隨機選擇一個哈希函數,并且 Alice將選取的哈希函數的描述告訴給 Bob,隨后雙方一起將該哈希函數作用到自己的比特串上面,得到最終密鑰串。為了達到較好的保密增強效果,選取的哈希函數簇需要滿足一些特別的要求,接下來我們就來對其進行討論。首先,為了減少 Eve 鉆空子的可能性,選取的哈希函數對于任意不同的輸入取值1x 和2x ,其輸出值應該盡可能不同。因為如果相同的話,則 Eve 有可能利用自己的錯誤信息獲得正確的最終密鑰,顯然協(xié)議就失去了效力。由于我們是從哈希函數簇H 中隨機選取

17、哈希函數來使用的,因此需要保證在這個簇里面,對于不同輸入值具有相同輸出值的函數盡可能少,才能保證保密增強算法多次使用的平均性能。其次,由于 Alice 需要發(fā)送所選哈希函數的描述給 Bob,這就要求描述哈希簇里面的某個特定哈希函數所需使用的比特數盡量少。雖然所選哈希函數沒有保密的必要,但是在實際運用中,描述過長會增加通信開銷,同時影響處理速度。一般來說,我們應該將描述的長度控制在輸入比特長度的一定比例范圍內。再次,我們需要使用輸入和輸出長度較大的哈希函數簇。這是因為,在 QKD實驗中,保密增強所需要去除的比特數是通過比較一定量的樣本統(tǒng)計信道參數后估計出來的。估計所用的測試樣本應該是隨機且均勻地分布在 QKD 一輪實驗得到的分塊中,否則若 Eve 是時變的,估計結果就會有誤。為了提高估計準確度,需要使用較多的測試樣本,這樣最終可用密鑰量就相應減少了。因此,最理想的策略是使用更大的分塊,增加測試樣本數的同時減小樣本在整個分塊中的比例。這樣一來,我們就需要設計輸入和輸出長度盡可能大的哈希函數簇。最后,哈希函數應該具有較高的計算效率,這很大程度上決定了其應用前景。在實時 QKD 系統(tǒng)中,對后處理算法的時間效率是有很高要求的,因此,不論是密鑰協(xié)商過程,還是保密增強