组织之间的协同管理决策就是利用各组织甚至个人的信息，协同制订全局优化决策问题的解决方案.然而组织间的管理或运营数据，不仅仅存在分布性、异构性等大数据的特点，关键还涉及到众多组织不愿意公开的信息，通常称这类信息为“隐私信息”^[1].如何保护好各自的隐私信息，又能完成协同决策问题，是大数据时代典型的组织协同优化决策问题的重要难题.

在供应链管理中，有联合库存管理(JMI)问题，产能约束下多个零部件的协同决策问题等等^[2-6].但在联合优化决策时，无论是目标函数还是约束条件，可能需要使用到不同组织间的数据，如上下游企业或合同企业的资金、人员、生产能力与库存情况等.在供应链的上下游企业中并不愿意提供本组织内的真实数据给对方，也不愿意将数据交给所谓的“可信”第三方进行计算，因此，如何设计一个“好的”的协同分析机制，在不泄露原始数据的前提下，去完成协同优化决策问题.这就是保护组织隐私数据的协同决策问题^[7].

安全多方计算(Secure Multi-party Computation，以下简称SMC)是目前解决大数据环境下这一类隐私保护计算问题的方法之一^[8].安全多方计算这个概念最早是由图灵奖获得者Yao A C^[9]于1982年提出的，即广为人知的百万富翁问题.Goldreich、Micali和Wigderson将其理论扩展，给出了一般的描述^[10].由于安全多方计算具有广泛的应用前景，目前许多国内外专家都致力于安全多方计算的研究.人们都知道在SMC理论上，最有名的构造方法就是单调张成方法^[11]，它是通过存取结构(Access Structure)来给出安全多方协议的通用构造矩阵，然而在实际应用时，该方法有着明显的缺点，就是计算复杂度太高，以至于实际应用时难以按这一思路来设计合作机制.因此近年来学者针对不同的应用提出各种具体构造安全多方协议的方法，如Du对科学计算问题就提出了一些高效的安全多方协议，但是科学计算问题的结构是无穷的，Du的方法目前对简单的线性方程是有效的，对于其他系统，如动态系统、优化问题等就未必有效了^[12].在国内，比较多的研究是针对供应链上的协同计算问题来研究，如供应链的订货管理^[13]，但该文只是针对一个成本函数来分析，没有考虑约束，因此，在得到成本函数的解析解后，再使用同态加密算法，这样处理方法还相对容易，加上同态算法的复杂度较高，使得实际效率不高.

在本文中，主要对组织间的决策机制分为异构与同构两种情况，并分别研究两种情况下的安全多方计算协议，及对它们的安全性给出证明.

1 基本概念与问题的提出 1.1 半诚实模型下的安全性定义

本节给出了半诚实模型下的两方计算的安全性定义^[6]，多方计算的安全性定义可以类推.

在半诚实模型中，一个半诚实参与方在执行协议的过程中会忠实地履行协议，但他可能会保留所有中间结果，试图从中间结果推导出协议之外的信息.

设f:{0, 1}^*×{0, 1}^*→{0, 1}^*×{0, 1}^*是一个函数，f₁(x, y)和f₂(x, y)分别代表函数f(x, y)的第一个和第二个元素.∏是计算函数f的两方协议.协议的输入(x, y)，执行协议∏时，参与方p₁(p₂)得到的信息记作

$ \begin{array}{l} {\rm{VIEW}}_1^\Pi \left( {x, y} \right) = \\ \left( {x, {r^1}, m_1^1, \cdots, m_t^1} \right)\left( {{\rm{VIEW}}_2^\Pi \left( {x, y} \right) = \left( {x, {r^2}, m_1^2, \cdots, m_t^2} \right)} \right), \end{array} $

其中rⁱ(i=1, 2)是参与方p_i产生的随机数，m_i¹(m_i²)是参与方p₁(p₂)接收到的第i个消息.OUTPUT_i^∏(x, y)(i=1, 2)表示p_i方的输出结果，显然它是VIEW_i^∏(x, y)的一部分.

定义1 若存在多项式时间算法S₁与S₂使得下面两个公式成立，则π能保密地计算f.

