在跨组织的协同优化决策中，常常表现为供应链管理中的生产计划问题、物流运输问题、库存优化问题、订单优化问题等.作为优化决策的一个重要分支，线性规划(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年，AliceBednarz等^[13]指出了利用Du^[3]或者Vaidyad^[7]的方法来解决隐私保护LP问题，得出的解也可能是不可行解.

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

考虑LP问题：{minc^Txs.t.Ax=b, x≥0}.在水平分区LP中，约束条件的A∈R^m×n和b∈R^m被水平分割成p个模块，并分别由p个参与者掌握：A_I1·, A_I2·, …, A_Ip·，b_I1, b_I2, …, b_Ip，其中A_Ii，b_Ii和下标索引I_i属于参与者i(i=1, 2, …, p).当所有参与者进行协同合作时，每个参与者i=1, 2, …, p都不想共享出自己的隐私数据块.因此，Mangasarian^[4]提出了一个转换的方法来解决这个问题：构造一个随机矩阵B∈R^k×m, k≥m，且rank(B)=m，这样就变成了一个新的LP问题，可表示为

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

在Mangasarian^[4]的PPHPLP算法中，每个参与者i=1, 2, …, p只公开了转换后的矩阵乘积B_·IiA_Ii·和转换后的向量B_·Iib_Ii来求解该问题.因此B_·Ii∈R^k×m_i，A_Ii和b_Ii还是隐私的.

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

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

其中x_s表示所有的松弛变量，且D=diag(D_I1, D_I2, …, D_Ip)∈R^m×m.如果(x^*, x_s^*)是转换后的LP问题(5) 的最优解，那么x^*就是原LP问题(4) 的最优解.

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

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

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

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

上述矩阵和向量中的元素是完全公开的.因此，Alice知道B_·I2A_I2·和B_·I2b_I2中有β₁α₁=0.4128，β₁α₂=1.2654，β₁α₃=-0.8436和β₁δ=0.4218，那么Alice可以很快地计算出α₁:α₂:α₃:δ=1:3:(-2):1.虽然Alice并不能推断出α₁, α₂, α₃, δ精确值，但是她完全可以用α₁:α₂:α₃:δ=1:3:(-2):1来重构约束条件x₁+3x₂-2x₃≤1.

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

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

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

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

Alice掌握m₁个约束条件${\mathit{\boldsymbol{\bar M}}_1}\mathit{\boldsymbol{x}} \le {\mathit{\boldsymbol{\bar b}}_1}$，Bob掌握m₂个约束条件${\mathit{\boldsymbol{\bar M}}_2}\mathit{\boldsymbol{x}} \le {\mathit{\boldsymbol{\bar b}}_2}$，且x∈R^n×1.Alice和Bob共同求解以下问题：

该问题共有m=m₁+m₂个约束条件，其中Alice掌握$ {\mathit{\boldsymbol{M}}_1}=\left( \begin{array}{l} {{\mathit{\boldsymbol{\bar M}}}_1}\\ \;\;0 \end{array} \right)\in {{\bf{R}}^{m \times n}}, {\mathit{\boldsymbol{b}}_1}=\left( \begin{array}{l} {{\mathit{\boldsymbol{\bar b}}}_1}\\ \;0 \end{array} \right)\in {{\bf{R}}^{n \times 1}} $，Bob掌握$ {\mathit{\boldsymbol{M}}_2}=\left( \begin{array}{l} \;\;0\\ {{\mathit{\boldsymbol{\bar M}}}_2} \end{array} \right)\in {{\bf{R}}^{m \times n}}, {\mathit{\boldsymbol{b}}_2}=\left( \begin{array}{l} \;0\\ {{\mathit{\boldsymbol{\bar b}}}_2} \end{array} \right)\in {{\bf{R}}^{n \times 1}} $以及目标函数的参数c∈R^n×1.

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

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

$ \begin{array}{l} {\mathit{\boldsymbol{C}}^{\rm{T}}}=\left( {{\mathit{\boldsymbol{c}}^{\rm{T}}}\vdots{{\bf{0}}^{\rm{T}}}} \right)\in {{\bf{R}}^{l+\left( {m+n} \right)}}, \mathit{\boldsymbol{X}}=\left( \begin{array}{l} \mathit{\boldsymbol{x}}\\ {\mathit{\boldsymbol{x}}_s} \end{array} \right)\in {{\bf{R}}^{\left( {n+m} \right)\times 1}}, {\mathit{\boldsymbol{N}}_1}+{\mathit{\boldsymbol{N}}_2}=\left( {{\mathit{\boldsymbol{M}}_1}+{\mathit{\boldsymbol{M}}_2} \vdots \mathit{\boldsymbol{I}}} \right), 其中{\mathit{\boldsymbol{N}}_1}=\left( \begin{array}{l} \begin{array}{*{20}{c}} {{{\mathit{\boldsymbol{\bar M}}}_1}}&{{\mathit{\boldsymbol{I}}_{{m_1}}}}&0 \end{array}\\ \begin{array}{*{20}{c}} \;\;0&\;\;\;\;0&\;\;0 \end{array} \end{array} \right), \\ {\mathit{\boldsymbol{N}}_2}=\left( \begin{array}{l} \begin{array}{*{20}{c}} \;\;0&\;\;0&\;0 \end{array}\\ \begin{array}{*{20}{c}} {{{\mathit{\boldsymbol{\bar M}}}_2}}&0&{{\mathit{\boldsymbol{I}}_{{m_2}}}} \end{array} \end{array} \right), \mathit{I}{\text{为}m\text{阶单位矩阵}}\mathit{.} \end{array} $.

本文进行一个等价的转换(N₁+N₂)X=b₁+b₂⇔K(N₁+N₂)QQ^-1X=K(b₁+b₂)，将原LP问题转变成如下形式：

Bob随机选择可逆矩阵K∈R^m×m和广义置换矩阵Q∈R^(m+n)×(m+n)(Q和Q^-1中所有元素均为非负数).Alice知道$ \mathit{\boldsymbol{\hat N}}=\mathit{\boldsymbol{K}}\left( {{\mathit{\boldsymbol{N}}_1}+{\mathit{\boldsymbol{N}}_2}} \right)\mathit{\boldsymbol{Q}}, \mathit{\boldsymbol{\hat b}}=\mathit{\boldsymbol{K}}\left( {{\mathit{\boldsymbol{b}}_1}+{\mathit{\boldsymbol{b}}_2}} \right){\rm{和}}{{\mathit{\boldsymbol{\hat C}}}^{\rm{T}}}={\mathit{\boldsymbol{C}}^{\rm{T}}}\mathit{\boldsymbol{Q}}, $这样，就可以求解LP问题：$ \left\{ {\min :{{\mathit{\boldsymbol{\hat C}}}^{\rm{T}}}\mathit{\boldsymbol{\hat X}}{\rm{s}}{\rm{.t}}{\rm{.}}\mathit{\boldsymbol{\hat N\hat X=\hat b, \hat X}} \ge \mathit{\boldsymbol{0}}} \right\}, $得出最优解$ {{\mathit{\boldsymbol{\hat X}}}^\mathit{\boldsymbol{*}}} $和最优值$ {{\mathit{\boldsymbol{\hat f}}}^\mathit{\boldsymbol{*}}} $.Alice将$ {{\mathit{\boldsymbol{\hat X}}}^\mathit{\boldsymbol{*}}} $和$ {{\mathit{\boldsymbol{\hat f}}}^\mathit{\boldsymbol{*}}} $都发送给Bob，Bob计算X^*=Q$ {{\mathit{\boldsymbol{\hat X}}}^\mathit{\boldsymbol{*}}} $和v=N₂X-b₂，并将结果发送给Alice.该协议的详细过程如下.

协议：Alice掌握矩阵N₁和向量b₁，Bob掌握矩阵N₂和向量b₂，N₁, N₂∈R^m×(m+n)，b₁, b₂∈R^n×1.(1) Alice和Bob通过添加松弛变量将他们的约束转换成等式形式：

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

(3) 利用协议1(章节2.2.2)，Alice和Bob计算$ \mathit{\boldsymbol{\hat N}} $=K(N₁+N₂)Q，且只有Alice得到$ \mathit{\boldsymbol{\hat N}} $；

(4) 利用协议2(章节2.2.2)，Alice和Bob计算$ \mathit{\boldsymbol{\hat b}} $=K(b₁+b₂)，且只有Alice得到$ \mathit{\boldsymbol{\hat b}} $；

(5) Bob本地计算$ \mathit{\boldsymbol{\hat C}} $ ^T=C^TQ，并发送给Alice；

(6) Alice掌握了求解{min:$ \mathit{\boldsymbol{\hat C}} $^T$ \mathit{\boldsymbol{\hat X}} $s.t.$ \mathit{\boldsymbol{\hat N}}\mathit{\boldsymbol{\hat X}} $=$ \mathit{\boldsymbol{\hat b}} $, $ \mathit{\boldsymbol{\hat X}} $≥0}的所有条件，这样他就能得出最优解$ {{\mathit{\boldsymbol{\hat X}}}^\mathit{\boldsymbol{*}}} $和最优值$ {{\mathit{\boldsymbol{\hat f}}}^\mathit{\boldsymbol{*}}} $.Alice将$ {{\mathit{\boldsymbol{\hat X}}}^\mathit{\boldsymbol{*}}} $和$ {{\mathit{\boldsymbol{\hat f}}}^\mathit{\boldsymbol{*}}} $都发送给Bob.注意$ {{\mathit{\boldsymbol{\hat f}}}^\mathit{\boldsymbol{*}}} $=f^*，因为$ \mathit{\boldsymbol{\hat C}} $^T$ \mathit{\boldsymbol{\hat X}} $=C^TQQ^-1X=C^TX；

(7) Bob计算X^*=Q$ {{\mathit{\boldsymbol{\hat X}}}^\mathit{\boldsymbol{*}}} $和v=N₂X-b₂，并将结果发送给Alice.

(8) Alice通过(N₁X-b₁)+v是否等于0, 或是否在可接受范围内趋近于0(如果存在不可避免的计算误差)，来验证X^*是否真实的最优解.

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

在上述问题的约束条件中加入松弛变量x₄, x₅, x₆，得到：

其中Alice掌握

$ {\mathit{\boldsymbol{N}}_1}=\left( \begin{array}{l} \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\;1}&{ - 2}&{\;1} \end{array}}&{\;\;1}&\;0&0 \end{array}\\ \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\;5}&{ - 1}&{ - 2}&\;0 \end{array}}&1&0 \end{array}\\ \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\;\;\;0}&0&{\;\;0} \end{array}}&{\;\;0}&\;0&0 \end{array} \end{array} \right), {\mathit{\boldsymbol{b}}_1}=\left( {\begin{array}{*{20}{c}} {11}\\ 1\\ 0 \end{array}} \right);\\ {\rm{Bob}}掌握 {\mathit{\boldsymbol{N}}_2}=\left( \begin{array}{l} \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\;\;0}&{\;0}&0 \end{array}}&0&\;0&0 \end{array}\\ \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\;\;0}&{\;0}&0&\;0 \end{array}}&0&0 \end{array}\\ \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} { - 2}&1&1 \end{array}}&{\;0}&0&1 \end{array} \end{array} \right), {\mathit{\boldsymbol{b}}_2}=\left( {\begin{array}{*{20}{c}} 0\\ 0\\ 0 \end{array}} \right);和{\mathit{\boldsymbol{C}}^{\rm{T}}}=\left( {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} { - 3}&1&1 \end{array}}&0&0&0 \end{array}} \right)\cdot $

