车联网下低频数据的动态完整性审计方案*

石玉成

（中国核动力研究设计院，四川 成都 610213）

0 引言

车联网作为有前景的物联网范例，现已成为各个国家和地区的研究热点[1-3]。车辆将数据外包给云日益成为一种趋势[4-6]，然而数据外包给云将面临完整性问题。在传统的完整性验证方案中，通过随机抽样来选取挑战数据块的方法效率低[7-9]。另外，现有安全难题随着量子计算的发展正变得愈发严重[10-12]虽然量子计算的引入使困难问题可解，但是大部分可证明安全的密码方案丧失安全性。

针对上述问题，本文基于车联网场景提出一种面向低频数据的动态完整性审计方案。本方案将采用一棵平衡二叉树实时保存用户数据访问周期信息，并使用概率比例规模抽样（Probability Proportional to Size Sampling，PPS）来根据数据实时访问周期抽取审计挑战数据块。此外，本方案基于格密码系统，只涉及简单的矩阵运算，计算开销低。

1 相关工作

近年来，学者们为了抵御量子计算机的攻击提出了一些基于格问题的审计方案。基于格密码系统的数据完整性检测方案由Xu 等人[13]基于小整数解（Short Integer Solution，SIS）问题设计。Liu 等人[14]提出了一种基于格云端数据完整性审计方案，该方案支持公开验证，但文中没有给出安全证明[15]。Liu 等人[16]又在此基础上设计了一种新的基于身份的审计方案，但该方案生成数据签名时使用了云服务器的公钥，云服务器可以伪造数据故该方案，因此也存在安全漏洞。Tian 等人[17]提出了一个新的采用格密码实现的基于身份的云端数据审计方案并给出了安全证明[18]。

本文设计了一个新的基于格密码的低频动态数据完整性审计方案。该方案通过引入索引平衡二叉树实现动态抽样及动态审计。

2 预备知识

PPS 是一种将总体按照辅助信息划分成大小不等的采样单元（Primary Sampling Units，PSU）的概率抽样。采样PSU的概率取决于PSU的大小，规模越大的PSU 有更大的概率被抽取。

假设总体规模大小为U，由n个PSU 组成，每个PSU 规模分别为U1,U2,…,Un均为整数且。若抽取l个样本，抽样间隔为I=U/l，并随机选取R∈[1,I]，根据R来均匀定位预抽取的样本，获得预抽取样本集合{R,R+I,…,R+(N-1)I}，然后根据预抽取的样本定位对应PSU，从PSU 中抽取作为输出样本。

3 低频数据动态完整性审计方案

3.1 系统模型

本研究构建了一个车联网云平台的数据完整性审计方案。本方案主要涉及车、路侧单元（Roadside Unit，RSU）、数据中心（Data Center，DC）以及密钥生成中心（Key Generation Center，KGC）4 个实体。如图1 所示。

图1 系统模型

（1）车辆（Vehicle，V）：可信实体，数据所有者，通过车载设备采集车辆数据。

（2）RSU：可信实体，具有一定的计算和存储能力。

（3）DC：半可信实体，具有海量存储空间和强大计算能力。

（4）KGC：可信实体，可根据系统要求生成公私密钥。

3.2 索引平衡二叉树

索引平衡二叉树结构如图2 所示，其中平衡二叉树每个结点由索引（index）、权值（height）、访问周期（cycle）以及左右指针域5 部分内容组成。

图2 索引平衡二叉树

每个数据块对应一个平衡二叉树结点，以数据块的唯一标号为权值构建平衡二叉树。结点中访问周期初始值为0，若在一定时间内（一般为一周）没有出现取用操作，则访问周期自增。

3.3 基于平衡二叉树的PPS 抽样

本方案的概率比例规模抽样将基于数据块的访问周期实现，具体过程如下文所述。

（1）生成排序表ST：先将平衡二叉树转化成一个链表，每个链表结点存有对应数据块的索引和访问周期，并依据访问周期对链表按照访问周期从小到大排序得到排序表ST。

（2）生成逻辑采样单元表：将最大访问周期fmax和周期间隔interv 作为输入，输出逻辑采样单元表LSUT，其中共包括该采样单元对应的访问周期范围、累计和以及该采样单元对应的范围3 项内容。

（3）采用PPS 抽取审计挑战数据块：假设需要抽取n×m个挑战数据块，先根据生成的逻辑采样单元表根据PPS 规则抽取n个逻辑采样单元，然后在其中各随机选取m个数据块。

3.4 低频动态数据完整性审计协议

