协同优化决策中数据水平分区的隐私保护算法研究

刘智慧, 刘洪伟, 詹明君, 肖　祺, 陈晓旋

(广东工业大学 管理学院，广东 广州 510520)



协同优化决策中数据水平分区的隐私保护算法研究

刘智慧, 刘洪伟, 詹明君, 肖祺, 陈晓旋

(广东工业大学 管理学院，广东 广州 510520)

在跨组织协同优化决策问题中的参数来源于不同主体的数据.在缺乏可信第三方时难以完成全局优化问题的求解.本文运用随机矩阵转换和加密技术方法来解决约束条件中数据水平分区优化问题的协同计算，克服了扰动或差分算法对问题结构以及解结构潜在的不稳定影响.提出的安全协议一方面可以保证在保护各方隐私信息的前提下得到计算结果与集中式的结果具有一致性，另一方面也具备良好的防推理攻击能力.该研究可广泛应用于供应链系统或企业联盟间的决策优化问题的协同安全计算问题.

数据水平分区； 安全协议； 推理攻击

在跨组织的协同优化决策中，常常表现为供应链管理中的生产计划问题、物流运输问题、库存优化问题、订单优化问题等.作为优化决策的一个重要分支，线性规划(linear programming，简称LP)模型可以用来解决各种领域的利润最大化或成本最小化的问题.但是，在求解LP问题的最优解时，目标函数的系数、约束条件的约束矩阵以及右边的向量可能被不同的实体拥有，这些实体不愿意泄露这些数据，这就产生了隐私问题，如何在不泄露这些实体的数据的情况下计算出LP问题的最优解就成了急需解决的课题.

一般地，隐私保护LP有两种不同的方法.第1种是基于转换的方法，这种类型的方法基本上是通过随机矩阵变换实现的，其主要思想是通过转换改变数据使得真实的隐私信息不被披露[1-6].2001年，基于不经意传输协议和随机矩阵转换法，Wenliang Du[1]首次提出一个半诚实模型下的安全两方PPC-LSE(privacy-preserving cooperation linear system of equations)协议.2009年，Vaidya提出了适用于一方拥有目标函数，另一方拥有约束的情况的隐私保护方法，该方法也是通过随机矩阵变换实现的[2].Mangasarian在文献[3]和文献[4]分别针对垂直分割数据和水平分割数据，提出了基于随机矩阵变换的隐私保护方法.然而，一个严重的缺点是这些方法得出的解可能是不可行解.

第2种方法是用加密技术来实现隐私保护[7-15]，这些方法是通过在每一步的算法中对私有数据进行加密.2009年，Vaidya[7]利用安全多方计算提出的基于单纯形法的解决方法是非常有效的，但是只适用于一方拥有目标函数，另一方拥有约束的情况.2009年，Alice Bednarz等[13]指出了利用Du[3]或者Vaidyad[7]的方法来解决隐私保护LP问题，得出的解也可能是不可行解.

为了解决不可行解的问题，Mangasarian在文献[4]提出在多方参与者掌握各自的隐私等式约束条件的情况下，基于随机矩阵变换的隐私保护水平分割LP(PPHPLP)方法.随后，Li等人[5]将该方法拓展成包含不等式约束的PPHPLP方法.然而，该方法还是不够安全——在只有两方参与的情况下，参与者的隐私约束还是会被攻击者推断出来.因此，本文将提出一个防推理的安全两方算法来解决文献中PPHPLP存在的潜在推理攻击.该算法结合了随机矩阵转换和加密技术(不经意传输协议)来实现隐私保护，且安全性比Mangasarian[4]和Li等人[5]提出的方法有所提高.

1　问题提出

1.1数据水平分布的隐私保护LP问题

(1)

Mangasarian采用一个随机矩阵，将原始的LP问题转换成一个安全的LP问题，并证明了在B∈Rk×m,rank(B)=m,k≥m的情况下，这个安全LP和原始LP问题的最优解是等价的.因此，每个参与者i=1,2,…,p生成一个随机矩阵B·Ii∈Rk×mi，使得

B·I1AI1·+B·I2AI2·+…+B·IpAIp·∈Rk×n;

(2)

B·I1bI1+B·I2bI2+…+B·IpbIp∈Rk.

(3)

