可验证的大规模矩阵满秩分解的安全外包

杜志强，郑 东，赵庆兰

（西安邮电大学网络空间安全学院，西安 710121）

（*通信作者电子邮箱zhaoqinglan@foxmail.com）

0 引言

随着科技的不断发展，基于云的服务在人们的生活中也越来越普及，如物联网、医疗数据，因此，产生数据的规模也越来越大。对于资源受限的用户来说，自己购买设备处理这些数据是不太现实的，因为购买和维护设备都需要大量的资金，是一个巨大的负担，所以为了经济的需求，资源受限的用户可以将庞大的数据存储在云上，或者将复杂度高的计算外包给云［1-2］。这种模式以其方便快捷、价格低廉、可扩展性等优势，给社会带来巨大的变革，但是，云带来便利的同时，也会带来一些安全性问题［3］：一方面，由于竞争者的利益输送，云可能返回给用户一个恶意的值，或者将计算结果泄露给竞争者；另一方面，为了节省开销，云可能会返回给用户一个任意的值；此外，云计算必须大大减少用户自身的开销，所以，方案必须是安全有效和可验证的。

矩阵的满秩分解作为基本的线性代数和矩阵理论问题，在学术和工程方面有许多应用，比如广义逆求解、最小二乘解的计算、超广义投影分析等。通常进行满秩分解采用的方法是使用高斯消去法推导出原始矩阵的行阶梯型［4］。假设一个m×n的矩阵A的秩为r，那么高斯消去法的时间复杂度为O(mnrw-2)［5］，其中w代表矩阵乘法的指数。目前，当采用Williams算法［6］时，w最小，w=2.373，所以满秩分解的最低时间复杂度是O(mnr0.373)。然而，在如今数据规模呈现爆炸性增长的时代，资源受限的用户是无法进行本地计算的。所以，利用云计算将是一种有效的方法。

关于外包大规模计算的研究有很多，研究领域主要集中在科学计算领域和密码学领域。在科学计算领域，主要是对大规模矩阵运算的外包。2001 年，Atallah 等［7］首先提出了科学计算问题的外包框架，该方案研究了矩阵求逆、矩阵乘法等问题的安全外包；但仅仅考虑到隐私性和安全性，而没有考虑到高效性和可验证性。2013 年和2014 年，Lei 等［8-9］先后提出了矩阵求逆、矩阵乘法的外包方案，该方案构造了新的置换矩阵来进行加解密，但这样的置换矩阵无法保护零元素数目的安全。2015年，Lei等［10］继续设计了一个矩阵满秩分解的外包方案，存在的问题是不仅没有保护零元素数目的安全，而且不具备可验证性。2016 年，Zhou 等［11］研究了矩阵的特征值分解和奇异值分解（Singular Value Decomposition，SVD）的外包，但该方案仍然存在零元素泄漏的问题。2017 年，Zhou 等［12］提出了外包线性回归问题的方案，保护了零元素的安全。同年，Luo 等［13］研究了外包矩阵的正交三角（QR）分解和三角（Lower-Upper，LU）分解的问题，该方案中用户需要和云进行多次交互。2019 年，Zhang 等［14］利用有限域上的幺模矩阵进行矩阵乘法、矩阵求逆、行列式的外包，解决了之前的方案中存在的零元素泄漏的问题，但对矩阵的处理也限制在了有限域。

在密码学领域，外包主要集中在模幂和模逆两个方面：2015 年，Xiang 等［15］分别针对单模幂运算和多模幂运算设计了两种外包方案，安全性较之前有了提高，但是降低了效率；2019年，Tian等［16］巧妙地利用幺模矩阵的性质，设计了模逆运算的安全外包，与之前的方案相比，将云的数量从两个降到了一个。所以目前为止，关于安全外包满秩分解仍然是一个开放的问题。

本文的主要工作如下：

1）对于需要保护矩阵零元素数目的安全和对云返回结果进行验证的问题，提出了一个安全可验证的矩阵满秩分解的外包方案。

2）协议分析证明方案是正确、安全、高效和可验证的。

3）计算出加密矩阵的熵，证明了方案可以盲化原始矩阵中零元素的数目，并且实验证明方案具有较高的效率。

1 问题描述

1.1 系统模型

系统模型如图1所示，资源受限的用户将大规模矩阵A的满秩分解问题外包到资源丰富的云上进行求解。假设云是恶意的，所以为保护用户的输入输出隐私，用户利用密钥K将原始矩阵加密为X，然后发送给云。在对云返回的结果解密之前，必须对结果进行验证：如果验证通过，则继续解密；否则，直接拒绝。

图1 系统模型Fig.1 System model

1.2 设计目标

本文设计的目标包括4 点：正确性、安全性、高效性和可验证性。

正确性 如果云和用户都诚实地执行了方案，那么用户最终可以得到正确的结果。

安全性 设计的方案必须可以有效地保护用户的输入输出隐私。

高效性 用户运行外包算法的时间要远远小于本地计算满秩分解的时间。

可验证性 方案必须具备验证云返回结果正确性的能力。

2 预备知识

2.1 相关引理