$ \begin{array}{l} {\left\{ {\left( {{S_1}\left( {x, {f_1}\left( {x, y} \right)} \right), {f_2}\left( {x, y} \right)} \right)} \right\}_{x, y \in {{\left\{ {0, 1} \right\}}^*}}}\mathop \equiv \limits^c \\ {\left\{ {\left( {{\rm{VIEW}}_1^\Pi \left( {x, y} \right), {\rm{OUTPUT}}_2^\Pi \left( {x, y} \right)} \right)} \right\}_{x, y \in {{\left\{ {0, 1} \right\}}^*}}}, \end{array} $

(1)

$ \begin{array}{l} {\left\{ {\left( {{f_1}\left( {x, y} \right), {S_1}\left( {y, {f_2}\left( {x, y} \right)} \right)} \right)} \right\}_{x, y \in {{\left\{ {0, 1} \right\}}^*}}}\mathop \equiv \limits^c \\ {\left\{ {\left( {{\rm{OUTPUT}}_1^\Pi \left( {x, y} \right){\rm{VIEW}}_2^\Pi \left( {x, y} \right)} \right)} \right\}_{x, y \in {{\left\{ {0, 1} \right\}}^*}}}, \end{array} $

(2)

其中，$\mathop \equiv \limits^c $表示计算不可区分，而且VIEW₁^∏(x, y)和VIEW₂^∏(x, y)，OUTPUT₁^∏(x, y)和OUTPUT₂^∏(x, y)是相关的随机变量.

1.2 同态加密

同态加密的概念是由Rivest、Adleman和Dertouzos于1978年提出的.同态加密的特殊性质使我们可以直接对密文进行某些运算来代替对明文的运算取得同样的效果，这样不影响明文数据的机密性.Paillier算法就是一种同加密算法^[14]，它有两个重要的性质：

(1) E(m₁)⊕E(m₂)=g^m₁+m₁(r₁r₂)^NmodN²=E(m₁+m₂)；

(2) E(m₁)^m₂=g^m₁m₁(r^m₂)^NmodN²=E(m₁m₂).

1.3 协同优化决策的模型

本文主要针对大数据环境下的优化问题来研究各合作方的安全多方计算问题：

$ \left. \begin{array}{l} {\rm{opt}}\;\xi {\rm{ = }}g\left( z \right), \\ {\rm{s}}{\rm{.t}}{\rm{.}}\;f\left( z \right) = 0. \end{array} \right\} $

(3)

下面给出协同优化决策时两类优化问题的安全多方计算问题.

1.3.1 决策变量同构时的优化决策问题

设参与协同决策的决策方分别是P₁, P₂, …, P_n，共同求解以下问题：

$ \left. \begin{array}{l} {\rm{opt}}\;\xi {\rm{ = }}g\left( {z, c} \right), \\ {\rm{s}}{\rm{.t}}{\rm{.}}\;f\left( {z, {\alpha _1}, {\alpha _2}, \cdots, {\alpha _n}} \right) = 0. \end{array} \right\} $

(4)

隐私假设：

(1) 决策变量是各方共享的；

(2) α_i是P_i的隐私参数；

(3) 目标函数的参数c是共享的.

1.3.2 决策变量异构时的优化决策问题

设参与方仍是P_i(i=1, 2, …, n)，优化问题的结构如下：

$ \left. \begin{array}{l} {\rm{opt}}\;\xi {\rm{ = }}g\left( {{z_1}, {z_2}, \cdots, {z_n}, c} \right), \\ {\rm{s}}{\rm{.t}}{\rm{.}}\;f\left( {{z_i}, {\alpha _i}} \right) = 0\;\;\;i = 1, 2, \cdots n. \end{array} \right\} $

(5)

隐私假设：

(1) z_i是P_i的隐私决策变量；

(2) α_i是P_i的隐私参数；

(3) 目标函数的参数c是共享的.

本文的后半部分将对以上两类问题的安全多方计算问题进行分析，并结合安全性证明.

2 约束同构时安全多方计算 2.1 模型与假设