在Mangasarian[4]的PPHPLP算法中，每个参与者i=1,2,…,p只公开了转换后的矩阵乘积B·IiAIi·和转换后的向量B·IibIi来求解该问题.因此B·Ii∈Rk×mi，AIi和bIi还是隐私的.

而且，Li等人[5]考虑了下面的不等式约束的水平分布LP问题：

mincTx

Mangasarian[4]指出将LP问题中的不等式约束通过添加松弛变量转变为等式约束，然后用Mangasarian的方法转换该问题，这样会泄漏B·Ii.因此，Li等人[5]在Mangasarian的基础上，通过让每个参与者i=1,2,…,p随机生成松弛变量的一个对角矩阵系数D·Ii∈Rmi×mi的方法来解决这一问题.所以，进行一个类似的转换，将原LP问题转变成如下形式：

mincTx

(5)

1.2推理攻击

在Li等人扩展转换的LP问题(5)中，每个参与者i=1,2,…,p随机生成了一个对角矩阵系数D·Ii∈Rmi×mi以防止其他人从松弛变量中推断出其隐私随机矩阵B·Ii.然而，这样的变换方法仍然容易受到潜在的推理攻击.

现在来做一个算例分析：Alice掌握两个约束条件x1+2x2+x3≤4和x1+x2-x3≤1，Bob掌握一个约束条件x1+3x2-2x3≤1.在转换后的LP问题中，Alice和Bob分别生成自己的隐私随机矩阵：

由于该不等式约束需要3个松弛变量(因为要一起解决LP问题，所以这是公开的)，Alice通过m1=2可得知Bob只有一个约束条件即m1=1，那么Alice又可得知B·I2∈R3×1，D·I2∈R1×1.因此，在Alice看来，AI2·∈R1×3，B·I2∈R3×1和bI2∈R1×1中的元素可表示为真实变量α1,α2,α3，β1,β2,β3和δ：

值得注意的是,Mangasarian[4]和Li等人[5]都将每个参与者转换后的矩阵B·IiAIi·和向量B·IibIi公开.因此，在这个两方的算例中，Alice可以将B·I2AI2·∈R3×3和B·I2bI2∈R3×1表示成

上述矩阵和向量中的元素是完全公开的.因此，Alice知道B·I2AI2·和B·I2bI2中有β1α1=0.412 8，β1α2=1.265 4，β1α3=-0.843 6和β1δ=0.421 8，那么Alice可以很快地计算出α1∶α2∶α3∶δ=1∶3∶(-2)∶1.虽然Alice并不能推断出α1,α2,α3,δ精确值，但是她完全可以用α1∶α2∶α3∶δ=1∶3∶(-2)∶1来重构约束条件x1+3x2-2x3≤1.

因此，公开LP问题约束条件的个数m可能会导致严重的隐私泄漏：一个攻击者可以利用真实变量重构方程来推断其他参与者的隐私约束条件.事实上，在现有研究中[4-5]有两种可能的方法可以获得m的信息，如下：

(1) 松弛变量的个数可能就是约束条件的个数m(见上面的算例).

(2) 在文献[12]中，因为转换后的矩阵BA和向量Bb是公开的，所以每个参与者都可以计算出矩阵BA的秩.由B∈Rk×m,rank(B)=m和A∈Rm×n, rank(A)≤m，可得rank(B)≥rank R(A).因此，rank(BA)=rank(A)，那么，所有参与者都可由rank(BA)推出rank(A).然而，约束条件的数量很可能等于rank(A)，特别是在LP问题包含少量约束条件的情况下(这适用于等式约束[4]和不等式约束[5]：在Li等人说明的例子[5]中，rank(BA)=rank(A)是能被计算出来，从而这两个参与者都可以推断出m=3,m1=2,m2=1).因此，在文献[4-5]中，通过rank(BA)来推断出约束条件个数的风险仍然很高.

2　防推理的协议

本文提出一个防推理的安全两方协议来解决在两方参与下的PPHPLP问题.

2.1问题定义

mincTx.

2.2解决方案

为了求解问题(6)，本文在Du[1]和Yang[16]等人的研究基础上，提出一个防推理的安全两方算法.这些学者都是用基于转换的方法来安全地解决线性方程组问题.如果想把其应用到LP问题中，那么问题(6)必须通过添加m个松弛变量转换成标准形式：

(7)

这里用新符号来表示标准形式中的变量：

