任意合谋模式下双边安全分布式矩阵计算的成本优化方法

1.本发明属于分布式安全矩阵计算技术领域，涉及分布式矩阵计算技术，矩阵安全加密技术，矩阵计算总成本优化技术，尤其涉及任意合谋模式下双边安全分布式矩阵计算的成本优化方法。


背景技术：

2.随着第五代(5g)无线网络的发展，吞吐量和传输速率迅速提高。这要求移动设备能够即时处理大量数据以满足服务质量(qos)。由于体积和功率的限制，移动设备无法独立完成所有数据处理工作。这使我们向一些旨在协助移动用户进行数据处理的在线服务器寻求帮助。此外，我们可以利用分布式服务器来加速数据处理，这意味着用户可以将计算任务分配给许多不同的服务器。然而，在保证返回给用户的数据的可解码性的同时，因为一些窃取用户数据的服务器，我们必须考虑数据的安全性。针对上述场景，本发明为解决一种任意合谋模式下双边安全分布式矩阵计算的成本优化问题，提出了一个求解该问题可行解的迭代算法。


技术实现要素：

3.发明目的：本发明的目的在于针对现有技术存在的不足，提供一种任意合谋模式下双边安全分布式矩阵计算的成本优化方法，该方法一方面能满足矩阵计算安全性、可解码性以及最大计算时延的需求，同时满足服务器存储要求，另一方面最小化系统的总成本，以此提升系统资源效率。
4.技术方案：为实现上述发明目的，本发明采取如下技术方案：
5.一种任意合谋模式下双边安全分布式矩阵计算的成本优化问题，包括如下步骤：
6.(1)对于两个输入矩阵和其中t表示矩阵a的行，s表示矩阵a的列以及矩阵b的行，d表示矩阵b的列，且t、s和d都是整数，并且有限域足够大，初始化矩阵的维度以及分割块数t,s,d,(t
(0)
,s
(0)
,d
(0)
)，其中t
(0)
表示沿矩阵a行分割的块数，s
(0)
表示沿矩阵a列分割的块数以及沿矩阵b行分割的块数，d
(0)
表示沿矩阵b列分割的块数，用户的上传成本cu、用户的下载成本cd、服务器的计算成本cc，第n个服务器的计算速度vn、上传速度下载速度矩阵计算最大时延q
thes
、系统参数p,y、迭代次数τ＝0，迭代误差∈；
7.(2)采用交替优化算法，给定矩阵的分割块数(t
(τ)
,s
(τ)
,d
(τ)
)，其中t
(τ)
表示第τ次迭代后沿矩阵a行分割的块数，s
(τ)
表示第τ次迭代后沿矩阵a列分割的块数以及沿矩阵b行分割的块数，d
(τ)
表示第τ次迭代后沿矩阵b列分割的块数，构建任意合谋模式下双边安全分布式矩阵计算的成本优化的矩阵分配以及安全加密子问题p1，求解子问题p1得到第τ+1次迭代后矩阵分配向量j
(τ+1)
以及第τ+1次迭代后随机矩阵个数
8.(3)给定矩阵分配向量j
(τ+1)
以及随机矩阵个数构建任意合谋模式下双边安全分布式矩阵计算的成本优化的矩阵分割子问题p2，采用yalmip工具包求解子问题p2得到
矩阵的分割块数(t
(τ+1)
,s
(τ+1)
,d
(τ+1)
)，其中t
(τ+1)
表示第τ+1次迭代后沿矩阵a行分割的块数，s
(τ+1)
表示第τ+1次迭代后沿矩阵a列分割的块数以及沿矩阵b行分割的块数，d
(τ+1)
表示第τ+1次迭代后沿矩阵b列分割的块数，接着采用向上取整函数得到矩阵分割块的维度分割块多余的行或列采用0来补全以此解决矩阵分割整除性问题；
9.(4)计算迭代目标函数的误差，若小于迭代误差∈，停止迭代；否则，返回步骤(2)。
10.优选的，子问题p1构建为：
[0011][0012][0013]1t
j≥l
δ
(sd+2s)+ts(d+1)-1,
[0014][0015][0016][0017]
其中，j表示矩阵分配向量，l
δ
表示随机矩阵个数，代表合谋模式矩阵，q
thes
代表矩阵计算最大时延，m表示服务器存储能力向量，n表示服务器的个数。
[0018]
优选的，先求解随机矩阵个数l
δ
，接着求解矩阵分配以及安全加密子问题p1，具体步骤包括：
[0019]
(2.1)对于固定参数(t,s,d)，可行的l
δ
必须满足以下不等式：
[0020][0021]
其中，p是包含所有服务器的最小合谋集合数；
[0022]
(2.2)如果以及p-d-2＞0，计算随机矩阵个数否则子问题p1不可解；
[0023]
(2.3)用matlab"intlinprog"函数求解子问题p1，以得到矩阵分配向量j；
[0024]
(2.4)如果矩阵分配向量j为可行解，则输出j和l
δ
；否则，令l
δ
＝l
δ
+1，再用
matlab"intlinprog"函数求解子问题p1，直到子问题p1可解，或者子问题p1不可解。
[0025]
优选的，矩阵分割子问题p2构建为：
[0026][0027][0028][0029]
(tst-1
s-1
+sds-1
d-1
+tdt-1
d-1
)1n≤m,
[0030][0031]
1≤t≤t,1≤s,1≤d≤d,
[0032]
d≤p-2,
[0033][0034]
给定采用yalmip求解器直接求解子问题p2，得到(t
(τ+1)
,s
(τ+1)
,d
(τ+1)
)，接着借助向上取整函数得到矩阵分割块的维度
[0035]
有益效果：与现有技术相比，本发明求解了任意合谋模式下双边安全分布式矩阵计算在矩阵计算安全性、可解码性以及最大计算时延的需求下，同时满足服务器存储要求，系统总成本最小化问题，并提出一种矩阵加密、分配以及分割策略，方法简单，结果准确，对比同构、异构分布式服务器系统，本发明可以降低系统成本，同时确保矩阵计算的安全性、可解码性以及服务器存储需求。
附图说明
[0036]
图1是双边安全分布式矩阵计算系统图。
具体实施方式
[0037]
本发明分别考虑分布式矩阵计算的矩阵分配、加密子问题以及分布式矩阵计算的矩阵分割子问题，具体是给定矩阵加密安全约束，用户的矩阵解码约束，分布式服务器的存储约束，矩阵计算时延约束，最小化系统总成本。给出了一种交替优化的迭代算法，该算法所得的矩阵分配向量，随机矩阵个数以及矩阵分割参数均为最终的安全分布式矩阵计算方案。
[0038]
具体步骤包括：
[0039]
考虑一个用户想要计算两个输入矩阵和的乘法。我们假设t、s和d
都是整数，并且有限域足够大。由于自身计算能力有限，用户希望将两个矩阵a和b分割成很多块，上传到n台服务器进行计算。同时，矩阵a和b都包含敏感信息，用户不希望将任何信息泄露给n台服务器。我们研究服务器之间可能合谋以获得两个矩阵a和b的信息的情况。我们用合谋模式来表示合谋行为，其中包含m个合谋集合，即来表示合谋行为，其中包含m个合谋集合，即是第m个合谋集合，这意味着中的服务器可能合谋获取两个矩阵的信息。我们对共谋模式做出以下两个假设：
[0040]
(1)为了便于表达，我们只在p中包含最大共谋集。
[0041]
(2)每个服务器必须至少出现在一个共谋集中。这是因为我们假设所有服务器都是好奇的，并且没有服务器可以信任a、b的敏感信息。
[0042]
合谋模式可以用其关联矩阵表示，大小为n
×
m，即如果第i个服务器在的第j个共谋集中，则中第(i,j)个元素的值为1。
[0043]
由于需要保证两个矩阵的安全，用户必须先对a、b进行编码，然后再将它们上传到服务器进行计算。假设有个n1编码副本，且n1≥n，则这些编码函数表示为：我们用和分别表示矩阵a和b的第i个编码副本，i∈[1:n1]，即用户分配编码矩阵的索引子集给第n个服务器，这称为上传阶段。第n个服务器计算分块矩阵乘积，即然后，第n个服务器将计算结果zi发送回给用户，这称为下载阶段。我们使用secure generalized polydot code(sgpd)来对两个输入矩阵进行编码。矩阵a可以被分割为t
×
s个小块，矩阵b可以被分割为s
×
d个小块，即
[0044][0045]
其中t∈[1:t],s∈[1:s],d∈[1:d],出于矩阵的加密考虑，我们对矩阵a和b添加随机矩阵即
[0046][0047]
其中，对矩阵a添加l
δ
行随机矩阵，对矩阵b添加l
δ
列随机矩阵，l
δ
为正整数。随机矩阵中的每一个元素都是独立同分布的，却在有限域服从均匀分布。基于此，加密矩阵可表示为
[0048][0049][0050]
其中，xi,i＝1,2,
…
,n1是有限域中n1个不同的非零元素，t
*
＝t+l
δ
,d
*
＝d+l
δ
。
[0051]
令矩阵分配向量表示为j＝[j
1 j2ꢀ…ꢀjn
]
t
，其中jn∈[0:n1]是分配给第n个服务器的加密矩阵数。所以，我们有为了确保矩阵计算的安全性，必须满足即同时必须满足用户的矩阵可解码性，必须满足h(ab|z1,z2,
…
,z
n1
)＝0，即1
t
j＝n1≥l
δ
(sd+2s)+ts(d+1)-1。假设每一个编码副本所占空间为如果第n个服务器的存储能力为mn，则必须满足若第n个服务器的计算速度，上传速度以及下载速度分别表示为vn,矩阵计算最大时延为q
thes
，则需满足若服务器的上传以及下载成本向量和计算成本向量表示为cu,cd,cc，则系统总成本可以写成
[0052]
因此，总体优化问题可建模为
[0053][0054][0055]1t
j≥l
δ
(sd+2s)+ts(d+1)-1,
[0056][0057][0058][0059]
其中，表示正整数，表示有理数，m表示服务器存储能力向量。为求解上述总体优化问题，采用交替优化技术，包括如下步骤：
[0060]
(1)初始化矩阵的维度以及分割块数t,s,d,(t
(0)
,s
(0)
,d
(0)
)，用户的上传以及下载成本和服务器的计算成本cu,cd,cc，第n个服务器的计算速度，上传速度以及下载速度
矩阵计算最大时延q
thes
，系统参数p,y，迭代次数τ＝0，迭代误差∈；
[0061]
(2)采用交替优化算法，给定矩阵的分割块数(t
(τ)
,s
(τ)
,d
(τ)
)，构建任意合谋模式下双边安全分布式矩阵计算的成本优化的矩阵分配以及安全加密子问题p1，求解子问题p1得到矩阵分配向量以及随机矩阵个数
[0062]
(3)给定矩阵分配向量以及随机矩阵个数构建任意合谋模式下双边安全分布式矩阵计算的成本优化的矩阵分割子问题p2，采用yalmip工具包求解子问题p2得到矩阵的分割块数(t
(τ+1)
,s
(τ+1)
,d
(τ+1)
)，接着采用向上取整函数得到矩阵分割块的维度分割块多余的行或列采用0来补全以此解决矩阵分割整除性问题；
[0063]
(4)计算迭代目标函数的误差，若小于迭代误差∈，停止迭代；否则，返回步骤(2)。
[0064]
优选的，其中步骤(2)中求解问题(p1)的具体方法如下：
[0065]
首先，给定矩阵分割块数(t,s,d)，问题(p1)可构建为
[0066][0067][0068]1t
j≥l
δ
(sd+2s)+ts(d+1)-1,
[0069][0070][0071][0072]
为求解矩阵分配及加密子问题(p1)，采用如下迭代算法，
[0073]
(2.1)对于固定参数(t,s,d)，可行的l
δ
必须满足以下不等式：
[0074][0075]
其中，p是包含所有服务器的最小合谋集合数。
[0076]
(2.2)如果以及p-d-2＞0，计算随机矩阵个数
否则子问题p1不可解。
[0077]
(2.3)第三步，用matlab"intlinprog"函数求解子问题p1，以得到矩阵分配向量j。
[0078]
(2.4)第四步，如果矩阵分配向量j为可行解，则输出j和l
δ
。否则，令l
δ
＝l
δ
+1，再用matlab"intlinprog"函数求解子问题p1，直到子问题p1可解，或者子问题p1不可解。
[0079]
优选的，其中步骤(3)包括：
[0080]
给定矩阵分配向量j和随机矩阵个数l
δ
，矩阵分割子问题p2可构建为
[0081][0082][0083][0084]
(tst-1
s-1
+sds-1
d-1
+tdt-1
d-1
)1n≤m,
[0085][0086]
1≤t≤t,1≤s,1≤d≤d,
[0087]
d≤p-2,
[0088][0089]
给定采用yalmip求解器直接求解子问题p2，得到(t
(τ+1)
,s
(τ+1)
,d
(τ+1)
)，接着借助向上取整函数得到矩阵分割块的维度
[0090]
本发明方案所公开的技术手段不仅限于上述实施方式所公开的技术手段，还包括由以上技术特征任意组合所组成的技术方案。