本节研究在半诚实模型下的约束同构的线性优化问题(本文只考虑存在最优解的安全多方计算，后面的计算亦是如此)，其数学模型如下：

$ \begin{array}{l} {\rm{max}}\;\xi {\rm{ = }}{\mathit{\boldsymbol{C}}^{\rm{T}}}\mathit{\boldsymbol{X}}, \\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ \begin{array}{l} {\left( {\mathit{\boldsymbol{A}}_1^{\rm{T}}, \mathit{\boldsymbol{A}}_2^{\rm{T}}, \cdots, \mathit{\boldsymbol{A}}_n^{\rm{T}}} \right)^{\rm{T}}}\mathit{\boldsymbol{X}} = {\left( {\mathit{\boldsymbol{b}}_1^{\rm{T}}, \mathit{\boldsymbol{b}}_2^{\rm{T}}, \cdots, \mathit{\boldsymbol{b}}_n^{\rm{T}}} \right)^{\rm{T}}}, \\ \mathit{\boldsymbol{X}} \ge 0. \end{array} \right. \end{array} $

(6)

假设：

(1) C, X ∈ Rⁿ为共享信息；

(2) P_i的隐私信息A_i, b_i，其中A_i∈ R^m_i×n，b_i∈ R^m_i, (一般m₁+m₂+…+m_n≤n).

2.2 模型(6)的安全多方协议

模型(6)用单纯形法求解的计算步骤如下：

Step1：找出初始可行基，确定初始基可行解，建立初始单纯形表.

Step2：在不泄漏隐私信息的情况下，P₁, P₂, …, P_n协同检查各非基变量的检验数，若σ≤0，则已得到最优解，计算结束.否则转入下一步.

Step3：根据max(σ)>0，确定了换入变量后，按照$\mathit{\boldsymbol{\theta }} = \mathop {\min }\limits_i \left( {\frac{{{{\left( {{\mathit{\boldsymbol{B}}^{-1}}\mathit{\boldsymbol{b}}} \right)}_i}}}{{{{\left( {{\mathit{\boldsymbol{B}}^{-1}}{P_j}} \right)}_i}}}\left| {{{\left( {{\mathit{\boldsymbol{B}}^{-1}}{P_j}} \right)}_i} > 0} \right.} \right) $，每个参与方P_i独自计算θ_i，并选出各自的min(θ_i)，在不泄露各自信息的情况下，安全比较其大小，确定换出变量，替换后得到新基变量，再入下一步.

Step4：求出新基变量以及新基变量对应的基可行解，得到新的单纯形表.

Step5：重复Step2~Step4，直到终止.

2.2.1 关于Step2的安全多方协议

参与方P_i隐私数据x_i，它们要共同计算$y = \sum\limits_{i = 1}^n {{x_i}} $，但任何一个参与方都不愿意向其他参与方泄漏自己的私有输入x_i.在此情况下，本文设计了一个基于Paillier算法的安全多方计算协议来完成这个计算任务.

协议1  安全多方求和问题的解决方案

输入：参与方P_i拥有隐私数据为x_i

输出：$y = \sum\limits_{i = 1}^n {{x_i}} $

(1) 若n为偶数，将n个参与者随机分成A和B组，对其重新编号，即A={A₁, A₂, …, A_k}，B={B₁, B₂, …, B_k}(${k = \frac{n}{2}}$)，其中A_i和B_i的隐私数据分别标记为a_i, b_i，即$y = \sum\limits_{i = 1}^n {{x_i}} = \sum\limits_{i = 1}^k {{a_i}} + \sum\limits_{i = 1}^k {{b_i}} $.

① 假设(G, E, D)是Paillier同态加密方案，τ是设定的安全参数.参与方A_i运行G(τ)生成同态加密方案的公钥和密钥，用公钥加密a_i得到密文E(a_i)；

② 将E(x_i)与公钥一起发送给B_i；

③ B_i选择一个随机数r_i，计算

E(a_i+b_i)=(r_i^NE(a_i)^b_i)modN²；

④ 将计算结果E(a_i+b_i)发送给A_i

