云存储为海量数据的存储提供了可能。基于网络编码的云存储与其他的云存储方式相比，维持相同的冗余水平具有较小的修复开销[1]，但是如何保证存储数据的完整性是基于网络编码云存储面临的一个重要挑战。
一般的云存储数据完整性校验方案，由用户生成数据块的消息认证码，然后与数据块一起上传到存储节点，当用户获取数据块时，同时得到相应的消息认证码，可以完成完整性的认证[2, 3, 4, 5]。这种验证方案中，数据块与消息认证码对于存储节点而言是一个整体，均被看作数据。由于一般云存储中采用直接复制或纠删码来实现数据的冗余存储[6]，当数据出现损坏时，直接可以进行数据恢复，因此数据块和消息认证码可以一起被恢复。但是在基于网络编码的云存储中，当数据发生损坏时，通过读取未损坏的数据并进行线性组合运算完成数据恢复。若仍采用一般的消息认证码来进行完整性验证，在线性组合恢复数据的同时并不能恢复修复后数据的消息认证码。因此，一般的消息认证码完整性校验并不适用于基于网络编码云存储的数据完整性验证。
目前，相关研究提出了一些基于网络编码云存储的数据完整性校验方法。在文[7]的完整性校验方案中，验证节点保存原始数据块与随机向量的内积以及编码系数； 当验证节点对存储节点上的数据进行完整性校验时，首先向所有存储节点发送保存的随机向量，所有存储节点需计算自身存储编码块和随机向量的内积，并将运算结果返回给验证节点； 验证节点将本地保存的编码系数，与保存的原始数据块与随机向量的内积值做乘运算，并将运算结果与存储节点返回的结果对比，完成校验。该方案由于在验证时只需向验证节点发送编码块和原始数据块的内积，从而可以节省一定的通信开销，但是该验证方法无法阻止存储节点故意隐藏错误。
文[8]则通过下载每个编码块的指定字节和全部编码系数，将指定字节组成的列向量与编码系数矩阵的所有列向量一起组成新的矩阵，通过验证新矩阵的秩和编码系数矩阵的秩是否相同来完成对数据块完整性的校验。该方案在验证时，无法阻止存储节点在多次验证中递交相同的编码块以隐藏错误目的的行为，且该方案若要验证所有编码块的完整性，需下载所有数据，这将带来很大的通信开销。
文[9, 10]提出了基于同态MAC的完整性验证方案。与一般的消息验证码方案不同的是，同态MAC的基本特性是，在线性组合恢复数据的同时能恢复出修复后数据的同态MAC。在文[9]的同态MAC校验方案中，用户通过每个数据块生成验证同态MAC，在对多个数据块进行校验时，支持将多个编码块线性组合并一起验证。在文[10]提出的NC-Audit验证方案中，将编码块及相应的编码系数向量一起看成一个数据块，并为该数据块生成同态MAC； 在验证时，存储节点只需向验证节点发送编码块部分和同态MAC，验证节点在收到的编码块后，添加上自身存储的相应的编码系数，并利用验证算法完成验证。该方案可以有效克服存储节点故意隐藏错误的问题。另外，NC-Audit方案中，通过引入独立的第3方验证节点(third party auditor,TPA)来完成数据的完整性验证工作，这可以减轻用户的负担。
通过对NC-Audit方案分析后发现，该方案虽然在目前的基于网络编码云存储数据完整性校验方案中具有较好的整体性能，但该方案计算开销较大，验证过程中安全性弱，对存储节点的计算能力要求高。针对以上问题，本文提出了基于零空间的网络编码云存储数据完整性校验方案--NS-NCCS (null space for network coding based cloud storage)。该方案首先计算出原始信息的零空间，利用零空间生成验证向量，并将验证向量发送给独立的第3方验证节点完成数据验证。该方案在完整性验证过程中可以显著降低漏检率，有效防止验证节点反推出原始信息，可以节省计算开销以及有效支持数据修复。
1 NC-Audit方案分析为了便于比较，本节首先介绍NC-Audit方案的数据存储及完整性验证过程，然后分析该方案在完整性验证过程中存在的问题。
NC-Audit方案采用的存储场景是(n,k)存储场景，即有n个存储节点，每个存储节点存放θ个编码块，每个编码块用m个(有限域Fq)字符表示，任取k个节点的编码块可以恢复出全部原始信息。
1.1 NC-Audit方案介绍图1给出了NC-Audit方案的存储验证过程，具体的存储验证过程如下。其中步骤1-5表示存储过程，步骤6-10表示验证过程。
|
| 图1 NC-Audit方案的存储验证过程 |
1) 用户将原始信息等分为k个原始数据块，分别表示为 b i (1≤i≤k)。
2) 用户生成两个密钥k1和k2。
3) 在原始数据块后添加k阶单位向量，添加单位向量后的原始数据块表示为 B i (1≤i≤k)，利用k1为之生成同态MAC t i ，利用k1、 k2生成标记向量( p1,p2,…,p m )。 $$\eqalign{ & {B_i} = ({b_i},\overbrace {\underbrace {0, \cdots ,0,1,}_i0, \cdots ,0}^k), \cr & {t_i} = MAC({k_1},{B_i}), \cr & \bar r \leftarrow \left( {{F_1}\left( {{k_1},1} \right), \cdots ,{F_1}\left( {{k_1},m} \right)} \right), \cr & \overline {{p_i}} \leftarrow \left( {{F_2}\left( {{k_2},i,1} \right), \cdots ,{F_2}\left( {{k_2},i,m} \right)} \right). \cr} $$ 其中1≤i≤m。 $${p_i} \leftarrow \bar r\overline {{p_i}} ,l \le i \le m.$$
4) 选取编码系数矩阵${EM\left( {{e_i}} \right)}$ (1≤i≤nθ)，利用编码系数对 B i 进行线性编码，得到nθ个编码块。 $$\overline {{e_i}} = \left( {{e_i}|EM\left( {{e_i}} \right)} \right) = \sum\limits_{j = 1}^k {{\alpha _{i,j}}} {B_j}.$$ 其中： 1≤i≤nθ； e i 是数据部分； ${EM\left( {{e_i}} \right)}$是 e i 对应的编码系数向量； ai,j是 ${EM\left( {{e_i}} \right)}$中的元素，是从有限域中随机选取的。
显然，由于同态MAC的特点，编码运算后的MAC值依然是对应编码数据块的同态MAC值，表示为 T i 。 $${T_i} = \sum\limits_{j = 1}^k {{t_j}} ,1 \le i \le n\theta $$
5) 将( p1,p2,…,p m )、 k2、 ${EM\left( {{e_i}} \right)}$、 e i 及相应的同态MAC T i 上传到存储节点，每个存储节点存放θ个编码块及相应的编码系数向量； 将[${EM\left( {{e_i}} \right)}$ (1≤i≤nθ)]和k1发送给第3方验证节点TPA保存。
6) 在对某存储节点进行验证时，TPA首先向该存储节点发送验证请求chal。
chal={(j,u j),1≤j≤θ}.
7) 存储节点收到chal后，利用chal中的 uj 对相应序号的编码块及同态MAC值进行线性组合运算，分别得到组合数据块 e和对应的同态 MAC T。 $$e = \sum\limits_{j = 1}^\theta {{u_j}} {e_j},T = \sum\limits_{j = 1}^\theta {{u_j}} {T_j}$$
然后利用k2生成加密向量 L=(L1,…,L m )，对 e进行线性加密，得到加密数据块c。同时，对(p1,p2,…,p m )进行组合，得到 p。 $$\overline {{p_i}} \leftarrow \left( {{F_2}\left( {{k_2},i,1} \right), \cdots ,{F_2}\left( {{k_2},i,m} \right)} \right).$$ 其中1≤i≤m。 $$\eqalign{ & \beta \leftarrow \left( {{F_3}\left( {{k_2},1} \right), \cdots ,{F_3}\left( {{k_2},m} \right)} \right), \cr & {L_i} \leftarrow \beta \overline {{p_i}} ,l \le i \le m, \cr & c \leftarrow e + L,p \leftarrow \sum\limits_{i = 1}^m {{\beta _i}{p_i}} . \cr} $$
8) 将c、 T、 p一起发送给 TPA。
9) TPA收到存储节点发送的验证信息后，从保存的 [EM( e i )](1≤i≤nθ)中得到相应的 EM( e i )，利用已获取的信息重新生成验证数据块 e的同态 MAC，并与存储节点发送的同态MAC进行比对完成验证，具体验证过程如下。 $$\eqalign{ & EM\left( e \right) = \sum\limits_{j = 1}^\theta {{u_j}} EM\left( {{e_j}} \right), \cr & C = \left( {c|EM\left( e \right)} \right),Verify\left( {{k_i},C,t + p} \right). \cr} $$
10) TPA向用户发送验证结果。当比对结果一致时，说明完整性没有发生改变； 反之，说明完整性发生改变。
1.2 NC-Audit方案安全性及计算开销分析 1.2.1 安全性分析NC-Audit方案利用密钥k1、 k2对存储节点发送的组合数据块进行加密，可以有效保护数据在发送过程中的安全性，但是TPA由于验证需要必须保存所有的编码系数，当TPA得到足够多的组合数据块后，可能会与存储节点合作发起合谋攻击，即利用存储节点的加密密钥和自身存储的编码系数，解码得到原始数据，导致用户数据隐私的泄漏。因此，NC-Audit方案虽然提高了数据传输时的安全性，但是仍存在隐私泄露的风险。
另外，文[10, 11]论证了应用该方案时的漏检率，即数据在非正常改变情况下依然能通过完整性验证的概率。当组合数据块发生非正常改变时，漏检率小于等于2/q，数据非正常改变是指在内在或者外在条件下引起的数据丢失、篡改、删除等。
1.2.2 计算开销分析NC-Audit方案通过对数据进行加密，在一定程度上提高了验证过程中的安全性，但是加密过程带来了较大的计算开销。文[11]分析了该方法在验证过程中的计算开销，主要包括： 生成组合数据块 e和同态 MAC T，加密过程以及 TPA验证时所带来的计算开销。在分析计算开销时，为了比较的公平性，以验证 n个存储节点所有编码块的完整性的计算开销为比较依据。在计算开销中，乘运算占绝大多数，因此，主要分析乘运算的次数。
1) 生成组合数据块 e和同态 MAC T需要做乘运算的次数是 nθ(m+k+1)；
2) 加密过程需要做乘运算的次数是n(2m2+m)；
3) TPA验证时需要做乘运算的次数是n(m+k)。
因此，NC-Audit方案所需总的乘运算次数是n(m+k)+nθ(m+k+1)+n(2m2+m)。
2 NS-NCCS方案 2.1 方案的基本思想本文提出了基于零空间的网络编码云存储数据完整性校验方案--NS-NCCS。该方案利用原始数据块矩阵的零空间生成验证向量，在验证时通过判断递交的组合数据块是否与验证向量正交来完成验证。方案中没有采用同态MAC技术，且TPA无 需保存编码系数，从而减少了计算同态MAC以及加密组合数据块带来的计算开销，也避免了TPA保存全部编码系数带来的数据隐私泄露风险。
定义1和性质1分别给出零空间定义及其性质。
定义1 对于有限域中的矩阵X，矩阵X的零空间是方程X·u T =0的所有解向量 u组成的集合。
性质1 矩阵X中的任一行向量或者多个行向量的任一线性组合都与其零空间正交。
2.2 安全模型与相关符号定义 2.2.1 安全模型本文采用文[10, 12, 13]中描述的安全模型。假设存储节点是半信任(semi-trusted)存储节点，即存储节点会执行规定的协议，但是为了自身利益，可能会故意删除自身存储的很少读取的数据，故意隐藏由于内在或者外在条件引起的数据损坏，可能和恶意节点合作发起合谋攻击，获取用户隐私。假设TPA是独立可靠的，但有获取用户数据隐私的欲望。
完整性校验方案的安全性体现为应对以下3方面威胁的能力。
1) 漏检率。
数据在非正常修改情况下，依然能够通过完整性验证的概率。
2) 存储节点故意隐藏错误。
当TPA所要求验证的编码块中包括错误编码块时，存储节点在验证时故意不递交有错误的编码块，而是用其他正常编码块替代作为应答，以达到逃避完整性验证的目的。
3) 隐私泄露。
即验证过程中TPA获取数据信息。
2.2.2 符号定义为了便于表示，对文中相关变量进行说明，如表1所示。
图2表示了NS-NCCS方案的存储与验证过程。其中步骤1-4表示存储过程，步骤5-9表示验证过程。
|
| 图2 NS-NCCS方案存储验证过程图 |
1) 用户首先将原始数据等分为k块，每块用m个Fq字符表示，记为 b i (1≤i≤k)，在 b i 后添加标记部分，标记部分由d位二进制字符组成的向量表示，记为 t i (1≤i≤k)。添加标记部分后的 b i记为 B i。
B i=( b i| t i).
2) 随机生成M个m+d阶的向量，分别记为 r i (1≤i≤M)，要求 r i与 B i是相互独立的，则矩阵 A 和其零空间的表示如下：
A =[B 1,B 2,…，B k,r 1,r 2,…，r M]T，
∏ 1 / A ∶ Z =[Z 1,…,Zm+d－k]← A · Z i=0.
将零空间向量进行随机线性组合即可生成验证向量 NS，生成的 β个线性无关的向量 NS组成验证矩阵 K。 $$NS = \sum\limits_{i = 1}^{m + d - k} {{c_i}{Z_i}} .$$ 其中 c i是有限域Fq里的随机非0元素。
3) 生成验证向量 NS之后，用户对 B i 进行线性网络编码，生成nθ个编码块。 $$\overline {{e_i}} = \left( {{e_i}|{T_i}} \right) = \sum\limits_{j = 1}^k {{\alpha _{i,j}}} {B_j}.$$
其中： 1≤i≤nθ； e i是数据部分； T i 是 e i对应的标记部分； ai,j是编码系数向量中的元素，是从有限域中随机选取的。
4) 用户将每个编码块的数据部分 e i及其对应的编码系数向量上传给存储节点，每个存储节点上传θ个，将编码块的标记部分 T i和验证向量 NS发送到 TPA。
5) TPA定期对所有存储节点存放的数据进行完整性校验。在对某个存储节点的数据进行完整性校验时，TPA首先向该存储节点发送验证请求chal。
chal={(j,u j),1≤j≤θ}.
其中： j表示要验证存储节点的编码块序号，uj 表示j号编码块的组合系数。
6) 存储节点收到chal后，首先利用chal中的组合系数对所要验证的编码块的数据部分进行线性组合，得到组合数据块 e。 $$e = \sum\limits_{j = 1}^\theta {{u_j}{e_j}} $$
7) 存储节点将组合数据块 e发送给 TPA。
8) TPA收到存储节点发送的组合数据块 e之后，首先利用uj 对所要验证编码块的标记部分进行组合，得到组合后的标记部分 T，然后将T添加在e后面，得到验证信息E，最后E和验证向量 NS相乘得到 R。 $$\eqalign{ & T = \sum\limits_{j = 1}^\theta {{u_j}{T_j}} \cr & E = \left( {e|T} \right),R = NSE. \cr} $$
9) TPA向用户发验证结果，若 R=0，则向用户返回0，表示数据完整性没有改变，否则返回1，表示数据完整性发生改变。
3 性能分析与比较 3.1 安全性分析与比较根据NS-NCCS方案的安全模型，本小节将从以下3方面入手，分析并比较NS-NCCS方案的安全性。
1) 漏检率。
定理1 在有限域Fq中，假设β×γ阶矩阵 K 是由 β个线性独立的γ维向量组成的，则任意一个随机的γ维向量w与矩阵 K正交的概率为 1/qβ。
定理2 NS-NCCS方案中，TPA上存储了 β个 线性无关的 NS验证向量，组成验证矩阵 K。对于一个非正常的组合数据块e，e能通过验证矩阵K完整性验证的概率为 1/qβ。
证明 在NS-NCCS方案中，矩阵 K是一个 β×(m+d)阶矩阵，非正常的组合数据块 e要通过验证矩阵K的完整性验证，必须满足e与验证矩阵K正交，即K·e T =0。由定理1知，非正常的组合数据块 e与矩阵K正交的概率为 1/qβ，即非正常的组合数据块 e通过验证矩阵验证的概率为 1/qβ。
2) 存储节点故意隐藏错误。
在NS-NCCS方案中，为防止存储节点故意隐藏错误，用户为原始数据块添加一个标记部分，标记部分只存放在TPA处。在进行完整性校验时，若存储节点没有按照TPA要求递交相应的组合编码块，而自身又无法伪造标记部分，便无法通过验证向量 NS的验证，从而可以达到防止存储节点故意隐藏错误的目的。
3) 隐私泄露。
在NS-NCCS方案中，用户向TPA发送的是验证向量 NS 和标记部分，存储节点向TPA发送的是组合的数据块，与NC-Audit完整性校验方案不同的是，TPA在验证时并不需要编码系数，仅仅通过标记部分和组合编码块，TPA无法获取用户的任何原始信息。
另外，为防止TPA利用验证向量 NS反推出原始信息，NS-NCCS方案在计算验证向量 NS时，在原始信息矩阵中添加 M个随机向量，因此，TPA也无法通过验证向量 NS获取用户的隐私。
两种完整性校验方案安全性的综合比较如表2所示。
| 项目 | NS-NCCS | NC-Audit | |
| β=1 | β=10 | ||
| 漏检率 | 3.9×10-3 | 8.3×10-25 | 7.8×10-3 |
| 抵抗故意隐藏错误威胁 | 是 | 是 | 是 |
| 抵抗隐私泄露威胁 | 是 | 是 | 否 |
表2说明，NS-NCCS方案在验证过程中具有更小的漏检率，能更好地防止数据隐私泄露。
3.2 计算开销分析与比较NS-NCCS方案验证过程中的计算开销主要包括存储节点生成组合编码块 e、 TPA 生成 e对应的 标记部分T以及E和验证向量 NS相乘所带来的计算开销。
1) 存储节点生成组合编码块 e 需要做乘运算的次数是nθm；
2) TPA生成 e对应的标记部分T需要做乘运算次数是 nθd；
3) TPA用 E和验证向量 NS相乘需要做乘运算的次数是 nβ(m+d)。
因此，NS-NCCS方案验证n个存储节点的全部编码块需要做乘运算的次数为n(θ+β)(m+d)。
表3和4中给出了两种方案在不同存储场景下，d=100时，对所有存储节点的全部编码块做完整性校验时，所需要做总的乘运算的次数。
| (n,k) | NC-Audit次数 | NS-NCCS 次数 | |
| β=1 | β=10 | ||
| (100，10) | 3.32×109 | 3.78×107 | 4.15×107 |
| (150，50) | 4.98×109 | 6.28×107 | 6.84×107 |
| (1 000，100) | 3.65×1010 | 3.74×109 | 3.77×109 |
由表3和4可以看出，在所列的不同存储场景下、 d=100时，NS-NCCS数据完整性校验方案在校验过程中都具有较少的乘运算次数，且当m越大，即编码块的大小越大时，NS-NCCS方案在节省计算开销方面的优势越明显。
| (n,k) | NC-Audit次数 | NS-NCCS 次数 | |
| β=1 | β=10 | ||
| (100，10) | 8.80×1014 | 1.91×1010 | 2.10×1010 |
| (150，50) | 1.32×1015 | 3.18×1010 | 3.46×1010 |
| (1 000，100) | 8.80×1015 | 1.89×1012 | 1.91×1012 |
为真实比较两种方案在完整性校验过程中的运算开销，在MATLAB7.0上模拟了NS-NCCS方案的完整性校验过程，模拟时采用与NC-Audit相同的分块方式，即将原始数据等分为500块，每块大小为4 kB，每个存储节点存放300个编码块，标记部分由100个字符表示(d=100)，模拟机器配置： 2.69 GHz CPU，1.96 GB RAM。表5给出了两种方案验证单个存储节点的完整性时，验证过程中存储节点和TPA所需的运行时间，运行时间为模拟运行2 000次的平均值。
通过分析表5发现，NS-NCCS方案即使在模拟设备运行速度远小于NC-Audit方案所使用模拟设备(2.8 GHz CPU，32 GB RAM)运行速度的情况下，其完整性验证过程中存储节点和TPA所需的运行时间都小于NC-Audit方案。
3.3 通信开销分析与比较NC-Audit方案在完整性验证过程中的通信开销主要指存储节点发送组合编码块、加密和验证所需的同态MAC等信息所带来的通信开销，而NS-NCCS方案在进行数据完整性校验时，存储节点只需发送组合数据块，无需发送其他任何信息，这可以节省一定的通信开销。因此，NS-NCCS方案的完整性校验方法可以进一步减少校验过程中的通信开销。
3.4 可支持修复性分析在NS-NCCS方案中，当用户收到TPA的完整性校验结果，发现某个节点的编码块无法通过完整性校验时，便会启动修复功能。与NC-Audit方案不同的是，由于NS-NCCS方案中的验证向量 NS 是利用原始数据块生成的，而修复过程只是利用原始数据块重新线性编码，原始信息没有发生任何变化，用户无需重新计算新的验证向量 NS。因此，NS-NCCS方案可以有效支持数据修复。
4 结 论本文提出了基于零空间的网络编码云存储完整性校验方案，该方案利用原始数据的零空间生成验证向量，通过判断存储节点递交的组合数据块是否与验证向量正交完成验证。分析与计算表明，与NC-Audit相比，该方案在完整性验证过程中可以显著降低漏检率，有效防止验证节点反推出原始信息，可以节省计算开销以及有效支持数据修复。
| [1] | Hu Y, Chen H C H, Lee P P C, et al. NCCloud: Applying network coding for the storage repair in a cloud-of-clouds [C]//USENIX FAST. 2012: 265 -272. |
| [2] | Shah M A, Swaminathan R, Baker M. Privacy-preserving audit and extraction of digital contents, HP Labs Technical Report No. HPL-2008-32 [R]. 2008. |
| [3] | Bowers K D, Juels A, Oprea A. Proofs of retrievability: Theory and implementation[C]//Proceedings of the 2009 ACM Workshop on Cloud Computing Security. ACM, 2009: 43-54. |
| [4] | Bowers K D, Juels A, Oprea A. HAIL: A high-availability and integrity layer for cloud storage [C]//Proceedings of the 16th ACM Conference on Computer and Communications Security. ACM, 2009: 187-198. |
| [5] | Wang C, Wang Q, Ren K, et al. Toward secure and dependable storage services in cloud computing [J]. IEEE Transactions on Services Computing, 2012, 5(2): 220-232. |
| [6] | Rodrigues R, Liskov B. High availability in DHTs: Erasure coding vs. replication [M]//Peer-to-Peer Systems IV. Springer Berlin Heidelberg, 2005: 226-239. |
| [7] | Dikaliotis T K, Dimakis A G, Ho T. Security in distributed storage systems by communicating a logarithmic number of bits [C]//2010 IEEE International Symposium on Information Theory Proceedings (ISIT). IEEE, 2010: 1948-1952. |
| [8] | Chen H C H, Lee P P C. Enabling data integrity protection in regenerating-coding-based cloud storage [C]//31st Symposium on Reliable Distributed Systems (SRDS). IEEE, 2012: 51-60. |
| [9] | Chen B, Curtmola R, Ateniese G, et al. Remote data checking for network coding-based distributed storage systems [C]//Proceedings of the 2010 ACM Workshop on Cloud Computing Security. ACM, 2010: 31-42. |
| [10] | Le A, Markopoulou A. NC-Audit: Auditing for network coding storage [C]//Network Coding (NetCod), 2012 International Symposium on. IEEE, 2012: 155-160. |
| [11] | Le A, Dimakis A G. Auditing for distributed storage systems, Cornell University Technical Report [R/OL]. http://arxiv.org/abs/1203.1730. |
| [12] | Wang C, Wang Q, Ren K, et al. Privacy-preserving public auditing for data storage security in cloud computing [C]//INFOCOM, 2010 Proceedings IEEE. San Diego, CA: IEEE, 2010. |
| [13] | Yu S C, Wang C, Ren K, et al. Achieving secure, scalable, and fine-grained data access control in cloud computing [C]//INFOCOM, 2010 Proceedings IEEE. San Diego, CA: IEEE, 2010. |
| [14] | Roman S. Advanced Linear Algebra (Second Edition) [M]. Springer, 2005. |
| [15] | Elias K, Li B C. Null keys: Limiting malicious attacks via null space properties of network coding [C]//INFOCOM, 2009 Proceedings IEEE. IEEE, 2009: 1224-1232. |