引理1［4］有m×n的矩阵A，rank(A)=r。如果存在列满秩矩阵和行满秩矩阵，使得A=FG，则称上式为矩阵A的满秩分解。

引理2［17］Fm×r为列满秩矩阵的充分必要条件是存在左逆Wr×m，使得Wr×m*Fm×r=Ir。同理，Gr×n是行满秩矩阵充分必要条件是存在右逆Rn×r，使得Gr×n*Rn×r=Ir。

引理3［17］设A=Am×n，则rank(A)=r的充分必要条件是存在行满秩矩阵Pr×n和列满秩矩阵Qm×r，使得A=QP。

引理4［18］如果有m×m的可逆矩阵S1，和n×n的可逆矩 阵S2，则对于任意的m×n矩 阵A，有rank(S1A)=rank(AS2)=rank(S1AS2)。

引理5［19］Sherman-Morrison 公式：定义P是可逆矩阵，u、v是列向量。如果(1+vTP-1u) ≠0，则(P+uvT)-1=P-1-

2.2 置换

置换在群理论和组合学应用广泛。根据柯西两行表示法，可以写成如下形式：

其中：π(i)=bi，并且bi∈[1，n]且互不相等。π-1表示置换的逆置换。

定义克罗内克函数

给定集合{α1，α2，…，αm}←κα和{β1，β2，…，βn}←κβ，然后根据生成的置换π1、π2，定义置换矩阵［8］P1(i，j)=同时，也可以得到置换矩阵的逆。

2.3 加密矩阵

本文利用Sherman-Morrison 公式构造一种稠密的加密矩阵S1，且这个矩阵可逆。操作如下：

1）首先根据文献［8］，约束集合{α1，α2，…，αm}←κα都大于0，随后生成置换矩阵P1。

2）其次生成两个列向量u1、v1，保证列向量中的每个元素大于0。

3）生成S1=P1+由于取密钥空间κα的中的元素都大于零，则根据有其次，有u1(i) ＞0，v1(i) ＞0，所以根据Sherman-Morrison 公 式，只 要有同理，构造加密矩阵

3 可验证的矩阵满秩分解的安全外包

3.1 方案概述

假设外包矩阵Am×n的满秩分解，求解出列满秩矩阵B和行满秩矩阵C，使其满足A=BC。方案如下：用户首先根据2.3 节，构造出加密矩阵S1、S2、随后，对原始矩阵A进行加密，X=，最后将X发送给云。云在得到加密矩阵X后，首先对X进行满秩分解，得到列满秩矩阵Fm×r和行满秩矩阵Gr×n。接下来继续计算Fm×r的左逆Wr×m和Gr×n的右逆Rn×r，最后将4 个矩阵返回给用户。在验证阶段需要验证两部分内容：1）Fm×r是否为列满秩矩阵，Gr×n是否为行满秩矩阵；2）验证等式X=Fm×r×Gr×n是否成立。和文献［10］一样，采用矩阵向量乘法进行概率性验证。验证通过则用户进行解密。

3.2 具体的算法

外包矩阵Am×n满秩分解的具体算法包含以下5个步骤：

1）密钥生成。

输入 安全参数λ。

输出 密钥K：{α1，α2…，αm}、{β1，β2…，βn}和4 个列向量u1、u2、v1、v2。

用户定义密钥空间κα、κβ，约束密钥空间中的数据都是大于0 的。生成集合{α1，α2，…，αm}←κα，{β1，β2，…，βn}←κβ。同时产生m×1的密钥列向量u1、v1，n×1的密钥列向量u2、v2。约束列向量中的元素都是大于0的。

2）加密。

输入A和密钥K。

输出 加密的矩阵X。

用户首先生成m×m置换矩阵和n×n的置换矩阵构造出密钥矩阵：

随后根据定理1 高效的计算出加密矩阵X=，最后用户将加密矩阵发送给云。

3）云计算。

输入X。

输出F，G，W，R。

云在接收到用户发送来的加密矩阵X后，首先进行满秩分解，得到两个矩阵Fm×r，Gr×n。随后计算矩阵Fm×r的左逆Wr×m和矩阵Gr×n的右逆Rn×r，并将这4 个矩阵F，G，W，R返回给用户。

4）验证。

输入F，G，W，R。

输出 0/1。

首先用户验证矩阵Fm×r和矩阵Gr×n是否是列满秩和行满秩矩阵。操作如下：

用户随机生成l组r× 1维的列向量t，计算：

如果q1和q2是零向量，则继续；否则返回0，表示结果错误。

随后，用户随机生成l组n× 1 维的列向量d，计算Fm×r×Gr×n×dn×1-Xm×n×dn×1=q3。如果q3是零向量，返回1，表示结果正确；否则返回0，表示结果错误。

5）解密。

输入F，G和密钥K。

输出B，C。

用户计算B=，C=GS2。

4 协议分析

4.1 协议证明

定理1加密过程和解密过程是高效的。

证明 在加密过程中

