四元域上多項式乘法Toom-3算法及其在量子密鑰分發(fā)中的應用

黃觀金,周華旭,陳創(chuàng)波,高鵬,凌杰

(1南方電網(wǎng)調(diào)峰調(diào)頻發(fā)電有限公司信息通信分公司,廣東 廣州 510700;2安徽問天量子科技股份有限公司,安徽 蕪湖 210042)

0 引言

1984年,IBM信息物理學家Bennett與加拿大蒙特利爾大學教授Brassard提出歷史上第一個量子密鑰分發(fā)(QKD)協(xié)議,簡稱BB84協(xié)議。此后,無論是理論與安全性證明,還是試驗與應用均取得了長足的進展。其中,我國在QKD領域一直走在世界的前列。2009年,郭光燦小組建成了世界上首個量子政務網(wǎng)-蕪湖“量子政務網(wǎng)”,在量子密碼的實用化道路上建立了第一個里程碑,標志著我國量子保密通信技術已具備應用水平。2016年8月,我國成功發(fā)射全球首顆量子通信科學實驗衛(wèi)星“墨子號”?！澳犹枴毙l(wèi)星在世界上首次實現(xiàn)了1200 km低軌衛(wèi)星和地面站間量子密鑰分發(fā),突破了傳輸距離的極限,并在星地之間1400 km鏈路完成單光子量子比特隱形傳態(tài),為超遠距離量子通信組網(wǎng)奠定了基礎。

QKD采用兩組非正交量子態(tài)作為信息載體,在通信雙方實現(xiàn)對稱密鑰分發(fā),其安全性由量子不可分割、測不準原理、未知量子態(tài)不可精確測量等量子力學原理保證,具有信息論可證明安全性。再結(jié)合一次一密方案可以實現(xiàn)無條件安全的保密通信。QKD分發(fā)主要包含以下幾個階段:量子信號制備、傳輸與測量、對基、糾錯和安全增強等。在安全增強中需要使用通用哈希函數(shù)對密鑰進行壓縮,提取出安全密鑰,其具體實現(xiàn)包括基于模算術、基于二元矩陣乘法和基于有限域乘法的安全增強方法,主要的計算復雜度分別在于大整數(shù)乘法、二元矩陣乘法和有限域上多項式乘法。QKD的安全性分析一般要求數(shù)據(jù)量至少要達到105～106量級,因此安全增強的效率特別依賴于實現(xiàn)這幾類乘法的算法選擇及其復雜度。

QKD中安全增強均基于二元域,且長度超過105。在數(shù)據(jù)量大時,會考慮用并行計算或硬件實現(xiàn)來提升性能,Karatsuba算法速度偏慢,Schonhage-Strassen/FFT雖然速度快但是需要消耗大量資源,Toom-3比較適中。但是二元域上多項式乘法Toom-3算法直到2007年才由Bodrato[4]給出,該算法需要額外執(zhí)行小多項式的乘法和除法,其中除法并不適合并行計算與硬件實現(xiàn)。

本文提出一種四元域上多項式乘法Toom-3算法并給出詳細的計算公式,進而提供了一種新的基于有限域乘法的安全增強方法,該方法適用于長度n=2m(其中m為奇數(shù))的情形。所提出算法不需要額外進行小多項式除法,實際復雜度優(yōu)于二元域上多項式乘法Toom-3算法,適合并行計算與硬件實現(xiàn)。

1 基于四元域上多項式乘法的安全增強方法

QKD在量子傳輸及糾錯階段均會泄露信息,安全增強使用通用哈希函數(shù)來壓縮泄露的信息,并提取出安全密鑰。假設安全增強前的密鑰為n bit,QKD安全性分析根據(jù)合適的GLLP公式計算可提取的安全密鑰量為k bit。記二元域F2=GF(2)={0,1},集合,其中k≤n為正整數(shù)。文獻[5]提出使用通用哈希函數(shù)族來實現(xiàn)安全增強。通用哈希函數(shù)族的定義如下。

1.1 基于二元域上多項式乘法的安全增強實現(xiàn)方式

在上述安全增強過程中,最耗時間的是步驟4,需要進行二元域上多項式的乘法。二元域上多項式的乘法也有多種算法選擇,例如引言中介紹的Karatsuba、Toom-3和Sch¨onhage-Strassen算法。其中文獻[4]給出的Toom-3算法需要進行小多項式的乘法和除法,為改進安全增強的復雜度,下文提出一種基于四元域上多項式乘法的安全增強方法。

1.2 基于四元域上多項式乘法的安全增強實現(xiàn)方式

步驟5:對h進行投影,得到Projn,k(h)=(h0,h1,···,hk-1)∈F2k,即為安全增強的輸出。

其中最耗時間的仍然是步驟4,需要進行四元域上多項式的乘法。四元域上多項式的乘法同樣也有多種算法選擇,如引言中介紹的Karatsuba、Toom-3和Sch¨onhage-Strassen算法。

2 四元域上多項式乘法Toom-3算法

Toom-3算法采用分治的思想將長多項式乘法分解為多個短多項式乘法,再遞歸循環(huán)將短多項式乘法分解為更短多項式乘法,最終獲得性能上的優(yōu)化。

四元域上多項式乘法Toom-3算法可分為5個步驟,具體計算與公式如下所述。

3 四元域上多項式乘法Toom-3算法復雜度分析

上一節(jié)四元域上多項式乘法Toom-3算法的復雜度分析如表1所示。在對多項式 f(x)∈F4[x]進行數(shù)量乘法αf(x)時,其復雜度等同于多項式的加法。另外,點P5的選取與矩陣計算等均是固定的,故不納入計算復雜度中。

表1 四元域上多項式乘法Toom-3算法復雜度分析Table 1 Complexity analysis of Toom-3 algorithm for polynomial multiplication over finite field F4

4 總結(jié)與展望

提出一種四元域上多項式乘法Toom-3算法并給出詳細的計算公式,并利用該算法實現(xiàn)基于有限域乘法的安全增強方法。與基于模算術或基于二元矩陣乘法的安全增強方法相比,所提出方法需求的隨機數(shù)數(shù)量減半,算法復雜度達到了O(n1.465)。由于沒有使用多項式除法,且Toom-3的算法本身采用分治思想,適合并行計算或硬件實現(xiàn)。目前QKD的密鑰生成速度還無法真正保障一次一密對密鑰量的需求,而安全增強速度的提升將為高速Q(mào)KD的發(fā)展提供重要保障。

所提出方法的一個重要創(chuàng)新點在于通過考慮二元域的擴張,使得有限域上Toom-Cook系列算法成為可能。沿著相同的方向,可以考慮二元域的更高次擴張,實現(xiàn)更高次的Toom-k算法,也可以考慮其他非特征2有限域上的Toom-Cook系列算法,提供適合并行計算或硬件實現(xiàn)的更優(yōu)QKD安全增強方法。