“平均工资问题”的方案分析与改进*

李烨龙 张艳硕

北京电子科技学院，北京市 100070

0 引言

安全多方计算起源于1982 年华裔计算机科学家、图灵奖获得者姚期智[1]先生提出的百万富翁问题:两个分别拥有隐私数据x； y 的参与者， 保密判断x 是否大于y，而不泄露x；y 的其他信息.由百万富翁问题发展而来的安全多方计算是指分别拥有隐私数x1； x2；……； xn的n 个参与者联合计算f( x1； x2；……； xn) 的值， 计算完成之后， 每个参与者除了得到f( x1； x2；……；xn) 的值之外， 得不到关于隐私数据的其他任何信息。 姚氏“百万富翁问题”后经OGoldreich、Micali[2]等人的深入研究和发展后，证明在一定的条件下， 任意函数f( x1； x2；……；xn) 的安全多方计算都是可以实现的， 并且给出基于不经意传输的解决方案。 这样的通用解决方案有着重要的理论意义，增加了其在现代互联网浪潮之下的应用价值，这使得安全多方计算成为现代密码学中非常活跃的研究领域，被进一步研究和发展。

安全多方计算的基本概念[3]是“一组参与者希望共同计算某个约定的函数；函数的输入参数有多个；每个参与者提供函数的一个输入；每个人都知道这个函数的值；除了函数的输出外，没有人知道其他参与者输入的信息”。 一个安全多方计算协议，如果对于拥有无限计算能力攻击者而言是安全的，则称作是信息论安全的或无条件安全的；如果对于拥有多项式计算能力的攻击者是安全的，称为是密码学安全的或条件安全的。 已有的结果证明了在无条件安全模型下，当且仅当恶意参与者的人数少于总人数的1/3 时，安全的方案才存在。 而在条件安全模型下，当且仅当恶意参与者的人数少于总人数的一半时，安全的方案才存在。

安全多方计算理论主要研究参与者间协同计算及隐私信息保护问题，其特点包括输入隐私性、计算正确性及去中心化等特性。 在隐私保护被不断提及的当下，安全多方计算研究取得了极大的进步[4]。 密码学家研究了各个应用领域中出现的安全多方计算问题，其中包括保密科学计算[5-7]、保密计算几何[8]、保密数据挖掘[9]等问题。 该理论后来被应用到电子选举、门限签名以及电子拍卖等诸多场合，是这些设计得以实施的密码学基础。 安全多方计算在极其注重个人隐私和数据安全的现在，发挥了巨大的作用，为实现数据的可控共享做出了极大的贡献。 很多隐私保护问题都可以用安全多方计算方法解决，因此安全多方计算成为信息社会隐私保护的关键技术。 如果借助可信的第三方， 安全多方计算问题很容易解决， 但在遍布整个世界的、复杂的互联网环境中， 找到一个所有参与者都信任的第三者并不容易， 因此需要设计安全多方计算协议保证私有信息不被泄露。 安全多方计算在保护私密数据隐私的前提下， 使得参与者能够最大限度地利用自己的私有数据进行保密合作计算， 充分发挥私有数据在社会、经济和科学技术领域的积极作用， 是实现合作保密计算的主要工具。

基于安全多方计算的平均工资问题在信息安全实践中具有重要的实际意义。 在日常生活中，工资无论对于个人或者公司来说都是极为隐秘和重要的数据。 如果某求职者想要知道自己在公司之中处于什么样的水平，这就需要计算身边同事之间的平均工资。 由于员工和公司之间通常都签有保密协议，这就需要进行平均工资问题的保密计算。 除此之外，平均工资问题还具有很重要的数学意义。 如何借助纯数学的知识来进行平均工资的保密计算，这需要借助随机数，同时还需要设计一个可靠的函数来进行计算，达到安全的同时保证其简易可行。

本文针对安全多方计算的衍生问题——“平均工资问题”进行深入分析阐述，在研究其原解法和新解法之后发现其隐藏的安全性问题，即去中心化不完全和存在信息泄露的隐患。 这说明原方案在流程设计方面存在着缺陷，在隐私数据保护方面的设计也不到位，使得参与协同计算者的个人信息受到严重威胁。 在深入探讨和思考之后，本文将针对如上两个问题制定改进方案，在进行数据隐藏时充分利用随机数来增加数据的不确定性，在避免信息泄露的同时提高方案效率，还构造了在几何均值上的拓展方案。