本文进行一个等价的转换(N1+N2)X=b1+b2⟺K(N1+N2)QQ-1X=K(b1+b2)，将原LP问题转变成如下形式：

minCTQQ-1X

协议：Alice掌握矩阵N1和向量b1，Bob掌握矩阵N2和向量b2，N1,N2∈Rm×(m+n)，b1,b2∈Rn×1.(1) Alice和Bob通过添加松弛变量将他们的约束转换成等式形式：

(2) Bob生成随机可逆矩阵K∈Rm×m和广义置换矩阵Q∈R(m+n)×(m+n)(Q和Q-1中所有元素均为非负数)；

2.2.1算例分析

为了展现完整的算法，考虑下面的优化问题，其中n=3,m=3:

(9)

在上述问题的约束条件中加入松弛变量x4,x5,x6，得到：

(10)

其中Alice掌握

(11)

2.2.2安全两方协议

本协议改编自Du[1]和Yang等人[16]的研究.因为本文研究的是水平分布的数据矩阵，所以本文要修改该协议，使得该结构无法轻易地被Bob利用.主要的改变是：在计算之前就将N1中的零矩阵截断.Alice将N1截断后的子秘密传送Bob，然后Bob在执行计算前，将其“填写”成已知的矩阵结构.

协议：

(4) 对每一个j=1,2,…,d，Alice和Bob执行下面的子步骤：

(6) Alice计算

2.3安全性和计算复杂性

在隐藏两方的隐私信息时，特别地让Bob掌握可逆矩阵K和广义置换矩阵Q，然后Alice和Bob使用上述的安全协议来交换数据，从而Alice得到K(N1+N2)Q和K(b1+b2)，但是Alice不知道Bob的隐私数据，也推测不出来.同样地，Bob也无法推测出Alice的隐私数据.

整个算法的计算复杂度主要取决于我们解决转换LP问题所选择的方法(单纯形法、内点法等).用户自主选择最有效的方法来解决这特定的转换LP问题，因此，本文的关注点是基于转换所产生的成本.

与文献[8,10,15]的加密算法相比，转换协议只需要在算法开始的时候运行一次，而不是每一次迭代中，这大大地减少了计算和通信成本.

通过比较，Toft的安全单纯形法[10]需要O(m(m+n))次安全乘法和在每一次主元转换中执行O(m)次安全比较.在最坏的情况下，单纯形法的计算成本是主元的指数级数量[18]，因此Toft的算法是不切实际的.

3　结束语

本文对前人的水平分区隐私保护LP问题[4-5]存在的潜在推理攻击进行了分析，即在两方的情况下，参与者的隐私信息能够被对手推断出来.因此，本文提出了一个防推理的安全两方算法来解决水平分区保护隐私LP问题.同时，还对该算法的安全性和计算复杂性进行了分析.

实际应用时，还要讲究计算的效率问题，目前多数SMC方法的计算复杂度比较高，如何提高实际协同决策时的SMC方法的计算效率，还是一个非常广阔的研究方向.在以后的研究中，将继续研究如何安全高效地解决现实世界中的协同优化问题.

[1] DU W, ATALLAH M J. Privacy-preserving cooperative scientific computations[C] ∥ Smith G: Proceedings of the 14th IEEE Computer Security Foundations Workshop. Washington: IEEE Compucter Society, 2001: 0273-0273.

[2] VAIDYA J. Privacy-preserving linear programming[C] ∥ Shin S Y: Proceedings of the 2009 ACM symposium on Applied Computing. New York: ACM, 2009: 2002-2007.

[3] MANGASARIAN O L. Privacy-preserving linear programming[J]. Optimization Letters, 2010, 5(1): 165-172.

[4] MANGASARIAN O L. Privacy-preserving horizontally partitioned linear programs[J]. Optimization Letters, 2012, 6(3): 431-436.

[5] LI W, DENG C Y. Privacy-preserving horizontally partitioned linear programs with inequality constraints[J]. Optimization Letters, 2013, 2013, 7(1):137-144.

[6] 陆涛, 刘洪伟, 刘智慧, 等. 跨组织间隐私数据水平分布线性规划协同优化算法研究[J]. 广东工业大学学报, 2015, 32(2): 43-47.

LU T, LIU H W, LIU Z H, et al. Collaborative optimization algorithm research on cross-organization’s privacy data horizontally partitioned linear programing[J].Journal of Guangdong University of Technology, 2015, 32(2): 43-47.