⑤ A_i用私钥解密E(a_i+b_i)得到a_i+b_i，参与者集合A共同计算$y = \sum\limits_{i = 1}^n {{x_i}} = \sum\limits_{i = 1}^k {{a_i}} + \sum\limits_{i = 1}^k {{b_i}} $，并把$\sum\limits_{i = 1}^n {{x_i}} $公开.

(2) 若n为奇数，则再增加一个虚拟参与者P_n+1，他拥有的隐私数据为0，这样可以参照上面的协议来完成这个计算任务.

2.2.2 关于Step3的安全多方计算

参与方P_i拥有隐私数据x_i=min(θ_i)，它们希望知道哪个x_i最小，但又不愿意泄漏各自的x_i.在此情况下, 探讨如何安全地进行比较.为了提高计算效率，本文将安全多方比较问题转换成多个安全两方比较问题，进而得到最终的计算结果.因此，这个计算问题可以归约为参与方A与B的隐私数据x与y的大小比较问题.

首先对保密的数据进行编码，不失一般性，假设x, y∈{w₁, w₂, …, w_m}= U, 其中w₁ < w₂ < … < w_m.进一步假设x=w_k，y=w_l，(1≤k, l≤m)，那么x≤y当且仅当k≤l.解决方案基于下面的的观察：

根据x，y和U, 构造两个新的向量A =(a₁, a₂, …, a_m)，B =(b₁, b₂, …, b_m)，其中${a_i} = \left\{ \begin{array}{l} 0, \;\;i < k\\ 1, \;\;i \ge k \end{array} \right.$，即a₁=a₂=…=a_k-1=0，a_k=a_k+1=…=a_m=1；类似地, ${b_j} = \left\{ \begin{array}{l} 0, \;\;j < l\\ 1, \;\;j \ge l \end{array} \right.$.如果x≤y，那么k≤l，b₁=b₂=…=b_l-1=0，a_l=b_l=1，则$v = \sum\limits_{i = 1}^l {{a_i}{b_i}} = \sum\limits_{i = 1}^{k-1} {{a_i}{b_i}} + \sum\limits_{i = k}^{l-1} {{a_i}{b_i} + {a_l}{b_l} = 1} $；

反之，如果x>y，那么k>l，a₁=a₂=…=a_l=0，则$v = \sum\limits_{i = 1}^l {{a_i}{b_i}} = 0$.

因此保密地比较x, y的大小可以归约到保密计算$\sum\limits_{i = 1}^l {{a_i}{b_i}} $.为了便于论述，定义P(x, y)如下：如果x≤y，P(x, y)=1；否则P(x, y)=0.用Paillier算法可以完成这个计算任务.

协议2  安全两方比较问题的解决方案

输入：参与方A的隐私数据为x，参与方B的隐私数据为y，设{x, y∈w₁, w₂, ···, w_m}=U.

输出：P(x, y).

(1) 设x=r_k，y=r_l，参与方A和B分别构造两个向量A=(a₁, a₂, ···, a_m)，B=(b₁, b₂, ···, b_m)，其中

$ {a_i} = \left\{ \begin{array}{l} 0, \;\;i < k\\ 1, \;\;\;i \ge k \end{array} \right., {b_j} = \left\{ \begin{array}{l} 0, \;\;\;j < l\\ 1, \;\;\;j \ge l \end{array} \right.. $

(2) 假设(G, E, D)是Paillier同态加密方案，τ是设定的安全参数.参与方A运行G(τ)生成同态加密方案的私钥和公钥，用公钥加密向量A得到E(A)=(E(a₁), E(a₂), …, E(a_m)).

(3) 将E(A)与公钥一起发送给Bob.

(4) 参与方B选择一个随机数r，计算

$ E\left( v \right) = \left( {{r^N}\prod\limits_{i = 1}^l {{{\left( {E\left( {{a_i}} \right)} \right)}^{{b_i}}}} } \right)\bmod {N^2} = E\left( {\sum\limits_{i = 1}^l {{a_i}{b_i}} } \right). $

(5) 将计算结果E(v)告诉参与方A.

(6) 参与方A用私钥解密E(v)得到v并告诉B.

2.3 安全性证明

证明1 通过构造满足式(1)和(2)的模拟器S₁，S₂来证明协议1的安全性.S₁工作过程如下：

(1) 给定输入(a_i, a_i+b_i)，S₁随机选择一个b′_i使得a_i+b′_i=a_i+b_i, 用a_i, b′_i来模拟；

(2) 加密a_i得到E(a_i)；

(3) 选择一个随机数r′_i，计算

$ E\left( {{a_i} + {{b'}_i}} \right) = \left( {r_i^NE\left( {{a_i}} \right){{b'}_i}} \right)\bmod {N^2}; $

(4) 解密E(a_i+b′_i)得到a_i+b′_i.

在本协议中, VIEW₁^∏(a_i, b_i)={a_i, E(a_i), E(a_i+b_i), a_i+b_i}.令S₁(a_i, a_i+b_i)={a_i, E(a_i), E(a_i+b′_i), a_i+b′_i}.因为a_i+b′_i=a_i+ b_i，根据a_i+b_i的计算方法可知E(a_i+b_i)$\mathop \equiv \limits^c $E(a_i+b′_i).所以{(S₁(a_i, a_i+b), a_i+b_i)}_{ai, bi}$\mathop \equiv \limits^c ${(VIEW₁^∏ (a_i, b_i), OUTPU₂^∏(a_i, b_i))}_{ai, bi}，可以用类似的方法构造模拟器S₂，满足{(a_i+b_i, S₂(b_i, a_i+b_i))}_{ai, bi}$\mathop \equiv \limits^c ${(OUTPU₁^∏(a_i, b_i))}VIEW₂^∏(a_i, b_i))}_{ai, bi}.证毕.

证明2 通过构造满足式(1)和(2)的模拟器S₁，S₂来证明协议2的安全性.S₁工作过程如下：

(1) 给定输入(x, P(x, y))，S₁随机选择一个y′∈{w₁, w₂, …, w_m}使得P(x, y′)=P(x, y)，用x，y′来模拟.首先按照协议构造向量A =(a₁, a₂，…, a_m)，B′=(b′₁, b′₂, …, b′_m).

(2) 加密A得到

$ E\left( \mathit{\boldsymbol{A}} \right) = \left( {E\left( {{a_1}} \right), E\left( {{a_2}} \right), \cdots, E\left( {{a_m}} \right)} \right). $

(3) 选择一个随机数r′，计算

$ E\left( {v'} \right) = \left( {{{\left( {r'} \right)}^N}\prod\limits_{i = 1}^l {{{\left( {E\left( {{a_i}} \right)} \right)}^{{{b'}_i}}}} } \right)\bmod {N^2} = E\left( {\sum\limits_{i = 1}^l {{a_i}{{b'}_i}} } \right). $