本文采用格密码构建了一个基于身份的远程数据完整性检查协议，详细内容如下文所述。

（1）系统初始化（Setup(n)）：首先，设置安全参数n，整数m，大质数q，实数β，哈希函数H，H1，H2，H3；其次，密钥生成中心生成一个矩阵A和(A)上的一组短的格基TA；最后，生成一个矩阵Q和一组(Q)上的短的格基TQ。其中，系统参数param=(A,Q,H,H1,H2,H3)，用户主密钥msk=TA。

（2）用户身份id生成密钥（KeyExtract(param,msk,id)）：首先，计算B=AR-1，其 中R=H(id)；其次，运行算法NewBasisDel(A,R,TA,s)生成Tid，Tid是(B)的一个格基，s是一个高斯采样参数；最后，输出skid=Tid作为数据所有者的私钥发送给RSU。

（3）生成数据块签名（SignGen(param,τ,skid,M,id)）：首先，需要将文件M分为l块，令数据文件M的标签为τ∈{0,1}*；其次，计算αj=H3(B||τ||j)∈，对于每个ui，计算λi=H1(τ||i)+Qui，计算内部产品hi=(hi1,…,hin)T，RSU 运行SamplePre来得到文件块的签名ei=SamplePre(B,Tid,hi,σ)；最后，RSU 将文件M={u1,…,ul}和相关签名Φ=(e1,…,el)发送给数据中心，用户将文件从本地删除。

（4）生成挑战信息（challenge(τ,M)）：RSU采用PPS 从全集{1,2,…,l} 选择元素索引集合I={i}i∈[1,l]I。对于每个元素i，RSU 选择一个随机值ci，并生成chal={τ,i,ci}i∈I作为挑战信息，RSU 将挑战信息发送给数据中心。

（5）生成证明（Proofcheck(param,chal,M,Φ,TQ,τ)）：一旦收到来自RSU的挑战信息chal，数据中心首先选择数据块{ui}i∈I以及相关签名{ei}i∈I计算签名证明和数据证明；然后在返回证明前对数据证明进行盲化，计算，其中uc∈，计算，其中ec∈，选择随机向量并运行算法SamplePre(Q,TQ,w,σ)生成w的签名ξ，计算和，其中；最后，数据中心将证明proof=(τ,uc',ec,w)发送给RSU。

（6）证据检查算法（Proofcheck(param,proof,chal,id,τ)）：一旦收到来自数据中心的证明proof=(τ,,ec,w)，RSU 计 算R=H(id) 和B=AR-1，计 算αj(j≤n)，αj=H3(B||τ||j)，让C=(α1,…,αn)，RSU计算；然后计算；最后RSU 检查如果两个等式成立，则RSU 接受该证明，否则该证明是非法的。

4 性能分析

首先在SIS 假设下验证方案的隐私保护特性，然后通过模拟实验分析方案性能。

4.1 安全性能分析

定理1：在签名不可伪造以及SIS 难题假设下本方案实现了数据隐私保护。

证明：外部攻击者截取证明proof=(τ,uc',ec,w)后，不能恢复M={u1,…,ul}中的任何数据块。假设外部攻击者试图恢复M={u1,…,ul}中的任何数据块。聚合信息选择一个随机向量，然后运行算法SamlePre(Q,TQ,w,σ)来生成w的签名ξ，然后计算=uc+ξH2(w)和。因为签名不可伪造以及SISq,m,n,β困难假设，外部攻击者并不知道数据中心的私钥，因此外部攻击者不可能恢复原始文件块。

4.2 计算开销分析

该实验运行在4 GB 内存和2 个处理器核心Ubuntu20.04 虚拟机上，实验采用数论库（Number Theory Library，NTL）11.4.4 版本。实验结果5 次取平均。

本文在仿真环境下测试了所提方案计算签名的开销，图3 为计算签名分别所需的时间花销。实验结果表明，随着数据块数的增加，签名总时间大致呈线性增长。

图3 计算签名开销

图4 展示了挑战数据块所需的时间花销，与挑战块数基本上呈正比，由此可见格密码方案因为不存在配对、求幂等耗时运算而具有较高的效率。

图4 验证签名开销

5 结语

现有车联网场景下，车辆将车载数据发送到数据中心后数据完整性无法得到保障。基于该问题，本文提出了一种面向低频数据的动态完整性审计方案。该方案结合数据块的访问周期作为参考信息，采用PPS 来选择挑战数据块，从而提高审计效率，并基于格密码设计使方案具有抗量子特性。最后，通过实验验证了本方案具有安全性和有效性。