杜志强，郑 东，赵庆兰

（西安邮电大学网络空间安全学院，西安 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)。然而，在如今数据规模呈现爆炸性增长的时代，资源受限的用户是无法进行本地计算的。……