(4) 解密E(v′)得到v′.

在本协议中，VIEW₁^∏(x, y)={ A, E(A), E(v), v}.令S₁(x, P(x, y))={ A, E(A), E(v′), v′}.因为P(x, y′)=P(x, y)，根据v的计算方法可知v=v′，E(v)_{x, y}$\mathop \equiv \limits^c $E(v′).所以{(S₁(x, P(x, y)), P(x, y))}_{x, y}$ \mathop \equiv \limits^c ${(VIEW₁^∏(x, y), OUTPUT₂^∏(x, y))}_{x, y}，可以用类似的方法构造使{(P(x, y), S₂(y, P(x, y)))}_{x, y}$\mathop \equiv \limits^c ${(OUTPUT₁^∏(x, y), VIEW₂^∏(x, y))}_{x, y}成立的模拟器S₂.证毕.

2.4 例子分析

例子1 Alice掌握：A₁, b₁，Bob掌握：A₂, b₂，其中A_i∈ R^m_i×n, b_i∈ R^m_i(i=1, 2)(一般的m₁+m₂≤n).在不完全泄漏各自隐私的情况下，共同解决线性规划问题：

$ \begin{array}{l} \max \xi = {\mathit{\boldsymbol{C}}^{\rm{T}}}\mathit{\boldsymbol{X}}, \\ \text{s.t.}\left\{ \begin{array}{l} {\left( {\mathit{\boldsymbol{A}}_1^{\rm{T}}, \mathit{\boldsymbol{A}}_2^{\rm{T}}} \right)^{\rm{T}}}\mathit{\boldsymbol{X}} = {\left( {\mathit{\boldsymbol{b}}_1^{\rm{T}}, \mathit{\boldsymbol{b}}_2^{\rm{T}}} \right)^{\rm{T}}}, \\ \mathit{\boldsymbol{X}} \ge 0. \end{array} \right. \end{array} $

(7)

为了阐述方便起见，设

$ \begin{array}{l} \left( \begin{array}{l} {\mathit{\boldsymbol{A}}_1}\\ {\mathit{\boldsymbol{A}}_2} \end{array} \right) = \left( {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{B}}_1}}&{{\mathit{\boldsymbol{D}}_1}}&{{\mathit{\boldsymbol{N}}_1}}\\ {{\mathit{\boldsymbol{D}}_2}}&{{\mathit{\boldsymbol{B}}_2}}&{{\mathit{\boldsymbol{N}}_2}} \end{array}} \right);\mathit{\boldsymbol{X}} = {\left( {\mathit{\boldsymbol{X}}_{{B_1}}^{\rm{T}}, \mathit{\boldsymbol{X}}_{{B_2}}^{\rm{T}}, \mathit{\boldsymbol{X}}_N^{\rm{T}}} \right)^{\rm{T}}};\\ \mathit{\boldsymbol{b}} = \left( {\mathit{\boldsymbol{b}}_1^{\rm{T}}, \mathit{\boldsymbol{b}}_2^{\rm{T}}} \right);\mathit{\boldsymbol{C}} = {\left( {\mathit{\boldsymbol{C}}_{{B_1}}^{\rm{T}}, \mathit{\boldsymbol{C}}_{{B_2}}^{\rm{T}}, \mathit{\boldsymbol{C}}_N^{\rm{T}}} \right)^{\rm{T}}}. \end{array} $

