随着经济全球化的深化和信息技术的发展，企业间的合作变得尤为重要，特别是在供应链管理中，为了提高顾客满意度和整个供应链的竞争力，供应链协同是供应链中各企业或组织的必然选择.供应链协同优化决策就是各企业或组织在信息共享的基础上，以整体供应链最优为目标进行协同决策，例如协同物流、协同生产以及协同调度等.然而在实践中，供应链中各成员很少愿意与其他成员共享信息，担心共享信息会给自己带来负面影响，称这些信息为“隐私信息”^[1].如何在不泄漏各自的私有信息情况下完成供应链的协同优化决策，是供应链管理中的重要难题.

线性规划模型是一类最基本且应用广泛的优化模型，然而在实际应用中模型的约束矩阵和目标函数都是基于不同实体的隐私信息或数据构建的，并且各实体都不愿意公开自己的隐私信息.目前解决基于隐私保护的协同优化问题的主要方法是建立可信第三方，如IBM^® Sterling Transportation Management System (TMS)，但是可信第三方并非绝对可信, 而且可信第三方可能需要高额的服务费用.在没有可信第三方的情况下，安全多方计算(Secure Multiparty Computation，SMC)是解决此类问题行之有效的方法.安全多方计算最早由A.C.Yao^[2]于1982年提出，即百万富翁问题，后来Goldreich，Micali和Wigderson将其理论扩展，并给出了一般的描述^[3].由于安全多方计算具有广泛的应用前景，目前许多国内外专家都致力于安全多方计算的研究.

对于基于隐私保护的线性规划模型, Yuan Hong等^[4]根据实际应用把数据的分布分为水平分布/同构、垂直分布/异构和任意分布；Mangasarian^[5]和Li^[6]分别针对等式和不等式约束条件的水平数据分布的隐私保护线性规划模型提出了基于随机矩阵变换的解决方案，但是该解决方案存在可推断攻击；Yuan Hong等^[7]对Mangasarian和Li所提出的方法进行了改进，提出了防推断型的解决方案.但是以上的基于隐私保护的线性规划模型的研究都是假设目标函数为公开信息，而在实际应用中目标函数也可能为隐私信息，例如供应链中的制造商、原材料供应商以及其他分布在不同地点的供应链结点进行协同物流，需要选择一家物流运输商.然而不同的物流运输商有不同的价格(但运输商不想泄露自己的价格信息让竞争对手知道)，也就导致了不同的目标函数.本文拟对线性规划模型的约束矩阵数据水平分布且目标函数也为实体隐私信息提出基于随机矩阵变换的仿推断解决方法.

1 问题的提出

基于水平数据分布的线性规划是指线性规划的约束矩阵和相应的资源向量按行分布在不同的实体中.即对于标准线性规划

$ \begin{array}{l} \min \;\mathit{\boldsymbol{z}}{\rm{ = }}{\mathit{\boldsymbol{C}}^{\rm{T}}}\mathit{\boldsymbol{X}}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ \begin{array}{l} \mathit{\boldsymbol{AX}} \le \mathit{\boldsymbol{b}}\\ \mathit{\boldsymbol{X}} \ge 0 \end{array} \right. \end{array} $

中$\left[ {\mathit{\boldsymbol{A}}\;\;\;\mathit{\boldsymbol{b}}} \right] = \left[ \begin{array}{l} {\mathit{\boldsymbol{A}}_{1 \cdot }}\;\;\;{\mathit{\boldsymbol{b}}_{1 \cdot }}\\ {\mathit{\boldsymbol{A}}_{2 \cdot }}\;\;\;{\mathit{\boldsymbol{b}}_{2 \cdot }}\\ \;\; \vdots \;\;\;\;\;\; \vdots \\ {\mathit{\boldsymbol{A}}_{p \cdot }}\;\;\;{\mathit{\boldsymbol{b}}_{p \cdot }} \end{array} \right]$，其中${\mathit{\boldsymbol{A}}_{i \cdot }}\mathit{\boldsymbol{X}} \le {\mathit{\boldsymbol{b}}_i}$.(包含等式约束和不等式约束)为实体i(i=1, …, p)的隐私信息，A∈R^m×n，C∈Rⁿ，b∈Rⁿ，b_i·∈R^m_i，A_i·∈R^m_i×n($\sum\nolimits_{i = 1}^p {{m_i} = m} $)，X=(x₁, x₂, …, x_n)^T.另外假设线性规划目标函数系数C为实体p+1(如物流运输商)的隐私信息，本文主要解决了在不泄露实体i(i=1, …, p, p+1)的隐私信息情形下求解线性规划.