1 平均工资问题及其解法

本节中将具体阐述平均工资问题及关于该问题隐藏的前提条件，再对现有各方案给出基本分析后详细说明最原始的解法。

1.1 安全多方计算中平均工资问题

工资对于个人和公司来说是极其隐私的数据。 很多公司的工资十分的隐蔽，员工必须签署工资保密协议，就是每人不得透漏自己的工资，但是有些员工还是特别想知道自己所拿到的工资在公司处于怎样一个层次，知道了平均工资就可以知道自己的层次。 安全多方计算就能解决这个问题，通过一个公认的函数秘密的计算平均工资，和平均工资一比较，就知道你的层次的。现假设有四名员工Alice、Bob、Carol 和Dave 四个人在一家公司工作，他们均签署了公司的保密协议，即他们不能向其他人透露自己的工资，但是他们每个人又想了解彼此的工资情况，现场无仲裁者。 在这种情况下，最能够简单直白地作为衡量自己工资标准的就是四个人的平均工资，只要设计一个方案能够安全地计算出平均工资就可以解决问题。

该问题在现实生活中可以分化成许多场景，比如公司之间想要了解各自的收入水平，又或是学校之间想要了解某次考试各自学校的成绩属于什么档次等均可以利用该模型来进行分析求解。

本文就是根据上述问题来设计解答安全多方计算中平均工资问题。

1.2 前提条件

为了深入探索该问题的解法，必须先探讨一些前提条件，再根据现有方案的安全性制造一些攻击，最后设计出一个相对来说安全性较高的方案。 为了寻求方案的一般性，在这里直接讨论针对n 个人的情况

前提1:所有的节点必须是诚实的，也就是说，每个人提供自己的工资信息时不能撒谎。

这是一个很不现实但又必须做的假设。 原因很简单，如果有且仅有一个节点撒谎，那么经过计算他将获得正确的平均工资，同时其余人将无法得到正确的平均工资，且完全无法验证；如果有至少两个人撒谎，那么没有人可以同时知道所有人的平均工资。 无论如何，整个协议将变得没有意义。

前提2:最坏的情况下只有n-2 个节点进行合谋，攻击其余两个节点。

如果n-1 个节点攻击另外一个节点，无论如何都一定成功。

前提3:他们只能靠互相交流信息来获得答案。

也就是说，在该协议中不存在一个第三方来协助计算，全部的过程都是只有参与者来进行。

在上述前提之下，如果存在除参与者之外的敌手对该协议进行攻击，那么便会存在安全风险。

假设这n 位参与者不在同一空间，彼此之间只能通过计算机发送信息，而通信的信道是不可靠的，参与者不能验证这条消息是不是由对方发来的、没有被篡改过的，传输的信息也有可能会被敌手得到。 而现在的要求中包括两方面:第一，这n 个人中即使有n-2 个人合谋，也只能知道剩下2 人的平均工资，不能获得更多的信息；第二，敌手即使可以获得所有的通信消息，也可以进行篡改。 在这种情况下，希望敌手不能获得关于工资的任何信息，也不能篡改通信内容而不被发现。

在接下来的所有方案中，需要利用到公私钥加密和数字签名默认两点:第一敌手的计算能力是有限的，这允许参与者进行公钥加密和签名；第二公开信息是可靠的，也就是说，参与者可以公开一个代表自己的字符串——一个“公钥”，这个公钥没有保密性，任何人都可以看到。 而这种情况下这个字符串是无法伪造的，也就是所有人都可以确定公开的是这段字符串。

1.3 设计思路分析

本小节将对现有的三种设计思路进行分析，初步探讨其安全性。

(1)借助一些能够代表数字的物理道具，比如扑克牌，麻将等。

在该方案中，每个人可以通过规定扑克牌的花色和大小所代表的金钱规模，接着找牌拼凑出自己的工资，之后每个人将所有的牌混在一起加起来求平均。 由于这些牌是扣起来混合的，因此所有人不能知道其他人的工资。

这个方法在大多数情况下可以保证自己的工资不被其他人所知，但是会存在信息泄露。 如果用红桃代表千位，当看到翻开后的牌里有一个红桃九，而你自己的工资只有一千多，矛盾就产生了。 但是基于安全多方计算所要求达到的效果是，所有参与计算的人只能知道最后的平均工资，而不能知道每一个人工资的任何信息，所以方案一不可行。