该LP问题的最优解是X^*=(1 0 2 8 0 0)^T，最优值是f^*=-1.

根据协议，Bob生成随机可逆矩阵K∈R^m×m和严格正定矩阵Q∈R^(m+n)×(m+n)，$ \begin{array}{l} \mathit{\boldsymbol{K}}=\left( \begin{array}{l} \begin{array}{*{20}{c}} 8&9&3 \end{array}\\ \begin{array}{*{20}{c}} 9&6&5 \end{array}\\ \begin{array}{*{20}{c}} 1&1&{10} \end{array} \end{array} \right) \mathit{\boldsymbol{Q=}}\left( \begin{array}{l} \begin{array}{*{20}{c}} 6&0&0&{\begin{array}{*{20}{c}} 0&0&0 \end{array}} \end{array}\\ \begin{array}{*{20}{c}} 0&0&0&{\begin{array}{*{20}{c}} 0&5&0 \end{array}} \end{array}\\ \begin{array}{*{20}{c}} 0&0&0&{\begin{array}{*{20}{c}} 0&0&3 \end{array}} \end{array}\\ \begin{array}{*{20}{c}} 0&0&0&{\begin{array}{*{20}{c}} 2&0&0 \end{array}} \end{array}\\ \begin{array}{*{20}{c}} 0&0&8&{\begin{array}{*{20}{c}} 0&0&0 \end{array}} \end{array}\\ \begin{array}{*{20}{c}} 0&1&0&{\begin{array}{*{20}{c}} 0&0&0 \end{array}} \end{array} \end{array} \right)\cdot {\rm{Bob计算}}{{\mathit{\boldsymbol{\hat C}}}^{\rm{T}}}={\mathit{\boldsymbol{C}}^{\rm{T}}}\mathit{\boldsymbol{Q=}}\left( {\begin{array}{*{20}{c}} { - 18}&0&0&{\begin{array}{*{20}{c}} 0&5&3 \end{array}} \end{array}} \right), \end{array} $并发送给Alice.Alice和Bob共同计算K(N₁+N₂)Q和K(b₁+b₂)，且只有Alice得到结果，并求解下面的LP问题：

