抗量子计算的装备保障云服务同态认证方案设计

张建航, 曹泽阳, 宋晓峰, 邢立鹏

(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格的(分层)线性同态认证方案，将是下一步深入研究的内容。