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

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

0 引言

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

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

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

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

1 基于四元域上多項(xiàng)式乘法的安全增強(qiáng)方法

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

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

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

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

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

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

2 四元域上多項(xiàng)式乘法Toom-3算法

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

四元域上多項(xiàng)式乘法Toom-3算法可分為5個(gè)步驟,具體計(jì)算與公式如下所述。

3 四元域上多項(xiàng)式乘法Toom-3算法復(fù)雜度分析

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

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

4 總結(jié)與展望

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

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