[7] VAIDYA J. A secure revised simplex algorithm for privacy-preserving linear programming[C] ∥ Gelenbe E: AINA ′09 Proceedings of the 2009 International Conference on Advanced Information Networking and Applications. Washington: IEEE Computer Society, 2009: 347-354.

[8] LI J, ATALLAH M J. Secure and private collaborative linear programming[C] ∥ Cheng-Jia L: International Conference on Collaborative Computing: Networking, Applications and Worksharing (2006). Washington: IEEE Computer Society, 2006: 1-8.

[9] TOFT T. Primitives and applications for multi-party computation[D]. Aarhus: Department of Computer Science, University of Aarhus, 2007.

[10] TOFT T: Solving linear programs using multiparty computation[C] ∥ Roger D: Financial Cryptography and Data Security. Berlin: Springer Berlin Heidelberg, 2009: 90-107.

[11] HONG Y. Privacy-preserving collaborative optimization[D]. New Jersey: Graduate School-Newark , Rutgers, The State University of New Jersey, 2013.

[12] HONG Y, Vaidya J. Secure transformation for multiparty linear programming[R]. New Jersey: Rutgers Technical Report, 2013.

[13] BEDNARZ A, BEAN N, ROUGHAN M. Hiccups on the road to privacy-preserving linear programming[C] ∥ Ehab Al-Shaer: Proceedings of the 8th ACM Workshop on Privacy in the Electronic Society. New York: ACM, 2009: 117-120.

[14] 刘洪伟, 刘智慧, 朱慧, 等. 大数据环境下跨组织间协同优化决策的隐私保护算法[J]. 广东工业大学学报, 2014, 31(3): 21-26.

LIU H W, LIU Z H, ZHU H, et al. Privacy-preserving Algorithm for cross-organizational collaborative optimization decision based on big data[J]. Journal of Guangdong University of Technology, 2014, 31(3): 21-26.

[15] CATRINA O, HOOGH S D. Secure multiparty linear programming using fixed-point arithmetic[J]. Lecture Notes in Computer Science, 2010, 6345: 134-150.

[16] YANG X, YU Z, KANG B. Privacy-preserving cooperative linear system of equations protocol and its application[C] ∥ Hu Y: The 4th International Conference on Wireless Communications, Networking and Mobile Computing. Washington: IEEE Computer Society, 2008: 1-4.

[17] NAOR M, PINKAS B. Oblivious transfer and polynomial evaluation[C] ∥ Jeffrey S: Proceedings of the thirty-first annual ACM symposium on Theory of computing. New York : ACM, 1999: 245-254.

[18] KLEE V, MINTY G J. How good is the simplex algorithm[R]. Washington: Washington Univ Seattle Dept of Mathematics, 1970.

Privacy-Preserving Algorithm Research on Horizontally Partitioned Data of Collaborative Optimization Decisions

Liu Zhi-hui, Liu Hong-wei, Zhan Ming-jun, Xiao Qi, Chen Xiao-xuan

(School of Management, Guangdong University of Technology, Guangzhou 510520, China)

In the cross-organizational collaborative optimal decision-making, the parameters of optimization usually originate from different subject data. It is difficult to solve the global optimization problems due to the lack of a trusted third party. A method combining the random matrix transformation and encryption technology is put forward to solve the collaborative optimization of the horizontally partitioned data. This method also overcomes the potential destabilizing impact of structural problems and structural solutions when using disturbance or difference algorithm. On one hand, the security protocol can ensure the consistency of calculation results with privacy-preserving and centralized results. On the other side, it can prevent the potential inference attack. The study can be widely used in collaborative computing security issues of optimization decision problems among enterprise alliance or supply chain.

data horizontally partitioned; security protocol; inference attack

2016- 03- 09

国家自然科学基金资助项目(70971027)；广东省普通高校人文社会科学重点研究项目(12ZS0112)

刘智慧(1990-)，女，硕士研究生，主要研究方向为隐私保护、电子商务.

刘洪伟(1962-),男，教授，博士生导师，主要研究方向为管理决策、数据分析、隐私保护等.E-mail:liuhongwei@gdut.edu.cn

10.3969/j.issn.1007- 7162.2016.05.004

TP309.2； F22.31

A

1007-7162(2016)05- 0015- 07