其最优解是$ {\mathit{\boldsymbol{\hat X}}^*}={\left( {\begin{array}{*{20}{c}} {\frac{1}{6}}&0&0&{\begin{array}{*{20}{c}} 4&0&{\frac{2}{3}} \end{array}} \end{array}} \right)^{\rm{T}}}, $最优值是$ {\mathit{\boldsymbol{\hat f}}^*} $=-1.

本文所用到的协议是在Du^[1]和Yang等人^[16]的基础上提出的，并做了一个重要的修改以提高协议的效率.在原协议中，p和d是安全参数，且p^d要足够大以至于打破安全性所花费的成本在计算上不可行的.但是，这就使该算法的成本非常昂贵.因此，这里选择的p和d只要让Bob推测到Alice的数据的概率$ {\frac{1}{p^d}} $是在可接受的低水平范围内即可.此外，本文也对协议进行了修改，使得Bob即便是估算出Alice矩阵的所有可能性(p^d次)，但在他看来这些矩阵都是一样的.而在原协议中，如果Alice的矩阵中有一个已知零结构，那么p^d次可能性矩阵就很有可能不是相等的，即正确的矩阵将是显而易见的.

协议1：  安全求$ \mathit{\boldsymbol{\hat N}} $ =K(N₁+N₂)Q

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