(2)由第一个人加上一个随机数，每个人加上自己的工资，最后减掉随机数。

该方案是符合最基本的安全要求的，在下文中具体解释的第一个方案就是使用的该方法。在该方案中，如果每个人都只知道自己的工资和传来的数字，就没有人可以知道其他人的工资，保证了一定的安全性。

这个方案几乎没有直接泄露的信息，但如果少数人合谋便可以对某个人的工资数进行攻击。例如Alice 知道了Carol 收到的数字，他就可以知道Bob 的工资；Bob 知道了Dave 收到的数字，就知道Carol 的工资……对于任意一个n， 只需要知道前后的数字就可以算出一个人的工资，所以这个协议还是比较脆弱的。

(3)每个人拆分自己的工资并发给其他人，各自求总和。

在这种情况下，即使任意n-2 个人合谋也只能得到其余两人的平均工资，无法获得更多的信息。 这是目前最好的方案，也是本文所探讨的平均工资问题新解法。 但是在该方案进行中进行了一些假设:每个人发给其他人的信息不会被这n 个人之外的敌手窃听，也不会被篡改。 但实际中并不是这样，下文中会有针对该问题而设计的更为安全的解法。

1.4 安全多方计算中平均工资问题基本解决方案

文献对于“平均工资问题”的保密算法利用了随机数进行初始的数据加密，同时利用公私钥加密的方式在传输数据时避免发生数据泄露，利用数字签名的方式来防止敌手窃密，保障了数据交换时的隐私性和安全性。

本文先给出最初始的解题方案(简称为方案一)，如下:

(1)Alice 生成一个随机数a，将其与自己的工资相加得到b，用Bob 的公钥加密后得到密文，再将密文用自己的私钥签名，将密文和签名信息发送给Bob。

(2)Bob 先进行签名认证，确认后用自己的私钥解密得到b，加进自己的工资得到c，然后用Carol 的公钥加密后得到密文，再将密文用自己的私钥签名，将密文和签名信息发送给Carol。

(3)Carol 先进行签名认证，确认后用自己的私钥解密得到c，加进自己的工资得到d，然后用Dave 的公钥加密后得到密文，再将密文用自己的私钥签名，将密文和签名信息。

(4)Dave 先进行签名认证，确认后用自己的私钥解密得到d，加进自己的工资得到e，然后用Alice 的公钥加密后得到密文，再将密文用自己的私钥签名，将密文和签名信息发送给Alice。

(5)Alice 先进行签名认证，确认后用自己的私钥解密得到e，减去原来随机数得到工资总和f。

(6)Alice 将工资总和除以人数得到平均工资g，最后宣布结果。

在该方案中，假定的前提是所有参与者均为诚实个体，即提交的工资数据都是真实的，如果非诚实则计算出的平均工资结果错误。 第一人Alice 在本方案中作为“名义上”的集成者，他能够最先得到计算结果并且需要将结果分发给其余参与者。 然而，Alice 也可以不冒任何风险地谎报数据，让其余参与者得到错误的平均工资，这是该方案的一个漏洞，原因是该方案的去中心化不完全。 一般的，该方案的“补救措施”是运用“比特承诺”[10]让Alice 向Bob 传输他的随机数，这样可以解决Alice 谎报的问题，但是如此一来Bob 就会获知Alice 的工资，方案仍然存在着缺陷。

2 安全多方计算中平均工资问题新方法

用于解决平均工资问题的方法有很多，在对其进行研究的时候发现了一种基于随机数的平均工资问题解决方案(简称为方案二)，该方案有着很高的安全性同时还具有简洁的数学美感。本节将介绍基于随机数的平均工资问题解决方案并对该方案的安全性做简要分析。

2.1 基于随机数的平均工资问题解决方案

因为上文中平均工资问题的原解法方案存在着严重缺陷，试图寻找其他的解法方案，经过仔细研究发现存在以下的一种更为简便可行且安全性更高的方案[11]，具体如下及表1 所示:

输入:参与方Ai(i=1，2，…，n)拥有整数ai∈Z+。

具体步骤如下及表1:

表1 方案二流程解释

2.2 方案分析