2 基本理论

本文是在半诚实模型下讨论基于隐私保护的协同优化问题.在半诚实模型中，参与方在执行协议的过程中会忠实地履行协议，但他可能会保留所有中间结果，试图从中间结果推导出协议之外的信息^[8].本文主要通过基于随机矩阵变换的方式隐藏各实体的隐私信息，其中主要用到了同态加密体制和安全双方点积协议.

(1) 同态加密体制

同态加密的概念是由Rivest，Adleman和Dertouzos于1978年提出.同态加密的特殊性质可以直接对密文进行某些运算来代替对明文的运算取得同样的效果，这样不影响明文数据的机密性.Goldwasser-Micali加密算法^[9]、Benaloh加密算法^[10]、Naccache-Stern加密算法^[11]、ElGamal加密算法^[12]、Paillier加密算法^[13]等都是一种同态加密算法.同态加密体制按其性质可以分为加同态和乘同态两种.加同态是指满足E(m₁)·E(m₂)=E(m₁+m₂)的加密方案，例如Paillier加密算法；乘同态是指满足E(m₁)·E(m₂)=E(m₁×m₂)的加密方案，例如ElGamal加密算法.

(2) 安全点积协议

安全点积问题可以描述为：Alice和Bob的输入分别为一个n维私有向量X(x₁, x₂, …, x_n)和Y=(y₁, y₂, …, y_n)，Bob随机选取一个随机数r_b, Alice需要得到值w=X·Y+r_b, 要求Alice不能从w中得到任意一个y_i的消息，而且Bob也不能获得w和任意一个x_i的消息.协议1描述了一种基于同态加密体制的安全两方点积协议.

协议1  基于同态加密体制的安全两方点积协议：

Step1：Alice产生一对私钥和公钥(sk，pk).

Step2：Alice将pk发送给Bob.

Step3：Bob选择n个随机数r_i并重新构造自己的隐私向量，令Y′=(y₁-r₁, …, y_n-r_n), 并将Y′发送给Alice.

Step4：Alice利用同态加密算法计算c=E_pk(x_i)和ω=E_pk(x_i(y_i-r_i)), 并将c, ω发送给Bob.

Step5：Bob收到(c, ω)后计算m_i=c^r_iω(i=1, …, n), 并选择一个随机数r_b, 计算s=E_pk(r_b)$\prod\limits_{i - 1}^n {{m_i}} $, 将s发送给Alice.

Step6：Alice利用私钥sk对s进行解密：w=Dec_sk(s)=$\sum\limits_{i = 1}^n {{x_i}{y_i} + {r_b}} $

目前点积协议得到了广泛的理论研究, 且广泛应用于保护隐私信息的各类协作计算，如数据挖掘、统计分析、信息检索等，并成为SMC一个基本的协议.

3 构建安全的新线性规划模型 3.1 隐藏实体i(i=1, …, p)的隐私信息

首先，对于线性规划(1)需要添加松弛变量使不等约束转换成等式约束，但是为了增加变换的随机性和防止攻击者的推断，令实体i=1, …, p根据自己私有的原始约束条件在本地产生人造约束条件组成实体i新的私有约束条件.注意人造约束条件不能改变原始约束条件的可行域，例如，实体i有不等式约束条件2x₁-3x₂≤10, 其中x ≥0，则实体i可以产生的人造约束条件为x₁-2x₂≤5，x₁-3x₂≤10，x₁-1.7x₂≤5等；如果实体i拥有等式约束条件x₁+2x₂=8，其中x≥0，则实体i可以产生人造约束条件为x₁+x₂≤8，0.5x₁+0.9x₂≤4等(不建议产生人造等式约束，因为不改变矩阵A的秩).通过增加人造约束条件，原始模型中的A和b扩展为A′∈R^m′×n和b′∈R^m′(m′为所有实体的原始约束条件和人造约束条件的个数总和)，即模型转化为

