抗量子計算的裝備保障云服務(wù)同態(tài)認(rèn)證方案設(shè)計

張建航, 曹澤陽, 宋曉峰, 邢立鵬

(1.空軍工程大學(xué)防空反導(dǎo)學(xué)院,西安,710051； 國防科技大學(xué)信息通信學(xué)院，西安，710106)

裝備保障信息網(wǎng)絡(luò)是執(zhí)行全部裝備保障信息功能的網(wǎng)絡(luò)，是保障信息化建設(shè)的重點內(nèi)容，也是信息化裝備保障的核心[1]。隨著裝備保障信息網(wǎng)絡(luò)綜合保障業(yè)務(wù)的不斷擴展和保障對象的復(fù)雜多樣化，在裝備保障信息網(wǎng)絡(luò)中建設(shè)云服務(wù)平臺已成為實現(xiàn)高速、可靠裝備保障的必然趨勢。云服務(wù)提供高速便捷、功能多樣服務(wù)的同時，也面臨著諸多的安全威脅與挑戰(zhàn)[2-3]。在保障云端數(shù)據(jù)的隱私性的同時，對云端數(shù)據(jù)來源與正確性的認(rèn)證需求也越來越重要。如何保障云端數(shù)據(jù)的認(rèn)證性，以及在云端數(shù)據(jù)進(jìn)行第三方的外包計算時的可靠性驗證，是一個需要解決的新問題。同態(tài)認(rèn)證就是能夠?qū)崿F(xiàn)這樣認(rèn)證功能的關(guān)鍵技術(shù)。

Johnson、Molnar、Song等[4]首次定義了同態(tài)認(rèn)證的概念。隨后，出現(xiàn)了諸多基于傳統(tǒng)數(shù)論困難問題構(gòu)造的同態(tài)認(rèn)證方案[5-7]。但是，近年來隨著量子算法的提出和量子計算機研制的快速發(fā)展，基于傳統(tǒng)數(shù)論問題困難設(shè)計的同態(tài)認(rèn)證方案都將面臨著潛在的致命威脅[8-9]?；诟窭碚撛O(shè)計的密碼方案是一類能夠抗量子計算的密碼，其具有線性結(jié)構(gòu)且安全性高的顯著優(yōu)勢[10]。Boneh和Freeman[11]首次給出了標(biāo)準(zhǔn)格上的線性同態(tài)認(rèn)證方案，并且在文獻(xiàn)[12]中給出了多項式同態(tài)認(rèn)證方案。文獻(xiàn)[13]在Boneh和Freeman工作的基礎(chǔ)上進(jìn)行了改進(jìn)，給出了一個效率更高的線性同態(tài)認(rèn)證方案。但是，這些線性同態(tài)方案顯著的缺點是運行仍需要大量的存貯資源和計算資源，導(dǎo)致方案的運行過程效率偏低，實際應(yīng)用價值較低。本文利用NTRU格[14]多項式環(huán)的結(jié)構(gòu)優(yōu)勢，將NTRU密鑰生成算法與NTRU格上原像高斯抽樣算法相結(jié)合，設(shè)計出了首個面向裝備保障云服務(wù)的高效線性同態(tài)認(rèn)證方案，簡化了系統(tǒng)的密鑰量，提高了高斯抽樣算法的運行效率，節(jié)約了算法運行過程中的計算資源。從理論上證明了新方案滿足弱內(nèi)容隱私性，且在隨機預(yù)言機模型下，證明了新方案在NTRU-SIS問題困難性條件下達(dá)到了適應(yīng)性選擇身份和選擇消息攻擊下的存在性不可偽造性。

1 NTRU格與高斯抽樣

1.1 符號說明

1.2 NTRU格理論方法

定義1(格)設(shè)B={b1,b2,…,bm}?Rn，b1,b2,…,bm為m個線性獨立的向量，則:

這樣的集合Λ或Λ(B)稱為格。其中b1,b2,…,bm稱為格Λ的一組基，簡稱格基。

定義2(反循環(huán)矩陣)由多項式向量f定義的反循環(huán)矩陣如下所述：

定義3(NTRU格)設(shè)n=2κ，κ∈Z+，素數(shù)q≥2。令多項式f,g∈R，f∈R×，并且h=g·f-1modq，那么由h和q決定的集合：

Λh,q={(u,v)∈R2|u+v·h=0 modq}

定義4(NTRU-SIS問題)給定參數(shù)n,m,q，給定多項式向量h=g·f-1modq，則NTRU-SIS問題就是尋求2個非零的小系數(shù)多項式u,v∈Rq，‖u‖,‖v‖≤β(n)并且滿足u+v·h=0 modq。

1.3 高斯抽樣相關(guān)理論

其中，如果當(dāng)c=0時，那么我們將DΛ,σ,0簡記為DΛ,σ。

定義6(原像高斯抽樣[16]) 格上的原像高斯抽樣分為2步計算：

1)令vn←0,cn←c,i=n,n-1,…,1

c.令ci-1←ci←zibi，

并令vi-1←vi←zibi;

2)輸出v0。

Step2原像輸出。對任意給定的向量t∈Zm滿足At=umodq，運行STEP1抽取向量-t∈Zm對應(yīng)的向量為v，計算e=t+v。則有Ae=umodq，u的原像是e。我們將原像高斯抽樣函數(shù)簡記為SamplePre(·)，也就是有e←SamplePre(B,σ,u)。

2 裝備保障云服務(wù)同態(tài)認(rèn)證方案設(shè)計

一個典型的裝備保障云服務(wù)系統(tǒng)模型一般由3個實體構(gòu)成。一是用戶(User)。裝備保障信息網(wǎng)絡(luò)中的用戶包括人、計算機、武器裝備等，這些用戶的大量數(shù)據(jù)文件存儲在云服務(wù)器中，通過云服務(wù)器進(jìn)行數(shù)據(jù)管理和應(yīng)用；二是云服務(wù)器(Cloud Server)。云服務(wù)器主要對用戶的數(shù)據(jù)進(jìn)行管理，為各種用戶提供不同需求的數(shù)據(jù)服務(wù)以及計算資源。三是密鑰生成器(Key Generator)。密鑰生成器用來產(chǎn)生云服務(wù)器中數(shù)據(jù)的認(rèn)證密鑰以及分配給各類用戶公鑰，即驗證密鑰。如圖1所示，在裝備保障信息網(wǎng)絡(luò)同態(tài)認(rèn)證的流程是：①密鑰生成器產(chǎn)生系統(tǒng)需要的密鑰，將認(rèn)證私鑰發(fā)送給云服務(wù)器，將公鑰發(fā)送給不同的用戶；②云服務(wù)器對存儲的一組數(shù)據(jù)采用線性同態(tài)算法進(jìn)行認(rèn)證，并且將認(rèn)證值和數(shù)據(jù)存儲在同一個數(shù)據(jù)服務(wù)器上；③用戶從云服務(wù)器中下載需要的數(shù)據(jù)；④用戶對該組數(shù)據(jù)認(rèn)證值的線性組合進(jìn)行檢查，對存儲在云服務(wù)器的數(shù)據(jù)需要進(jìn)行認(rèn)證操作。如果通過驗證，那么說明下載的數(shù)據(jù)線性組合是合法的完整的數(shù)據(jù)，這時用戶可以放心使用該組數(shù)據(jù)，否則驗證不通過，則用戶認(rèn)為該組數(shù)據(jù)不合法，不予接受。

圖1 裝備保障云服務(wù)同態(tài)認(rèn)證模型

2.1 系統(tǒng)參數(shù)設(shè)置

2.2 系統(tǒng)密鑰生成

表1 系統(tǒng)密鑰生成算法

續(xù)表