在该方案中，并没有像方案一中那样存在着一个集成者，而是选择了将每个人的工资数据分成若干份，分散出去，最后保证了每位参与者得到的是最先散发出去的所有数据的总和。 这种方式避免了一个中间人的存在，所有参与者的地位都是平等的，不需要让其他某位参与者对数据进行计算再进行传输，从而解决了因去中心化不完全而发生的数据造假的问题。 该方案使用了纯数学的方法，只有简单的加减乘除运算，设计思路十分巧妙，通过拆分自己的工资数据来达到数据隐蔽，在得到所有的数据之后每位参与者可以自行计算平均工资，保证每个人得到的都是“一手数据”，降低了存在中间篡改数据的风险。

然而，该方案仍然存在着缺陷。 由于第一步中要求每位参与者将自己的工资数据拆分并全部分散给其余参与者，这实际上是安全系数较低的一种方式，因为其余参与者都得到了该参与者的一部分工资数据，如果基数够小，其余参与者是可以很容易通过碎片数据的组合来大体估摸出该参与者的工资，这对每位参与者的工资数据都造成了威胁。

3 现有方案中存在的安全问题

方案一和方案二表面上都可以解决平均工资问题，但是在实际操作中还是存在着不可忽视的安全问题，本小节将揭示其存在问题对其进行分析并给出改进思路。

3.1 存在问题

方案一实际上没有满足安全多方计算中的去中心化，第一位参与者名义上就是中心，负责对数据进行最终的计算和分发，在这里存在着安全隐患。 第一位参与者可以在计算得到了平均工资后，捏造一个虚假的平均工资。 虽然方案一给出了解决方法，即利用“比特协议”将第一位参与者生成的随机数传输给第二位参与者进行确认，但是这样第一位参与者的工资数据就暴露给了第二位参与者。 另外，第一位参与者可以一开始就给出虚假的工资数据，最后再更改为正确的工资数据，如此即使进行了安全确认，也只有第一位参与者得到了真正的平均工资，其余参与者得到的都是虚假的平均工资。 也就是因为该方案的去中心化不完全，导致了最终的结果仅对于第一位参与者来说是“一手的”，对于其余参与者来说都是“二手的”，在这转手的过程之中，存在着极大的安全隐患。

方案二在每位参与者随机拆分并分发自己的工资数据时，实际上存在着信息泄露的隐患。其余参与者可以根据某一位参与者给出的碎片数据得到一个工资的下限，即该参与者的工资一定大于某个值。 当多位参与者互通交换各自的信息时，该参与者的工资数据便一步一步接近真实值。 这样一来，即使每位参与者都得到了正确的工资数据，但是也存在着隐私泄露的隐患。

3.2 安全性分析

方案一中的去中心化不完全和方案二中的信息泄露问题并不是没有解决方案，针对方案一和方案二中的存在的安全问题，本小节将就此深入展开安全性分析。

方案一存在的问题是去中心化不完全，存在着名义上的集成者，在数据多次转手的过程中数据的安全性在一步步降低，所以方案一需要避免最终的计算只交给一个人来进行从而产生转手数据降低安全性的流程设计。 方案一可以借鉴方案二的设计思路，最终数据不是全部落到一个人手中，而是到达每个人的手里，让每个人可以自己进行计算，该方法避免了产生集成者转手数据的安全性缺陷。

方案二在处理每个人的工资数据时将工资拆分成若干份再进行分发而导致存在信息泄露。每个人都可以知道其余参与者的工资是大于传到手上的工资碎片的大小，所以一旦有多人联手进行攻击，那他们得到的数据和便会愈发接近其他参与者的工资。 该问题可以很好解决，只需要借鉴方案一中对数据进行初加工时使用随机数进行加密，这样他人就无法对数据进行解读，安全性大大增加。

3.3 改进思路

在对方案一方案二进行安全性分析后，本小节将针对以上方案一二中存在的安全问题进行探讨并给出改进的方案思路。 新方案的目标是在具有隐私性、计算正确性及去中心化的特性的同时具有简单的原理和较强的可行性。

由于方案一存在的问题是去中心化不完全，存在着名义上的集成者，而方案二的设计思路避免了该问题，所以新方案将沿袭方案二中的“先分散数据再各自集中求和”的方法，达到完全的去中心化，将方案流程上的风险进一步降低，避免因数据多次转手而产生的误差和错误，增强其安全性。