开销主要集中在矩阵与置换矩阵之间的计算或矩阵向量之间的计算。各部分的时间复杂度如下的时间复杂度 为O(mn)；的时间复杂度为O(5mn)；时间复杂度为O(3mn)的时间复杂度为O(7mn)。故加密的时间复杂度为O(16mn)。同理，解密的时间复杂度为O(8mn)。

定理2外包方案满足正确性、安全性、高效性和可验证性。

证明 1）外包方案满足正确性。

利用两个可逆矩阵S1、S2将矩阵A加密成X=随后云返回X的满秩分解为：

所 以F=S1B，G=可以推导出C=GS2。而且，通过引理4，有rank(X)=r。此外

故在解密完成后，B是列满秩矩阵和C是行满秩矩阵且A=BC。由引理1 和引理3 得，B、C一定是秩为r的矩阵A的满秩分解。

2）外包方案满足安全性。

当m，n非常大时，攻击者不可能获取用户的输入输出隐私。

3）外包方案满足高效性。

由于云是具备大量资源的实体，所以不考虑云的开销。从定理1 得，加密的时间复杂度为O(16mn)，解密的时间复杂度为O(8mn)。同时，密钥生成的时间复杂度为O(3(m+n))，验证的时间复杂度为O(3mrl) +O(3nrl) +O(mnl)。由于l远小于m、n，所以用户所需的总的时间复杂度近似为O(mn) +O(mr) +O(nr)。而文献［10］的时间复杂度也和本方案一样，也为O(mn) +O(mr) +O(nr)。此外，由于用户本地计算满秩分解的时间复杂度为O(mnr0.373)。O(mnr0.373)远大于O(mn) +O(mr) +O(nr)。所以，方案是高效的。

4）外包方案满足可验证性。

方案的验证分为两步：第一步是验证云返回的F，G是否为行满秩矩阵和列满秩矩阵。这步是非常有必要的，因为云有可能返回给用户任意两个满足X=FG的矩阵F，G。所以除了让云计算X的满秩分解外，也让云计算出F的左逆W和G的右逆R。这是因为从引理2得，矩阵存在左逆则一定是列满秩矩阵；同理，存在右逆一定是行满秩矩阵。因此，如果成功验证F是列满秩矩阵和G是行满秩矩阵之后，再继续第二步验证X=FG是否相等。这里的验证都是通过矩阵向量乘法进行的概率性验证，成功的概率为

4.2 加密矩阵的熵

在信息论中，香农提出熵是信息不确定度的度量，可用于进行安全性评估。通过一组实验来测量加密矩阵的熵，证明方案确实可以保护矩阵零元素的安全，并与文献［10］算法进行了比较。方便起见，认为原始矩阵的维度是512 × 512，矩阵中非0元素的密度从0.1增加到1。

实验结果如图2 所示，本文算法的熵恒定为18。这说明在本文的加密矩阵中，每个元素都不相同，盲化了零元素的数目。理由如下：假设在加密矩阵中，每个元素都不相同，不存在重复的零元素，则每个元素出现的概率均为p(xi)=所以根据熵的计算公式：

图2 加密矩阵的熵Fig.2 Entropy of encryption matrix

计算出加密矩阵的熵。如下：

计算得到熵为18，与实验结果相同，说明方案保护了零元素数目的安全。而在文献［10］算法中，熵的大小是随着矩阵的密度的增加而递增，因此不能保护零元素的安全。

5 实验仿真

本章对本文方案进行仿真。仿真环境是：Inter Core i7，1.8 GHz CPU，4 GB RAM，Matlab 2015a。方便起见，假设原始矩阵的维度为n×n。在实验中，用户计算和云计算是在同一台电脑进行，这样可以忽略用户端和云端之间的通信延迟，不考虑云计算时间，并且定义toriginal为用户本地完成满秩分解所需要的时间，tclient为用户运行算法所需要的时间，即在密钥生成、加密、验证、解密这4 个阶段总的时间。speedup=toriginal/tclient，表示加速比，当这个值大于1时，表示算法有效，并且这个值越大，说明用户运行算法所能得到的收益越高。实验结果如表1所示。

表1 不同维度下各阶段的运行时间 单位：sTab.1 Running time of each stage in different dimension unit：s

实验结果表明，当矩阵是1 000×1 000 的方阵时，用户本地计算矩阵满秩分解的时间为14.278 5 s，而如果采用设计的外包协议，所需要的时间仅为0.183 8 s。因此，外包矩阵满秩分解可以得到77.678 5 倍的效率，说明方案确实可以有效地节省用户满秩分解的时间。而且从表1 的数据可以看出，当矩阵的规模越来越大时，随着加速比的增加，用户选择外包时得到的效率也越来越高。所以，实验结果体现了方案的高效性。

6 结语

本文利用Sherman-Morrison等式和矩阵的伪逆的性质，提出了一个安全有效、可验证的外包矩阵满秩分解的方案。方案不仅对原始矩阵中零元素的数目进行了保护，而且对云返回的结果进行了验证。通过协议分析和实验仿真证明了方案具有正确、安全、高效、可验证的性质。本文的验证算法是概率性的验证算法。接下来，将引入公共验证的性质对外包问题进行重点研究。