抗量子計算的裝備保障云服務同態認證方案設計

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

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

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

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

1 NTRU格與高斯抽樣

1.1 符號說明

1.2 NTRU格理論方法

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

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

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

定義3(NTRU格)設n=2κ，κ∈Z+，素數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問題)給定參數n,m,q，給定多項式向量h=g·f-1modq，則NTRU-SIS問題就是尋求2個非零的小系數多項式u,v∈Rq，‖u‖,‖v‖≤β(n)并且滿足u+v·h=0 modq。

1.3 高斯抽樣相關理論

其中，如果當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對應的向量為v，計算e=t+v。則有Ae=umodq，u的原像是e。我們將原像高斯抽樣函數簡記為SamplePre(·)，也就是有e←SamplePre(B,σ,u)。

2 裝備保障云服務同態認證方案設計

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

圖1 裝備保障云服務同態認證模型

2.1 系統參數設置

2.2 系統密鑰生成

表1 系統密鑰生成算法

續表

輸入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進行截取最近整數運算,并將截取的結果記為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 同態認證過程

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

表2 同態認證算法

2.4 認證驗證階段

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

則接受該認證值。

2.5 方案正確性證明

定理1本方案在給定的系統參數下，經過同態認證過程產生的認證值能夠通過認證驗證算法。

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

3.1 弱內容隱私性

定理2本文所構造的新方案滿足弱內容隱私性。

3.2 存在性不可偽造性

定理3在NTRU-SIS問題困難性假設下，本文構造的方案在隨機預言機模型下滿足適應性選擇消息的存在性不可偽造性。

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

1)系統建立：輸入安全參數n，挑戰者C生成系統公共參數PP，運行密鑰生成算法產生系統公鑰和認證私鑰，然后挑戰者C將系統公共參數PP發送給攻擊者A。

2)詢問階段：任意的攻擊者A適應性地進行如下哈希詢問和認證詢問：

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

3.3 效率的分析與比較

表3 與已有抗量子同態認證方案效率的比較

4 結語

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