云辅助的安全高效非负矩阵分解算法

祁新雷,周 强,田呈亮

(1.西安邮电大学 研究生院,陕西 西安 710121;2.青岛大学 计算机科学技术学院,山东 青岛 266071)

非负矩阵分解[1](Non-negative Matrix Factorization,NMF)主要是把一个非负矩阵V∈m×n分解成两个规模更小的非负矩阵W∈m×r和H∈r×n,使得V≈WH。通过非负矩阵分解,可获得近似原始矩阵的低秩矩阵,使得数据的存储和处理更高效便捷,现已广泛应用在计算机视觉[2]、数据挖掘[3]、音频信号处理[4]和推荐系统[5]等众多领域。 然而,在大数据时代的实际应用中,非负矩阵分解涉及到的矩阵往往规模很大,导致非负矩阵分解算法消耗大量的计算资源[6-7]。例如,图像视频处理过程中产生的大小为60 000×60 000双精度矩阵占用存储空间高达20 G,而使用一台普通的笔记本电脑对一个8 000×4 000矩阵进行非负矩阵分解时,耗时将近10 min。因此,资源受限的用户很难在本地执行非负矩阵分解操作。

云计算提供对可配置计算资源共享池的按需网络访问。通过云计算服务,资源受限的用户可以通过按需付费方式将沉重的计算任务外包给云服务器,而不必购买昂贵的软硬件设备维持足够大的计算资源。然而,远程云服务器的不可信性给这种计算模式带来了许多安全挑战[8-9]。首先,云服务器可能对收到的数据好奇,而用户的外包数据可能包含用户的生物特征信息、医疗记录以及财产数据等敏感信息,这些敏感信息一旦泄露,将会给用户带来严重损失。其次,出于外部经济利益驱动,云服务器可能是懒惰的甚至是恶意的,这使得云服务器可能返回随机或故意伪造的结果欺骗用户。最后,一些意外事件,如软硬件故障或外部攻击也可能导致产生错误的计算结果。因此,设计保护用户数据隐私并可检测云服务恶意行为的高效外包计算算法具有重要的研究价值。

1992年,Chaum等[10]首次提出了“Wallet with Observers”概念,给出了一个在用户的计算机中安装一个安全硬件辅助用户计算的方案。此后,设计完备的安全外包算法成为科学和工程技术领域的研究热点[11]。根据当前研究目的不同,安全外包算法主要分为两个研究方向。第一个方向是致力于研究适用于任意运算的通用外包算法,聚焦于设计全同态加密(Fully Homomorphic Encryption,FHE)方案。Gentry[12]于2009年设计了第一个FHE方案,但由于实现全同态加密本身就涉及复杂的运算,导致方案效率很低,难以在实际工程应用部署。另一个方向是研究适用于特定计算任务的定制外包算法,例如,大规模矩阵运算[13-15]、大规模线性方程组的求解[16]、线性回归[17]、双线性对运算[18]、模指数运算[19-20]和模逆运算[21]等。尽管该领域的研究广泛,但对NMF的外包算法研究却鲜有涉及。2016年,Duan等[22]提出了一个实用的外包求解NMF算法,其采用两个置换矩阵对原始矩阵进行加密,利用NMF计算的迭代性质设计了一种单轮验证策略,理论和实验都证明了这种策略是非常高效的。但是,Pan等[7]发现基于置换矩阵的加密方法存在两个缺陷。第一,泄露了原始矩阵的元素信息。置换矩阵加密只会改变原始矩阵中元素的位置,并不会改变其大小,因而原始矩阵中的元素不会变,云服务器可以获得原始矩阵中元素的分布信息。第二,泄露了原始矩阵的聚类性质。云服务器计算出的结果只是真实结果的简单置换,从加密结果中可获得真实结果的聚类信息。因此,Pan等采用可逆稀疏矩阵进行加密策略,给出了可行的可逆稀疏矩阵构造方法,有效地保护了原始矩阵,但是并不能保护原始矩阵中零元素的数目和分布。

基于对上述研究成果存在的隐私泄露及消耗计算资源问题,拟提出一种基于单服务器的安全外包算法。首先通过随机矩阵填充对原始输入矩阵中元素的个数进行隐藏,然后使用随机置换和对角矩阵变换,盲化矩阵中的元素的数值和分布,以解决原始矩阵零元素的数目和分布信息不能保护的问题。同时,使用的置换矩阵与对角矩阵均为稀疏矩阵,从而降低本地端的加解密成本以及与云端的通信成本,使本地端获得可观的计算节省。

1 预备知识

1.1 非负矩阵分解

给定一个非负矩阵V∈m×n,其非负矩阵分解是指寻找两个非负矩阵W∈m×r和H∈r×n,使得V≈WH,其中r为分解因子,其同时小于m,n。V的每一列可以看作W中所有列向量的线性组合,即

Vi=WHi

式中：Vi为V的第i个列向量;Hi为H的第i个列向量。

1.2 代价函数