协议1  安全求$ \mathit{\boldsymbol{\hat N}} $ =K(N₁+N₂)Q

输入：  Alice拥有隐私矩阵$ {\mathit{\boldsymbol{\bar M}}_1} \in {{\bf{R}}^{{m_1} \times n}}, $储存在N₁；Bob拥有隐私矩阵$ {\mathit{\boldsymbol{\bar M}}_2} \in {{\bf{R}}^{{m_2} \times n}}, $储存在N₂，随机矩阵K∈R^m×m以及非负广义置换矩阵Q∈R^(n+m)×(n+m).矩阵N₁, N₂的结构如下：

$ {\mathit{\boldsymbol{N}}_{\rm{1}}}\mathit{\boldsymbol{=}}\left( \begin{array}{l} \begin{array}{*{20}{c}} {{{\mathit{\boldsymbol{\bar M}}}_1}}&{{\mathit{\boldsymbol{I}}_{{m_1}}}}&0 \end{array}\\ \begin{array}{*{20}{c}} {\;0}&{\;\;\;\;\;0}&{\;\;0} \end{array} \end{array} \right), {N_2}=\left( \begin{array}{l} \begin{array}{*{20}{c}} {\;0}&{\;\;\;\;0}&{\;0} \end{array}\\ \begin{array}{*{20}{c}} {{{\mathit{\boldsymbol{\bar M}}}_2}}&0&{{\mathit{\boldsymbol{I}}_{{m_2}}}} \end{array} \end{array} \right)\cdot $N₁的子秘密将表示成$ {{\mathit{\boldsymbol{\bar X}}}_{i}} $, i=1, 2, …, d.