技术特征：
1.一种任意合谋模式下双边安全分布式矩阵计算的成本优化方法，其特征在于，包括如下步骤：(1)对于两个输入矩阵和其中t表示矩阵a的行，s表示矩阵a的列以及矩阵b的行，d表示矩阵b的列，且t、s和d都是整数，并且有限域足够大，初始化矩阵的维度以及分割块数t,s,d,(t
(0)
,s
(0)
,d
(0)
)，其中t
(0)
表示沿矩阵a行分割的块数，s
(0)
表示沿矩阵a列分割的块数以及沿矩阵b行分割的块数，d
(0)
表示沿矩阵b列分割的块数，用户的上传成本c
u
、用户的下载成本c
d
、服务器的计算成本c
c
，第n个服务器的计算速度v
n
、上传速度下载速度矩阵计算最大时延q
thes
、系统参数p,y、迭代次数τ＝0，迭代误差∈；(2)采用交替优化算法，给定矩阵的分割块数(t
(τ)
,s
(τ)
,d
(τ)
)，其中t
(τ)
表示第τ次迭代后沿矩阵a行分割的块数，s
(τ)
表示第τ次迭代后沿矩阵a列分割的块数以及沿矩阵b行分割的块数，d
(τ)
表示第τ次迭代后沿矩阵b列分割的块数，构建任意合谋模式下双边安全分布式矩阵计算的成本优化的矩阵分配以及安全加密子问题p1，求解子问题p1得到第τ+1次迭代后矩阵分配向量j
(τ+1)
以及第τ+1次迭代后随机矩阵个数(3)给定矩阵分配向量j
(τ+1)
以及随机矩阵个数构建任意合谋模式下双边安全分布式矩阵计算的成本优化的矩阵分割子问题p2，采用yalmip工具包求解子问题p2得到矩阵的分割块数(t
(τ+1)
,s
(τ+1)
,d
(τ+1)
)，其中t
(τ+1)
表示第τ+1次迭代后沿矩阵a行分割的块数，s
(τ+1)
表示第τ+1次迭代后沿矩阵a列分割的块数以及沿矩阵b行分割的块数，d
(τ+1)
表示第τ+1次迭代后沿矩阵b列分割的块数，接着采用向上取整函数得到矩阵分割块的维度分割块多余的行或列采用0来补全以此解决矩阵分割整除性问题；(4)计算迭代目标函数的误差，若小于迭代误差∈，停止迭代；否则，返回步骤(2)。2.根据权利要求1所述的任意合谋模式下双边安全分布式矩阵计算的成本优化方法，其特征在于，子问题p1构建为：(p1)(p1)1
t
j≥l
δ
(sd+2s)+ts(d+1)-1,1,1,
其中，j表示矩阵分配向量，l
δ
表示随机矩阵个数，代表合谋模式矩阵，q
thes
代表矩阵计算最大时延，m表示服务器存储能力向量，n表示服务器的个数。3.根据权利要求2所述的任意合谋模式下双边安全分布式矩阵计算的成本优化方法，其特征在于，先求解随机矩阵个数l
δ
，接着求解矩阵分配以及安全加密子问题p1，具体步骤包括：(2.1)对于固定参数(t,s,d)，可行的l
δ
必须满足以下不等式：其中，是包含所有服务器的最小合谋集合数；(2.2)如果以及p-d-2＞0，计算随机矩阵个数否则子问题p1不可解；(2.3)用matlab"intlinprog"函数求解子问题p1，以得到矩阵分配向量j；(2.4)如果矩阵分配向量j为可行解，则输出j和l
δ
；否则，令l
δ
＝l
δ
+1，再用matlab"intlinprog"函数求解子问题p1，直到子问题p1可解，或者子问题p1不可解。4.根据权利要求1所述的任意合谋模式下双边安全分布式矩阵计算的成本优化方法，其特征在于，矩阵分割子问题p2构建为：(p2)(p2)(p2)(tst-1
s-1
+sds-1
d-1
+tdt-1
d-1
)1
n
≤m,1≤t≤t,1≤s,1≤d≤d,d≤p-2,
给定采用yalmip求解器直接求解子问题p2，得到(t
(τ+1)
,s
(τ+1)
,d
(τ+1)
)，接着借助向上取整函数得到矩阵分割块的维度

技术总结
本发明公开了任意合谋模式下双边安全分布式矩阵计算的成本优化方法，其中总成本包括计算成本和传输成本。在所提出的优化问题中考虑了矩阵的可解码性和安全性、服务器的存储能力和计算延迟。本发明提出了一种补0方案来克服矩阵分割的整除性问题。然后，讨论了分割矩阵块的维度以最小化总成本。在此基础上，借助交替优化(AO)算法将优化问题划分为两个子问题，得到可行解。仿真结果表明，同构和异构服务器的总成本随着两个输入矩阵的维度增加而显著增加。而且，对于异构服务器，由于各个服务器的属性不同，总成本可以明显降低。总成本可以明显降低。


技术研发人员：刘楠 李进 康维
受保护的技术使用者：东南大学
技术研发日：2023.07.31
技术公布日：2023/9/26