X_B, X_N分别表示基变量和非基变量，这时的线性规划问题可变换成如下的等价形式：

$ \begin{array}{l} \max \xi = \mathit{\boldsymbol{C}}_{{B_1}}^{\rm{T}} + \mathit{\boldsymbol{C}}_{{B_2}}^{\rm{T}}\mathit{\boldsymbol{X}}_{{B_1}}^{\rm{T}} + \mathit{\boldsymbol{C}}_N^{\rm{T}}{\mathit{\boldsymbol{N}}_N}, \\ \text{s.t.}\left\{ \begin{array}{l} \left( {\begin{array}{*{20}{l}} \mathit{\boldsymbol{E}}&{\mathit{\boldsymbol{B}}_1^{-1}{\mathit{\boldsymbol{D}}_1}}&{\mathit{\boldsymbol{B}}_1^{-1}{\mathit{\boldsymbol{N}}_1}}\\ {\mathit{\boldsymbol{B}}_2^{-1}{\mathit{\boldsymbol{D}}_2}}&\mathit{\boldsymbol{E}}&{\mathit{\boldsymbol{B}}_2^{ - 1}{\mathit{\boldsymbol{N}}_2}} \end{array}} \right)\left( \begin{array}{l} {\mathit{\boldsymbol{X}}_{{B_1}}}\\ {\mathit{\boldsymbol{X}}_{{B_2}}}\\ {\mathit{\boldsymbol{X}}_N} \end{array} \right) = \left( \begin{array}{l} \mathit{\boldsymbol{B}}_1^{ - 1}{\mathit{\boldsymbol{b}}_1}\\ \mathit{\boldsymbol{B}}_2^{ - 1}{\mathit{\boldsymbol{b}}_2} \end{array} \right), \\ {\mathit{\boldsymbol{X}}_{{B_1}}}, {\mathit{\boldsymbol{X}}_{{B_1}}}, {\mathit{\boldsymbol{X}}_N} \ge 0. \end{array} \right. \end{array} $

该表达形式称为线性规划问题对应与基变量的典式.

用单纯形法求解，见表 1.

其计算步骤如下：

Step1：找出初始可行基，确定初始基可行解，建立初始单纯形表.

Step2：在不泄漏隐私信息的情况下，Alice和Bob协同检查各非基变量的检验数，若σ≤ 0，则已得到最优解，计算结束.否则转入下一步.

Step3：根据max(σ)=σ_k>0，确定x_k为换入变量后，按照$\mathit{\boldsymbol{\theta }} = \mathop {\min }\limits_i \left( {\frac{{{{\left( {{\mathit{\boldsymbol{B}}^{-1}}\mathit{\boldsymbol{b}}} \right)}_i}}}{{{{\left( {{\mathit{\boldsymbol{B}}^{-1}}{\mathit{\boldsymbol{P}}_j}} \right)}_i}}}\left| {{{\left( {{\mathit{\boldsymbol{B}}^{-1}}{\mathit{\boldsymbol{P}}_j}} \right)}_i} > 0} \right.} \right)$，Alice和Bob分别单独计算θ₁和θ₂，并选出各自的min(θ₁)，min(θ₂)，在不泄露各自信息的情况下，安全比较其大小，确定换出变量，替换后得到新基变量，再入下一步.

Step4：求出新基变量对应的典式以及新基变量对应的基可行解.

Step5：重复Step2~Step4，直到终止.

关于Step2和Step3的安全多方计算问题, 可用前面的协议1和协议2来解决，因此本节不再述说.

3 约束异构时安全多方计算 3.1 模型与假设

本节研究在半诚实模型下的约束异构的线性优化问题，其数学模型如下：

$ \begin{array}{l} \max \xi = \left( {\mathit{\boldsymbol{C}}_1^{\rm{T}}, \mathit{\boldsymbol{C}}_2^{\rm{T}}, \cdots, \mathit{\boldsymbol{C}}_n^{\rm{T}}} \right){\left( {\mathit{\boldsymbol{X}}_1^{\rm{T}}, \mathit{\boldsymbol{X}}_2^{\rm{T}}, \cdots, \mathit{\boldsymbol{X}}_n^{\rm{T}}} \right)^{\rm{T}}}, \\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ \begin{array}{l} {\rm{diag}}\left( {{\mathit{\boldsymbol{A}}_1}, {\mathit{\boldsymbol{A}}_2}, \cdots {\mathit{\boldsymbol{A}}_n}} \right)\left( {\mathit{\boldsymbol{X}}_1^{\rm{T}}, \mathit{\boldsymbol{X}}_2^{\rm{T}}, \cdots, \mathit{\boldsymbol{X}}_n^{\rm{T}}} \right) = \\ \;\;\;\;\;\;\;\;\;\;{\left( {\mathit{\boldsymbol{b}}_1^{\rm{T}}, \mathit{\boldsymbol{b}}_2^{\rm{T}}, \cdots, \mathit{\boldsymbol{b}}_n^{\rm{T}}} \right)^{\rm{T}}}, \\ {\mathit{\boldsymbol{X}}_i} \ge \mathit{\boldsymbol{0}}, i = 1, \cdots, n. \end{array} \right. \end{array} $

(8)

假设：

(1) C_i∈ Rⁿ为共享信息；

(2) P_i的隐私信息A_i, b_i, X_i，其中A_i∈ R^m_i×n，b_i∈ R^m_i, X_i∈ Rⁿ(一般m₁+m₂+…+m_n≤n).

3.2 模型(8)的安全多方协议

模型(8)用单纯形法求解的计算步骤如下：

Step1：找出初始可行基，确定初始基可行解，建立初始单纯形表.

Step2：在不泄漏隐私信息的情况下，P₁, P₂, …, P_n独自检查各非基变量的检验数，若σ_i≤ 0，则已得到最优解，计算结束.否则转入下一步.

Step3：若max(σ_i)>0，P₁, P₂, …, P_n选出各自的max(σ_i)，在不泄露各自信息的情况下，比较其大小，确定换入变量，进入下一步.

Step4：按θ规则，P₁, P₂, …, P_n独自计算θ_i，并选出各自的min(θ_i)，在不泄露各自隐私的情况下，比较其大小，确定换出变量，再入下一步.

Step5：求出新基变量与其对应的基可行解.

Step6：重复Step2~Step5，直到终止.

Step7：P₁, P₂, …, P_n共同计算maxξ.

模型(8)涉及到的隐私计算问题是安全多方比较问题和安全多方求和问题，可以用协议1和协议2来完成这两个计算任务，因此本节不再详述.

3.3 例子分析

例子2：Alice掌握：A₁, b₁，Bob掌握：A₂, b₂，其中A_i∈ R^m_i×n, b_i∈ R^m_i(i=1, 2)(一般的m₁+m₂≤n)，且C₁, Χ₂∈ Rⁿ是公开的.在不完全泄漏各自隐私的情况下，共同解决线性规划问题：

$ \begin{array}{l} \max \xi = \left( {\mathit{\boldsymbol{C}}_1^{\rm{T}}, \mathit{\boldsymbol{C}}_2^{\rm{T}}} \right){\left( {\mathit{\boldsymbol{X}}_1^{\rm{T}}, \mathit{\boldsymbol{X}}_2^{\rm{T}}} \right)^T}, \\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ \begin{array}{l} {\rm{diag}}\left( {{\mathit{\boldsymbol{A}}_1}, {\mathit{\boldsymbol{A}}_2}} \right){\left. {\mathit{\boldsymbol{X}}_1^{\rm{T}}, \mathit{\boldsymbol{X}}_2^{\rm{T}}} \right)^{\rm{T}}} = {\left( {\mathit{\boldsymbol{b}}_1^{\rm{T}}, \mathit{\boldsymbol{b}}_2^{\rm{T}}} \right)^{\rm{T}}}, \\ {\mathit{\boldsymbol{X}}_i} \ge \mathit{\boldsymbol{0}}, i = 1, 2. \end{array} \right. \end{array} $