输出：  Alice获得$ \mathit{\boldsymbol{\hat N}} $ =K(N₁+N₂)Q，而Bob得不到任何输出.

协议：

(1) Alice和Bob约定两个数p和d，使得Bob推测到Alice的数据的概率$ {\frac{1}{p^d}} $在可接受的低水平范围内.

(2) Alice生成随机矩阵X₁, X₂, …, X_d-1∈R^m₁×n，使$ {\mathit{\boldsymbol{\bar X}}_d}={\mathit{\boldsymbol{\bar M}}_1} - \sum\limits_{\mathit{\boldsymbol{i}}{\bf{=1}}}^{\mathit{\boldsymbol{d}}{\bf{ - 1}}} {{{\mathit{\boldsymbol{\bar X}}}_i}} ; $

(3) Bob生成随机矩阵Y₁, Y₂, …, Y_d-1∈R^m₂×n，使$ {\mathit{\boldsymbol{Y}}_d}={\mathit{\boldsymbol{N}}_2} - \sum\limits_{\mathit{i}{\rm{=1}}}^{\mathit{d}{\rm{ - 1}}} {{{\mathit{\boldsymbol{Y}}}_\mathit{i}}} ; $

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

① Alice生成p-1个随机矩阵G_i^(j)∈R^m₁×n，并将下面的序列发送给Bob：

$ \left( {\mathit{\boldsymbol{\bar H}}_1^{\left( j \right)}, \mathit{\boldsymbol{\bar H}}_2^{\left( j \right)}, \cdot \cdot \cdot, \mathit{\boldsymbol{\bar H}}_p^{\left( j \right)}} \right), $其中H_k^(j)=x_j，秘密数k∈[1, p]是Alice随机产生的，且只有她自己知道，G_i^(j)被分配到剩余的p-1个H_i^(j), i≠k.

② Bob“填写”H_i^(j)生成H_i^(j).

“填写”过程：Bob添加一个m₁×m₁阶的$ {\frac{1}{d}} $单位矩阵和一个m₁×m₂的零矩阵到H_i^(j)，并在H_i^(j)下面插入一个m₂×(m+n)的零矩阵，即

对所有的i=1, 2, …, p，Bob计算Z_i^(j)=K(H_i^(j)+Y_j)Q+R_j，其中R_j∈R^m×(m+n)是Bob生产的随机矩阵.

③ 利用不经意传输协议OT₁^N，Alice取回计算结果：

Z_k^(j)=K(H_k^(j)+Y_j)Q+R_j=K(X_j+Y_j)Q+R_j.