而由于方案二中，直接将工资数据拆分会有信息泄露的风险，方案一中运用了随机数来对数据进行加密隐藏，相较之下使用随机数更加安全隐私性更加高，所以考虑在新方案中引入随机数，通过多个随机数进一步增加初始数据的不可确定性，从而达到对参与者工资数据的保护。

4 平均工资问题的改进方案

4.1 具体方案

根据上文的改进思路，在进行深入思考与讨论之后，得出了一种结合了方案一和方案二各自优点的新方案，在完全去中心化的同时避免了信息泄露。 下面本文将给出改进后的安全多方计算中平均工资问题新设计，具体方案如下及表2:

输入:参与方Ai(i=1，2，…，n)拥有整数Ri∈Z+。

具体步骤:

用自己的私钥进行签名，将对应的加密信息和签名一起发送给Aj(1≤j≤n，i≠j)。

(3) Ai(i=1，2，…，n)将第二步收到的n 份加密过随机数总和进行签名认证，确认后用自己的私钥解密得到n 份总和。

(4) Ai(i=1，2，…，n)将第一步收到的n-1份加密过的随机数先进行签名认证，确认后再用自己的私钥解密得到随机数，求总和，并加入自己的工资得到T1，T2，T3，……，Tn，先用Aj的公钥加密再用自己的私钥进行签名，将对应的加密信息和签名一起发送给Aj(1≤j≤n，i≠j)。

表2 方案三流程解释

4.2 方案分析

与方案二进行对比，方案二采取的措施是将工资“打碎”并分发让每个人得到的是部分工资数据的总和，再将部分工资数据的总和进行求和得到总和求平均数，而新方案选择的是将随机数进行分发，让每个人得到一个随机数的和，利用这个随机数的和来对工资数据进行隐藏同时传输，最后求出的是随机数的总和加上工资的总和，再减去随机数的总和求平均便得到了平均工资。 新的方案设计避免了方案二中可能出现的信息泄露问题，即方案二中如果各用户对工资“拆分”操作不当，产生并分发的都是非负随机数，那么如果其余参与者合谋便可以得到该参与者的部分工资，且参与合谋的人越多，泄露出的数据和便越发接近该参与者的工资。 然而如果我们传出的都是随机数，在n-2 位参与者进行合谋的情况下，仍然保证了工资信息的安全。

与方案一进行对比，新方案保证了完全的去中心化，防止了像方案一中由于相邻两位参与者进行合谋而造成的工资泄露。

新方案的流程设计由于绝对的去中心化，保证了数据的安全可靠，同时由于频繁利用随机数来对工资数据进行包装隐藏，减小了数据在输过程中发生信息泄露的可能性。 同时该方案设计原理简单易懂，操作流程简便，极大地增强了可行性。

5 “平均工资问题”在几何均值上的拓展方案

在上一方案中，已经能够成功通过协议安全计算平均工资，能够在每位参与者给出正确工资的情况下，计算得到平均工资了解自己的层次。上述方案只能够计算算数平均值，会极容易手极端数据的影响，每个数据或大或小的变化都会影响到最终结果。 考虑到平均值中的几何均值受极端数据的影响较小，在改进方案的基础上，该方案设计出了安全计算几何均值的方法。 在本小节中，将介绍基于安全多方计算的求几何均值方案，具体方案如下及表3:

输入:参与方Ai(i=1，2，…，n)拥有整数Ri∈Z+。

具体步骤:

(3) Ai(i=1，2，…，n)将第二步收到的n 份加密过随机数乘积进行签名认证，确认后用自己的私钥解密得到n 份乘积。

表3 计算几何均值流程解释

6 总结

随着现代密码学的不断发展，安全多方计算理论在信息安全领域以及密码保密领域起到了越来越大的作用。 随着人们对个人隐私和信息安全的关注逐渐提升，对于安全多方计算的安全性、隐私性和去中心化程度的要求会越来越高。本文对现有的安全多方计算中平均工资问题的两种解决方案进行了深入解读分析，发现其隐藏的安全隐患，取长补短设计新方案解决了原有的去中心化不完全和信息泄露的问题，极大地增加了安全性，同时新方案设计原理简单操作简便，可行性极高，还构造了在几何均值上的拓展方案。