(9)

根据文献[15]，Alice和Bob独自对系数增广矩阵(A₁ b₁)和(A₂ b₂)作保持可行性(即b列非负)的初等行变换，得到(A′₁ b′₁和(A′₂ b′₂); 其中diag(A′₁, A′₂)已含初始可行基.建立初始单纯形表，如表 2所示.

其计算步骤如下：

Step1：找出初始可行基，确定初始基可行解，建立初始单纯形表.

Step2：在不泄漏隐私信息的情况下，Alice和Bob各自检查各非基变量的检验数，若σ≤0，则已得到最优解，计算结束.否则转入下一步.

Step3：若max(σ)>0，Alice和Bob选出各自的max(σ₁)，max(σ₂)，在不泄露各自信息的情况下，比较其大小，确定换入变量，进入下一步.

Step4：按θ规则，Alice和Bob分别单独计算θ₁和θ₂，并选出各自的min (θ₁)，min(θ₂)，在不泄露各自信息的情况下，比较其大小，确定换出变量，再入下一步.

Step5：求出新基变量与其对应的基可行解.

Step6：重复Step2~Step5，直到终止.

Step7：P₁, P₂, …, P_n共同计算maxξ.

例子2的安全多方计算问题，可以用协议1和协议2来解决，因此本节不再详述.

4 结语

无论是生产运作管理还是在供应链管理中，有大量的优化决策问题，本文仅仅是提出一种针对线性优化问题的安全多方计算协议，并对文中提出的协议的安全性给出了证明，研究表明该协议比一般的单调张成方法生成的安全多方计算协议具有较高的计算效率.在实际应用系统中，大部分的系统(如SCM，ERP)中的模型求解，多数使用Karmarkar方法，本文没有采用这个方法来设计SMC，也没有考虑非线性约束下的各类优化问题的SMC问题，当然这是非常庞大的研究内容，从目前的研究来看，也不太可能存在一种通用的设计方法，因此对于不同的优化系统，可能还是要先设计不同的SMC.

实际应用时，还要讲究计算的效率问题，目前多数SMC方法的计算复杂度比较高，如何提高实际协同决策时的SMC方法的计算效率，还是一个非常广阔的研究方向.