$ \begin{array}{l} \min \;\mathit{\boldsymbol{z = }}{\mathit{\boldsymbol{C}}^{\rm{T}}}\mathit{\boldsymbol{X}}{\rm{;}}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ \begin{array}{l} \mathit{\boldsymbol{A'X}} \le \mathit{\boldsymbol{b'}}\\ \;\;\;\mathit{\boldsymbol{X}} \ge {\rm{0}}{\rm{.}} \end{array} \right. \end{array} $

(2)

其次，添加松弛变量.令加入人造约束条件后的线性规划模型(2)中不等式约束条件个数为l(l≤m′).同样，为了防止攻击者的推断，实体i(=1, …, p)在本地对其不等式约束条件可以添加多于1个的松弛变量把不等式约束转换成等式约束.对于模型(2)中第j(j=1, …, l)个不等式约束，设其拥有的实体为其增加t_j个松弛变量变为等式约束，则最后的模型(2)中拥有$t = \sum\nolimits_{j = 1}^l {{t_j} \ge l} $个松弛变量.令实体i(i=1, …, p)转换其不等式约束的所用的松弛变量的个数为T_i.一般情况下，T_i可以取得相当大(如令T_i≥m′_i，m′_i为模型(1)中实体i私有的约束条件的个数)，则有$t = \sum\nolimits_{i = 1}^p {{T_i} > m' \ge l > \ell } $($\ell $为模型(2)中的不等式约束条件个数)和m′>m≥$\ell $(m=$\ell $时，模型(2)最容易受到攻击者的攻击).通过添加松弛变量，线性规划(2)变换为

$ \begin{array}{l} \min \;\mathit{\boldsymbol{z = }}{\mathit{\boldsymbol{C}}^{\rm{T}}}\mathit{\boldsymbol{X}}{\rm{, }}\\ {\rm{s}}{\rm{.t}}.\left[ {\mathit{\boldsymbol{A'}}\;\;\;\;\mathit{\boldsymbol{M'}}} \right]\left[ \begin{array}{l} \mathit{\boldsymbol{X}}\\ {\mathit{\boldsymbol{X}}_s} \end{array} \right]{\rm{ = }}\mathit{\boldsymbol{b'}}, \mathit{\boldsymbol{X}} \ge 0, {\mathit{\boldsymbol{X}}_s} \ge 0. \end{array} $

(3)

其中A′∈R^m′×n，松弛变量集合X_s=[s₁, s₂, …, s_t]^T，M′∈R^m′×t为所有约束条件中松弛变量的系数矩阵：M′中对应(2)中每个等式约束的行的元素全为0；M′中对应(2)中第j(j=1, …, l)个不等式约束所在行中t_j个松弛变量系数为随机产生的正实数；M′中其余元素为0.在水平数据分布的线性规划模型(3)中实体i=1, …, p的隐私信息为$\left[ {{{\mathit{\boldsymbol{A'}}}_{i \cdot }}\;\;\;\;{{\mathit{\boldsymbol{M'}}}_{i \cdot }}} \right]\left[ \begin{array}{l} \mathit{\boldsymbol{X}}\\ {\mathit{\boldsymbol{X}}_s} \end{array} \right] = {{\mathit{\boldsymbol{b'}}}_i}$，其中${{\mathit{\boldsymbol{A'}}}_{{I_{i \cdot }}}} \in {\mathit{\boldsymbol{R}}^{{{m'}_i} \times n}}, \;{{\mathit{\boldsymbol{b'}}}_i} \in {\mathit{\boldsymbol{R}}^{{{m'}_i}}}, \;{{\mathit{\boldsymbol{M'}}}_{i \cdot }} \in {\mathit{\boldsymbol{R}}^{{{m'}_i} \times t}}$为M′中实体i拥有的等式和不等式约束条件所对应的行组成，即$\mathit{\boldsymbol{M' = }}\left[ \begin{array}{l} {{\mathit{\boldsymbol{M'}}}_{1 \cdot }}\\ \;\; \vdots \\ {{\mathit{\boldsymbol{M'}}}_{p \cdot }} \end{array} \right] \in {\mathit{\boldsymbol{R}}^{m' \times t}}$.

最后，通过产生随机矩阵隐藏线性规划(3)中实体i(i=1, …, p)的隐私信息.由上面可知V_i·=[A′_i·   M′_i·]∈R^{m′_i×(n+t)}为实体i(i=1, …, p)的隐私信息，由拥有V_i·的实体产生一个m′×m′_i随机矩阵B_·i，B_·i中的每个元素均匀分布在0, 1区间上且B_·i不公开.设

$ \mathit{\boldsymbol{B = }}\left[ {{\mathit{\boldsymbol{B}}_{ \cdot 1}} + \lambda {\mathit{\boldsymbol{E}}_1}\;\;\;{\mathit{\boldsymbol{B}}_{ \cdot 2}} + \lambda {\mathit{\boldsymbol{E}}_2}, \cdots , {\mathit{\boldsymbol{B}}_{ \cdot p}} + \lambda {\mathit{\boldsymbol{E}}_p}} \right], $

(4)

其中λ为实体i(1, …, p)共同商定的一个确定的较大的实数且λ≥n+t，E=[E₁E₂, …, E_p]为m′×m′阶单位矩阵，则B为可逆矩阵^[14].线性规划(3)中将B_·i+λE_i分别乘以每个实体的私有信息V_i·和b′_i，可得(B_·i+λE_i)V_i·和(B_·i+λE_i)b′_i.线性规划(3)即转化成为线性规划

$ \begin{array}{l} \min \;\mathit{\boldsymbol{z = }}{\mathit{\boldsymbol{C}}^{\rm{T}}}\mathit{\boldsymbol{X}}{\rm{, }}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\mathit{\boldsymbol{BA'X + BM'}}{\mathit{\boldsymbol{X}}_s} = \mathit{\boldsymbol{Bb'}}, \mathit{\boldsymbol{X}} \ge 0, {\mathit{\boldsymbol{X}}_s} \ge 0. \end{array} $

(5)

线性规划(5)对于隐藏实体i(i=1, …, p)的隐私信息是安全的，这是因为只有实体i知道Β_·i，其余实体在不知道Β_·i时无法从(B_·i+λE_i)V_i·和(B_·i+λE_i)b′_i中计算出V_i·和b′_i，所以线性规划(5)不泄露任何实体i(i=1, …, p)的隐私信息.由于B可逆，线性规划(5)和线性规划(3)是等价的.另外，各实体在增加人造约束条件和添加松弛变量时不改变原始线性规划模型(1)的可行域，可以证明，如果(X^*, (X_s^*))是线性规划(3)的最优解，那么X^*是线性规划的最优解.隐藏实体i(i=1, …, p)的隐私信息的具体算法见算法1.

算法1 基于水平数据分布的约束矩阵隐藏算法

Step1：实体i(i=1, …, p)根据原始的隐私约束条件在本地产生人造约束矩阵成为实体i新的隐私信息.

Step2：实体i(i=1, …, p)在本地添加松弛变量使隐私约束条件的不等式约束转化成等式约束，松弛变量系数为随机产生的正实数.

/*经过Step1和Step2后实体i(i=1, …, p)的隐私信息为A′_i·X+M′_i·X_s=b′_i*/

Step3：实体i(i=1, …, p)共同随机确定一个较大的实数λ(≥n+t).

Step4:由拥有隐私信息A′_i·X+M′_i·X_s=b′_i的实体i产生m′×m′_i阶随机矩阵B_·i，B_·i中的元素分布在区间0，1，且B_·i不公开.

Step5：实体1计算(B_·1+λE₁)[A′_1·   M′_1·   ]和(B_·1+λE₁)b′₁，并传送给实体2.

Step6：实体2计算(B_·1+λE₁)[A′_1·   M′_1·   ]+(B_·2+λE₂)[A′_2·   M′_2·]和(B_·1+λE₁)b′₁+(B_·2+λE₂)b′₂，并传送给实体3.

{以此类推}

……

Step p+4：实体p负责计算[BA′ BM′]=(B_·1+λE₁)[A′_1· M′_1·]+…+(B_·p+λE_p)[A′_p· M′_p·]和Bb′=(B_·1+λE₁)b′₁+…+(B_·p+λE_p)b′_p.

/*得到安全隐藏实体i(i=1, …, p)隐私信息的线性规划模型：min z=C^TX

$ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ \begin{array}{l} \left[ {\mathit{\boldsymbol{BA'BM'}}} \right]{\left[ {\mathit{\boldsymbol{X}}\;\;{\mathit{\boldsymbol{X}}_s}} \right]^{\rm{T}}} = \mathit{\boldsymbol{Bb'}}\\ \mathit{\boldsymbol{X}} \ge {\rm{0, }}{\mathit{\boldsymbol{X}}_s} \ge 0 \end{array} \right.\;\;*/. $

3.2 隐藏实体p+1的隐私信息

为了不泄露实体p+1的私有信息(C)，本文利用变换的思想隐藏C的具体信息，此方法最早是由Du针对线性方程组系统提出的^[15]，后来Du将其扩展到安全两方的线性规划模型^[16].由算法1可以知道，线性规划(5)中的BA′和BM′为i(i=1, …, p)的公开信息(因为任何实体i不能从BA′和BM′中推导出其他实体j(j=1, …, i-1, i+1, …, p)的隐私信息).显然

$ \begin{array}{l} \;\;\;\;\;{\mathit{\boldsymbol{C}}^{\rm{T}}}\mathit{\boldsymbol{Q}}{\mathit{\boldsymbol{Q}}^{ - {\rm{1}}}}\mathit{\boldsymbol{X = }}{\mathit{\boldsymbol{C}}^{\rm{T}}}\mathit{\boldsymbol{X}}, \\ \mathit{\boldsymbol{BA'Q}}{\mathit{\boldsymbol{Q}}^{ - 1}}\mathit{\boldsymbol{X}}{\rm{ + }}B\mathit{\boldsymbol{M'}}{\mathit{\boldsymbol{X}}_s} = \mathit{\boldsymbol{Bb'}} \Leftrightarrow \mathit{\boldsymbol{BA'X + BM'}}{\mathit{\boldsymbol{X}}_s} = \mathit{\boldsymbol{Bb'}}. \end{array} $

(6)

其中Q^-1(Q^-1∈R^n×n)的元素全为正实数，X≥0, X_s≥0.令U=BA′Q，U′= BM′，Y=Q^-1X，C′^T=C^TQ，则线性规划(5)转换成

$ \begin{array}{l} \min \;\mathit{\boldsymbol{z' = }}{{\mathit{\boldsymbol{C'}}}^{\rm{T}}}\mathit{\boldsymbol{Y}}{\rm{;}}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ \begin{array}{l} \mathit{\boldsymbol{UY}} + \mathit{\boldsymbol{U'}}{\mathit{\boldsymbol{X}}_s} = \mathit{\boldsymbol{Bb'}}, \\ \;\;\;\;\;\mathit{\boldsymbol{Y}} \ge {\rm{0, }}{\mathit{\boldsymbol{X}}_s} \ge {\rm{0}}{\rm{.}} \end{array} \right. \end{array} $

(7)

根据Du的方法，很容易证明如果(Y^*, (X_s^*))是线性规划(7)的最优解，那么(X^*, (X_s^*))(X^*=QY^*)为线性规划(5)的最优解(采用反正法).

由(6)可知，通过转化隐藏实体p+1隐私信息方法的核心在于如何在不泄露其他实体隐私信息的条件下得到C^TQ和BA′Q.根据矩阵理论，矩阵相乘可以拆分为多个向量的点积，即一个m×n阶矩阵乘以一个n×n阶矩阵相当于进行m×n次的两个向量的点积.可以很容易地将协议1中的安全两方点积协议扩展到矩阵相乘^[17].

假设由机器产生元素均为正实数的随机可逆矩阵Q，并将Q随机进行分解：Q=Q₁+Q₂(Q_i(i=1, 2)的元素均为正实数)，并将Q₁通过安全可信通道发送给实体p+1(令为P₁)，将Q₂发送给实体i(i=1, …, p)(此时可以把实体i(i=1, …, p)看成一个集体参与方，令为P₂).显然，任何实体都不知道Q的值，只有P₁和P₂合谋才能够得到Q的值.根据矩阵乘法BA′(Q₁+Q₂)= BA′Q₁+ BA′Q₂，首先P₂计算BA′Q₂，并对BA′Q₂和BA′的元素加密，将BA′Q₂和BA′的加密形式发送给P₁；根据同态加密的性质，P₁计算BA′Q₁的加密形式，然后计算BA′Q₁+ BA′Q₂的加密形式，并发送给P₂；最后P₂通过解密得到BA′Q.具体算法见算法2.同样在计算C^TQ时，P₁的输入为n×n阶矩阵Q₁和1×n阶矩阵C^T，P₂的输入为n×n阶矩阵Q₂，此时应由P₁产生一对公钥和私钥.通过把矩阵相乘转化成多个向量的点积，再利用安全点积协议就可以解决在不泄露双方隐私信息的情况下获得C^TQ和BA′Q.隐藏实体p+1的隐私信息的具体算法见算法2.

算法2 隐藏线性规划目标函数系数的隐私保护算法

P₁的输入为n×n阶矩阵Q₁.

P₂的输入为n×n阶矩阵Q₂和m′×n阶矩阵BA′(令BA′=H).

Step1：P₂产生一对私钥和公钥(sk，pk).

Step2: P₂将公钥sk发送给P₁.

Step3：P₂计算m′×n阶矩阵R=HQ₂.

Step4：P₂进行加密计算R′=Enc_pk(R).

Step5：P₂计算H′=Enc_pk(H).

Step6: P₂将R′和H′发送给P₁.

/*下面为P₁计算加密矩阵后S′的步骤*/

Step7:对于H′的每一行i和Q₁的每一列j进行下面循环：

Step9：P₁计算S′_ij=$\prod\limits_{k = 1}^n {\mathit{\boldsymbol{H'}}_{ik}^{{Q_{{1_{kj}}}}} \cdot {{\mathit{\boldsymbol{R'}}}_{ij}}} $.(其中下标表示所在行和列交叉处的元素)

{结束循环，P₁得到加密后的矩阵S′=(S′_ij)}

Step10：P₁将S′发送给P₂.

Step11：P₂进行解密计算S=Dec_sk(S′)= H(Q₁+Q₂)=BA′Q

4 安全性和有效性分析

在隐藏实体i(1≤i≤p)的隐私信息时，特别地让每个实体增加了人造约束条件且对于不等式约束转化成等式约束要求各实体增加多于1个的松弛变量，有效地减小了推断的可能性，尤其是当实体的个数p较小时，如若不增加人造约束条件和多个松弛变量，模型中的隐私信息很容易被推断出来.在算法1中各实体间只需进行2(p-1)次的信息交换并且各实体只需进行2次矩阵相乘计算，具有较高的效率.

算法2中的安全性取决于安全点积协议的安全性.对于一次安全点积过程需要2m′n次加密、n次幂运算和n次乘积运算，总共需要进行m′n次安全点积协议，即算法过程需要同时进行m′n²的幂运算和m′n²+mn的乘积运算.最后，需要进行m′n的解密运算才能够获得变形后的矩阵，相对于传统的安全多方计算方法具有较高的效率.

5 结论

实际应用中，例如生产运作管理和供应链管理中，存在着大量的优化决策问题.而线性规划模型是应用最为广泛的一种优化决策模型，并且模型数据的分布各种各样.本文针对线性规划约束矩阵数据水平分布且目标函数也为隐私信息的LP模型提出解决方案，此种情况在实际应用中也是广泛存在的.但是基于随机矩阵变换的方法隐藏实体的隐私信息的安全性有待进一步探讨，潜在的攻击仍然存在.本文提出的算法运用到实际应用中可能还存在很大的困难，但是为基于隐私保护的协同优化算法的研究提供了理论研究.另外，对于不同数据分布的线性规划很难提出一种通用的解决方案，只能针对特殊优化决策系统设计不同的解决方案.