为了寻找V的近似非负矩阵分解形式,通常通过定义代价函数衡量结果的近似程度[23]。一般地,可使用两个非负矩阵A∈m×n和B∈m×n之间的一些距离度量构造这样的代价函数。常见的衡量方式是简单计算A和B之间欧式距离的平方,即

(1)

当且仅当A=B时,上式为0。

根据式(1),把NMF问题转化为优化问题

非负矩阵W和H中的每一个元素都要大于等于零,因此在实际应用中,会预先设定错误边界ε,即当

时,认为V≈WH。

求解非负矩阵分解问题的计算复杂度约为O(lmnr),其中l为算法中的迭代次数。在实际应用中,为达到精确的分解结果,迭代次数通常会设定的比较大。因此,当处理的矩阵规模较大时,非负矩阵分解问题的复杂度就会变得非常大,这时会给资源受限的用户造成沉重的计算负担,可将该任务外包给资源丰富的云服务器完成。

1.3 置换矩阵

集合{1,2,...,n}上的置换是指从该集合到自身的双射,置换通常用置换函数形式表示为

其中αi∈{1,2,…,n},也可以表示为

π(i)=αi,i=1,2,…,n

特别地,恒等置换为

对于变量i,j,克罗内克δ函数定义为

设In×n为一个n维的单位矩阵,则置换π对应的置换矩阵Mn×n,其第i行j列元素可表示为

Mi,j=Ii,jδπ(i),j,Mi,j∈{0,1}

(2)

式中,Iij为单位矩阵第i行j列元素。

生成随机置换的Fisher-Yates洗牌算法由Richard Durstenfeld于1964年提出[24],其伪代码如下。

算法1 Fisher-Yates洗牌算法输入：n个元素输出：随机打乱顺序的n个元素1.令π=In2.对i从n-1到1,执行3.随机选取j←{1,…,i}4.交换π(j) and π(i)

2 系统模型和设计目标

2.1 系统模型

安全外包算法的系统模型主要由资源受限的用户C和具有强大计算能力但是不可信的云服务器S两个实体组成。用户C拥有输入数据x,要完成大规模运算任务Φ受限于有限的计算能力,用户C意图通过把计算任务外包给云服务器S以完成计算。系统模型示意图如图1所示。

图1 系统模型

图1中,用户C先调用密钥生成算法得到私钥Ks,利用私钥Ks把真实输入数据x加密成为σx,再把盲化之后的数据σx和相关数据发送给云服务器S。云服务器S收到交付的计算任务Φ、输入数据σx及相关数据后便计算σv=Φ(σx),并将结果σv返回给用户C。最后,用户C首先验证σv的正确性,如果验证成功,则解密σv,将其恢复成真实结果y,否则输出⊥。

2.2 设计目标

完备的安全外包算法需要满足正确性、隐私性、可验证性和高效性等4个设计目标。

1)正确性。如果云服务器诚实地执行算法指定的计算任务,安全外包算法总能确保用户得到正确的计算结果。

2)隐私性。隐私性包括输入的隐私性和输出的隐私性,是指云服务器不能从用户交付的输入的盲化数据和自己计算得到的输出数据中,恢复出用户的真实输入和真实输出的相关信息。

3)α-可验证性。保证用户能以不可忽略的概率α检测出云服务器的恶意行为。

4)高效性。用户在使用安全外包算法时,本地用户加密、验证和解密的用时总开销要小于不使用外包算法单独计算的时间。

3 安全外包算法

3.1 问题描述及基本思想

V′=(VB)m×t

式中,t=p+n。

将盲化矩阵V″发送给云服务器,计算完毕后向用户返回结果,用户验证结果是否正确,如果正确,则恢复出真实输出结果,否则报告云服务器的恶意行为。

安全外包算法首先通过随机矩阵增扩原始矩阵,然后使用对角矩阵和置换矩阵先后对增扩后的矩阵进行加密,实现了对输入矩阵的彻底盲化,不仅盲化了矩阵中的非零元素,而且首次隐藏了矩阵中零元素的分布和数目,同时隐藏了原始矩阵的部分维数信息,使得安全性能大幅上升。

3.2 安全外包算法具体描述

安全外包主要包括密钥生成、加密、云计算以及验证和解密等4个子算法。

2)加密。对输入矩阵V∈m×n,首先使用随机矩阵B填充得到V′=(VB)m×t,然后使用对角矩阵和置换矩阵加密得到盲化矩阵

并将V″以及分解因子r发送给云服务器。

3)云计算。云服务器收到用户发送的数据后,执行非负矩阵分解算法,得到W″∈m×r,H″∈r×t,其中V″=W″H″。

4)验证和解密。对云服务器返回的W″和H″进行验证,若W″、H″均为非负矩阵且

否则,用户拒绝接收并报告云服务器的恶意行为。

3.3 算法理论分析

围绕设计目标,下面分别分析安全外包算法的正确性、隐私性、可验证性与高效性。

3.3.1 正确性分析

首先先给出几个引理。

引理1对V∈m×n,若P1∈{0,1}m×m和P2∈{0,1}n×n为置换矩阵,则

(P1V)i=(P1)iV

引理2对V∈m×n,若和为对角线元素大于1的对角矩阵且满足或那么