(5) Bob计算$ \sum\limits_{j=1}^d {{\mathit{\boldsymbol{R}}_j}} $，并发送给Alice.

(6) Alice计算

$ \begin{array}{l} {{\mathit{\boldsymbol{\hat N}}}^ = }\sum\limits_{j = 1}^d {Z_k^{(j)}} - \sum\limits_{j = 1}^d {{{\bf{R}}_j}} = \\ \sum\limits_{j = 1}^d {\left( {\mathit{\boldsymbol{K}}\left( {{\mathit{\boldsymbol{X}}_j} + {\mathit{\boldsymbol{Y}}_j}} \right)\mathit{\boldsymbol{Q}} + {{\bf{R}}_j}} \right)} - \sum\limits_{j = 1}^d {{{\bf{R}}_j}} = \mathit{\boldsymbol{K}}\left( {{\mathit{\boldsymbol{N}}_1} + {\mathit{\boldsymbol{N}}_2}} \right)\mathit{\boldsymbol{Q}} \cdot \end{array} $

协议2  安全求$ \mathit{\boldsymbol{\hat b}}=\mathit{\boldsymbol{K}}\left( {{\mathit{\boldsymbol{b}}_1}+{\mathit{\boldsymbol{b}}_2}} \right)$

输入：  Alice拥有m₁维隐私向量b₁；Bob拥有m₂维隐私向量b₂和随机矩阵K∈R^m×m，且

$ {\mathit{\boldsymbol{b}}_1}+{\mathit{\boldsymbol{b}}_2}=\left( \begin{array}{l} {{\mathit{\boldsymbol{\bar b}}}_1}\\ 0 \end{array} \right)+\left( \begin{array}{l} 0\\ {{\mathit{\boldsymbol{\bar b}}}_2} \end{array} \right)\cdot $

输出：  Alice获得$ \mathit{\boldsymbol{\hat b}}=\mathit{\boldsymbol{K}}\left( {{\mathit{\boldsymbol{b}}_1}+{\mathit{\boldsymbol{b}}_2}} \right)$，而Bob得不到任何输出.

协议：  该协议是协议1的一种特殊情况，即Q=I.同时，“填写”过程也更加简单，因为不需要向向量中添加单位矩阵.Bob只需要将m₂维的零向量添加到b₁.

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

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

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

转换阶段只需要两个子协议.在每个子协议中，p和d是安全参数，而$ {\frac{1}{p^d}} $是Bob推测到Alice隐私数据的概率，选择的p和d只要让这个概率在可接受的低水平范围内即可.每个协议都有一个线性代数的开销和一个基于不经意传输协议OT₁^N的加密算法(在本文的协议中N=p).所有值的位长度k是一个常数，因此可以忽略.Naor和Pinkas^[17]的研究中指出不经意传输协议OT₁^N的计算成本是logN，通信成本是O(N).

每个子协议需要进行d轮；在每轮中都要执行一次不经意传输协议OT₁^N.下面依次来说明每个子协议的计算复杂度.

协议1  安全求$ \mathit{\boldsymbol{\hat N}}=\mathit{\boldsymbol{K}}\left( {{\mathit{\boldsymbol{N}}_1}{\bf{+}}{\mathit{\boldsymbol{N}}_2}} \right)\mathit{\boldsymbol{Q}} $.总共需要pd(m²(n+m)+m(n+m)²)次乘法.在d轮通信中，每一轮都要用一次不经意传输协议OT₁^N来传送一个m×(n+m)阶的矩阵.

协议2  安全求$ \mathit{\boldsymbol{\hat b}}=\mathit{\boldsymbol{K}}\left( {{\mathit{\boldsymbol{b}}_1}+{\mathit{\boldsymbol{b}}_2}} \right)$.该算法需要pdm²次乘法.在d轮通信中，每一轮都要用一次不经意传输协议OT₁^N来传送一个m维的向量.

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

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

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