輸入n,q,σ輸出:mpk=h,msk=B∈Z2n×nq4)利用擴展歐幾里得算法,計算ρf,ρg∈R和rf,rg∈Z且滿足以下條件:-ρf·f=rfmod (xn+1)-ρg·g=rgmod (xn+1)5)如果gcd(rf,rg)≠1,或者gcd(rf,q)≠1,那么返回步驟1);6)利用擴展歐幾里得算法,計算u,v∈Z且滿足條件u·rf+v·rg=1;7)計算f'←qvρg,g'←-quρf;8)對f'· f+g'· gf· f+g· g進(jìn)行截取最近整數(shù)運算,并將截取的結(jié)果記為k∈Z;9)提取多項式f',g':f'←f'-k`·f,g'←g'-k·g;10)計算h←f-1·gmod q,B←A(g) -A(f)A(g') -A(f')

2.3 同態(tài)認(rèn)證過程

同態(tài)認(rèn)證算法如表2所示。輸入系統(tǒng)的參數(shù)n,q,σ,i,h,B,αi，消息子空間的標(biāo)簽τ∈{0,1}n，消息子空間V=(v1,v2,…,v)。輸出聯(lián)合認(rèn)證值為并且滿足條件e′j+e″j·h=hj。

表2 同態(tài)認(rèn)證算法

2.4 認(rèn)證驗證階段

2)e′j+e″j·h=hjmodq。

則接受該認(rèn)證值。

2.5 方案正確性證明

定理1本方案在給定的系統(tǒng)參數(shù)下，經(jīng)過同態(tài)認(rèn)證過程產(chǎn)生的認(rèn)證值能夠通過認(rèn)證驗證算法。

3 方案的安全性證明與效率分析

3.1 弱內(nèi)容隱私性

定理2本文所構(gòu)造的新方案滿足弱內(nèi)容隱私性。

3.2 存在性不可偽造性

定理3在NTRU-SIS問題困難性假設(shè)下，本文構(gòu)造的方案在隨機預(yù)言機模型下滿足適應(yīng)性選擇消息的存在性不可偽造性。

證明：對于任何一個具有多項式時間攻擊能力的攻擊者A，它與挑戰(zhàn)者C進(jìn)行交互式游戲的過程設(shè)計具體如下：

1)系統(tǒng)建立：輸入安全參數(shù)n，挑戰(zhàn)者C生成系統(tǒng)公共參數(shù)PP，運行密鑰生成算法產(chǎn)生系統(tǒng)公鑰和認(rèn)證私鑰，然后挑戰(zhàn)者C將系統(tǒng)公共參數(shù)PP發(fā)送給攻擊者A。

2)詢問階段：任意的攻擊者A適應(yīng)性地進(jìn)行如下哈希詢問和認(rèn)證詢問：

綜上所述，在NTRU-SIS問題困難性條件下，該方案在隨機預(yù)言機模型下滿足適應(yīng)性選擇消息的存在性不可偽造性。

3.3 效率的分析與比較

表3 與已有抗量子同態(tài)認(rèn)證方案效率的比較

4 結(jié)語

為解決裝備保障云服務(wù)中抗量子計算的安全認(rèn)證問題，結(jié)合NTRU格簡潔的幾何結(jié)構(gòu)，提出了一種基于NTRU格快速的面向計算資源和存儲資源嚴(yán)重受限的裝備保障信息網(wǎng)絡(luò)的線性同態(tài)認(rèn)證方案。從理論上證明了新方案的正確性和安全性，并對方案的運行效率進(jìn)行了比較分析。這對于云計算環(huán)境下實現(xiàn)高效的裝備保障信息網(wǎng)絡(luò)同態(tài)認(rèn)證具有重要的理論意義和應(yīng)用價值。如何在標(biāo)準(zhǔn)模型下設(shè)計基于NTRU格的(分層)線性同態(tài)認(rèn)證方案，將是下一步深入研究的內(nèi)容。