(D1V)i,j≥Vi,j

式中：(D1V)i,j为矩阵D1和矩阵V乘积的第i行j列元素;Vi,j为矩阵V的第i行j列元素。

而

定理1对任意有效输入V∈m×n,安全外包是正确的。

证明正确性意味着如果安全外包中云服务器是“诚实的”,那么用户最后将得到正确结果。

对于输入矩阵V∈m×n,通过随机矩阵、对角矩阵和以及置换矩阵P1∈{0,1}m×m和P2∈{0,1}t×t加密得到

式中,V′=(VB)m×t。

因此

而V′=(VB)m×t,于是有

则由引理1和引理2可得

即

3.3.2 隐私性分析

定理2对任意有效输入V∈m×n,安全外包能够保护用户输入信息V∈m×n和输出信息(分解结果)W、H的隐私。

证明对输入矩阵V∈m×n,通过随机矩阵对角矩阵和以及置换矩阵P1∈{0,1}m×m和P2∈{0,1}t×t加密得到其中V′=(VB)m×t。引入随机矩阵B增扩了原始矩阵,通过对角矩阵加密改变了增扩后的矩阵中元素的大小,实现了对原始矩阵中非零元素和部分维数信息的盲化,最后通过置换矩阵加密,打乱了增扩后的矩阵中元素的排列方式,实现了对原始矩阵中零元素数目分布的隐藏。云服务器获得盲化后的矩阵V″之后,由于B、D1、D2、P1和P2是保密的,因此由V″相关信息无法恢复出真实输入V∈m×n的信息,从而保护了输入数据的隐私性。云服务器通过盲化后的矩阵V″计算得到W′、H′,同样如果没有密钥B、D1、D2、P1和P2,也无法恢复或者获得真实输出W、H的相关信息,从而保护了输出数据的隐私。

3.3.3 可验证性分析

定理3对任意有效输入V∈m×n,安全外包满足1-可验证性。

证明对于输入矩阵V∈m×n,云服务器收到盲化矩阵V″∈m×n后,计算得到W′和H′。若计算错误,则验证条件W″、H′是非负矩阵且就不能满足。如果验证通过,由定理1可知,用户可通过计算得到

因此,云服务器的恶意行为总是能够以1的概率被发现,即安全外包满足1-可验证性。

3.3.4 高效性分析

定理4对任意有效输入矩阵V∈m×n,安全外包具有高效性。

证明在调用安全外包时,用户只需完成密钥生成、加密、验证和解密步骤。由于密钥生成阶段可以在预处理时完成,因此用户实际要完成加密、验证和解密。

在验证和解密阶段,用户验证W″、H″为非负矩阵且

是否成立,此时复杂度为O(mtr)。验证通过后要计算

此时复杂度为O(mr)。

综上,用户的计算复杂度为O(mtr),b

4 性能评估实验

为评估安全外包的实际性能,实验硬件配置为Intel(R) Core(TM) i5-3230M CPU、2.60 GHz和8 GB RAM。软件环境为Matlab R2016a。设tClient表示用户在调用外包算法时所花费的时间,即加密、验证和解密的时间总和,tCloud表示调用外包算法时云服务器花费的时间,tDirect表示用户本地直接计算所花费的时间。tDirect与tClient之间的比值是衡量外包算法效率的一项重要指标,比值越大,说明用户获得计算节省越多,算法效率越高。当固定r时,不同规模矩阵采用安全外包和不采用安全外包两种模式的时间开销对比如表1所示。

表1 固定r时两种模式的时间开销对比

由表1可以看出,矩阵的规模越大,tDirect与tClient比值越大,安全外包的优势就越明显,因此安全外包适用于大规模非负矩阵分解。

当固定(m,n,p)时,不同规模矩阵采用安全外包和不采用安全外包两种模式的时间开销对比如表2所示。

表2 固定(m,n,p)时两种模式的时间开销对比

由表2可以看出,分解因子r越大,tDirect与tClient比值越大,安全外包的优势就越明显。

当固定(m,n,r)时,采用安全外包和不采用安全外包两种模式的时间开销对比如表3所示。

表3 固定(m,n,r)时两种模式的时间开销对比

由表3可以看出,引入随机矩阵后,p的规模越大,安全外包算法的效率优势逐渐减小,因此用户可以根据实际情况确定随机矩阵的规模。如果对安全性要求较高,对计算速度要求不高时,可以选择一个大规模的随机矩阵。如果对安全性要求较低,对计算速度要求较高时,可以选择一个小规模的随机矩阵。3组实验均表明,安全外包算法能使本地端获得可观的计算节省。

5 结语

通过引入随机矩阵,并使用对角矩阵和置换矩阵等矩阵变换技术,给出了一个云辅助的安全高效非负矩阵分解安全外包算法。该算法不仅盲化了输入矩阵中的非零元素,而且首次实现了盲化了矩阵中零元素的数目和分布。理论分析证明了安全外包算法的正确性、隐私性、可验证性和高效性。实验结果表明,采用安全外包算法能使本地端获得可观的计算节省。