基于分支程序逆向评估的安全多方计算

俞强生，古天龙，徐周波，宁黎华

(桂林电子科技大学 广西可信软件重点实验室，广西 桂林541004)

计算机和网络技术的迅猛发展为多方联合计算提供了大量应用场景。然而，信息化发展带来便利的同时，数据安全与隐私保护问题不断凸显，成为制约多方联合计算发展的最大障碍。安全多方计算(secure multi-part computation，简称SMC)概念最早由图灵奖获得者Yao提出［1］，其核心思想是在保护隐私的前提下，互不信任的参与方进行联合计算，并得到预期执行结果。安全多方计算在隐私保护基因计算［2］、保密计算［3］等许多领域有广泛应用。

决策函数有效表示问题是安全多方计算研究的热点问题，决策函数表示是否高效决定了协议效率的高低。Yao［4］最早提出用混淆布尔电路的方法解决决策函数表示问题，但布尔电路不能描述伪布尔函数。同时，随着决策函数复杂性增加，布尔电路中的电路门规模急剧增大，造成编码规模大、计算复杂度高等问题。

符号描述技术是一种求解决策函数表示问题的新方法，其中有序二叉决策图(ordered binary decision diagram，简称OBDD)是布尔电路的一种紧凑表示方式。Kruger于2006年提出基于OBDD技术描述决策函数［5］，一定程度上降低了编码复杂度，提高了协议效率。但是，OBDD是布尔电路方法基础上的一种形式化表示，也不能描述伪布尔函数。在文献［5］基础上，古天龙等［6］提出基于代数决策图(algebraic decision diagram，简称ADD)技术取代符号OBDD刻画决策函数，决策函数的表示形式由此得到极大扩展。然而，符号ADD随着决策函数复杂性增加，叶子节点规模会急剧膨胀，协议面临状态空间爆炸问题。

安全计算借助可编程通用电路，将函数描述及隐私数据作为输入，进行联合计算并输出结果［7］，但是，由于布尔电路本身固有的局限性，描述效率不够理想。因此，Brickell等［8］使用分支程序(branching program，简称BP)表示安全计算问题。为减少交互次数，降低协议复杂度，Mohassel［9］结合不经意传输技术，提出基于不经意传输BP的安全计算协议。

边值二叉决策图(edge-valued binary decision diagram，简称EVBDD)作为表示伪布尔函数的一种新型数据结构，极大改善了伪布尔函数和有限域取值函数的描述能力，在一定程度上解决了因决策函数规模增大而导致的状态空间爆炸问题。为此，引入EVBDD的符号描述技术，利用其易操作和高紧凑性的优点，给出一种基于EVBDD的决策函数表示方法，并设计一个效率高、评估计算简单且适用大多数决策函数的基于符号EVBDD的安全2方计算协议。同时，在分支程序的基础上，提出一种分支程序的逆向评估方法，借助基于边值二叉决策图的安全2方计算协议为基础协议，设计一个基于分支程序逆向评估的安全多方计算协议，此协议将传统的2方计算扩展到多方，其效率也有所提高。

1 预备知识

1.1 不经意传输协议

定义1［10］2选1不经意传输协议(O):参与者按行为划分为发送方和选择方。发送方输入一串长为t的字符串对∈{0，1}t，其中i=1，2，…，n，选择方输入选择位b∈{0，1}。协议执行完毕，选择方获得字符串，但无法知晓另一字符串，而发送方也无法获知选择方的选择b。

1.2 同态加密(HE)

使用一种语义安全的加同态公钥加密机制，加密机制的语义安全是指无法从特定密文中提取任何明文信息。

加同态加密算法具有如下性质:存在有效算法⊕，E(x+y)=E(x)⊕E(y)或x+y=D(E(x)⊕E(y))成立，并且不泄漏x和y。因此，加同态算法也可直接用于与常数k的乘法操作:kE(x)=E(kx)。对同态加密的实例化采用文献［11］中的加密机制。

2 基于符号EVBDD的安全2方计算协议(协议1)

2.1 边值二叉决策图(EVBDD)

EVBDD［12］是在ADD的基础上，在边中引入权值提高子图的共享度，进而为函数值是整数的伪布尔函数提供一种更为规范、紧凑的表示形式。EVBDD不仅能像OBDD一样实现布尔函数操作，还能像ADD一样实现对伪布尔函数的布尔操作和算术操作。这里，决策函数的EVBDD表示建立在有序的基础上。图1和图2是伪布尔函数f=3+5x1+6x2+x3分别在ADD和EVBDD符号表示下的图形结构，变量序为x1＜x2＜x3。在输入模式(0，1，0)下，函数f对应的函数值为3+0+6+0=9。

图1 伪布尔函数f=3+5x1+6x2+x3 ADD表示Fig.1 ADD for pseudo-Boolean functionf=3+5x1+6x2+x3

图2 伪布尔函数f=3+5x1+6x2+x3 EVBDD表示Fig.2 EVBDD for pseudo-Boolean functionf=3+5x1+6x2+x3

2.2 协议流程

在符号EVBDD表示的基础上，提出基于符号EVBDD的安全2方计算协议。假设参与计算双方为Alice和Bob，输入为:表示(伪)布尔函数f(x1，x2，…，xn)的EVBDD(f)，其中变量序为x1＜x2＜…＜xn。Alice的输入Xa=(x1，x2，…，xk)对应EVBDD(f)中前k个变量，Bob的输入Xb对应后n-k个变量。预期输出为:C=f(Xa，Xb)。

参与方Alice执行协议的流程为:

1)用变量(x1，x2，…，xk)遍历EVBDD(f)的前k个节点，约束后的初始节点记为v。

2)约束后的EVBDD(ffull|Xa)随机产生n-k对节点的取值密钥:，并为每个节点v分配节点密钥sv。

3)为k+1层到n层的每个节点随机分配一个标签，用l(v)表示节点v所处的层数。

4)为约束后的EVBDD(ffull|Xa)填充虚节点。

5)加密EVBDD(ffull|Xa)，每个节点密文都包含代表该节点位置的节点标签、该节点不同取值下的2条子密文。每条子密文又包含路径中下一节点的标签、下一节点的节点密钥、该节点取值时的边值(也称权值)。

6)Alice将k+1层到n层的节点密文和初始节点的节点密钥sv发送给Bob。

参与方Bob执行协议的流程为:

1)Bob获取初始节点的节点密钥sv，并通过nk次1-out-of-2不经意传输获得对应其输入的密钥

2)Bob用获得的密钥解密，从Alice步骤5)获取的密文得到C，即f(Xa，Xb)。

3 基于分支程序逆向评估的安全多方计算

3.1 分支程序

定义2［9］分支程序:分支程序是3元组〈{P1，P2，…，Pz}，L，R〉的有向无环图，其中Pi(i=1，2，…，z)为节点集，且满足以下条件。

1)P1，P2，…，Pd为决策节点(又称内部节点、非终节点)，Pd+1，Pd+2，…，Pz为分类节点(终节点)。

2)每个决策节点Pi(1≤i≤d)对应一个2元组〈ti，αi〉，对应输入值V=v1，v2，…，vn。其中，ti为阀值，αi为输入索引，vai为索引αi下的输入值。

3)分类节点(又称诊断节点、终节点)即为叶子节点，每一个叶子节点都持有唯一的标签〈di〉。

4)L和R分别表示决策点Pi的左右分支索引函数的有向无环图，若vai≤ti，索引为L(i)，反之，则为R(i)。

分支程序的评估始于节点P1，若va1≤t1，h=L(1)，否则，h=R(1)。重复此过程计算Ph，直到获取叶子节点。从分支程序的评估过程可知，评估顺序从初始节点依次到叶子节点，称为顺序评估，顺序评估的优点在于评估层次明显，过程简单。

3.2 分支程序的逆向评估

由分支程序的评估过程可知，评估信息需要交互。若考虑隐私因素，参与对象只能局限于2方，即所有决策节点为1方所有。鉴于此，引入分支程序的逆向评估方法，评估顺序从叶子节点依次逆向直到初始节点，如此节点之间无需信息交互，各个评估节点可分属不同参与方所有。其逆向评估过程如下:假设分支程序为〈{P1，P2，…，P15}，L，R〉，其中P1，P2，…，P10为决策节点，P11，P12，…，P15为叶子节点，评估输入V=v1，v2，v3，v4。如图3、4所示，参与者4开始评估第4层节点，得到相应叶子节点信息1、2、3、4，用此信息替代第4层节点内容。依次逆向评估第3层节点，参与者3将评估得到的第4层节点的叶子节点信息替代第3层节点内容，如此直到唯一一个叶子节点信息替代初始节点内容，评估结束。

图3 分支程序叶子节点评估Fig.3 The leaf nodes evaluation of branch program

图4 分支程序第4层节点评估Fig.4 The fourth layer nodes evaluation of branch program

3.3 基于分支程序逆向评估的安全多方计算协议(协议2)

良好的隐私保护和对决策函数的有效表示是降低安全多方计算协议复杂度、提高协议效率的关键所在。为此，将安全多方计算任务分割成若干个子任务，在分支程序中不同决策节点处理不同子任务。其中，借助基于EVBDD的安全2方计算协议为基础协议，分别处理各个子任务。

基于分支程序逆向评估的安全多方计算协议需要分3步:分支程序的混淆处理、不经意传输选择和安全计算的逆向评估。为保证隐私得到保护，需要将分支程序T转换成混淆的分支程序T′。假设输入V=v1，v2，…，vn，其长度为l，具体算法如下。

算法1分支程序的混淆处理。输入:分支程序T=〈{P1，P2，…，Pk}，L，R〉，pi=〈ti，αi〉为决策节点，其中i=1，2，…，d，pi=〈di〉为叶子节点，i=d+1，d+2，…，k。输出:1)混淆后的安全分支程序T′。2)k对随机l+l′值b1，b2，…，bk。3)2kl对随机边值密钥，其中1≤i≤k，1≤j≤l。

算法步骤为:

1)令Q为集合{1，2，…，k}的随机置换函数，且Q［1］=1。

2)为所有k个决策节点分配节点密钥λ1，λ2，…，λk。

3)对i=1，2，…，k进行遍历。

4)为节点i分配边值密钥，，其中，j=1，2，…，l。

6)对所有节点编号进行混淆，令ι=Q［i］。

7)若Pi是叶子节点，即Pi=〈di〉，则令Si={“label”，di}λι。

8)若Pi是决策节点，即Pi=〈ti，αi〉，则借助基于符号EVBDD的安全2方计算协议来刻画评估该节点，并根据该EVBDD的最终计算结果x，计算x-(b′imod 2l)。

9)若步骤8)的计算结果小于阀值ti，则转向左分支L，否则转向右分支R。其中，L=(Q［L(i)］，KQ［L(i)］)，R=(Q［R(i)，KQ［R(i)］)，所有被评估计算的决策节点标记为C。

10)对决策节点内容进行加密:Si={Ci}λι。

11)协议输出:T′=〈{S1，S2，…，Sk}，k1〉，协议结束。

算法2不经意传输选择。输入:长为l的值V=v1，v2，…，vn，混淆后分支程序T′中的阀值ti，索引αi和混淆值bi。输出:1)s1，s2，…，sk，其中对于任意i有si=vai+(bimod 2l)。2)对于任意i，用边密钥wi1，wi2，…，wil加密si，其中si又等价于vai+(b′imod 2l)。

算法步骤为:

1)各参与方构造相应的同态加密方案，并将公钥发送给服务器。

全省矿业绿色发展现场会在湖州召开（省厅新闻宣传中心） ............................................................................9-6

2)对i=1，2，…，k进行遍历。

3)参与方对各自的隐私输入进行加密，并将加密结果E［vi］发送给服务器。

4)服务器接收公钥以及密文E［vi］，同态计算E［vai+bi］=E［vai］+E［bi］，将结果返回参与方。

5)参与方用私钥对E［vai+bi］进行解密，得到vai+bi。令si=vai+(bimod 2l)=vai+(b′imod 2l)。

6)对j从1到l进行遍历。

在算法2获取边密钥的基础上，参与者利用服务器提供的节点密钥对混淆后的安全分支程序进行逆向计算评估，具体算法如下。

算法3安全计算逆向评估。输入:混淆后的安全分支程序T′、索引向量h、节点密钥λh以及边密钥wi1，wi2，…，wil。输出:叶子节点信息m=T(V)。

算法步骤为:

1)参与方根据节点密钥kh对混淆后的分支程序T′的倒数第2层决策节点(已加密)进行解密，得到决策节点Ch。

2)若决策节点Ch不是初始节点，则利用基于符号EVBDD的安全2方计算协议以及输入wh1，wh2，…，whl对该决策节点进行评估计算，否则转向步骤6)。

3)将上述计算结果(即叶子节点信息)标记为M。

4)将M替代已经解密的决策节点Ch，并令h=h-1。

5)转向步骤2)。

6)评估计算初始节点，获取最终结果m=T(V)，协议结束。

本协议引入分支程序逆向评估技术，并在内部决策节点分配不同子任务，使协议的评估参与者由2方扩展到多方。同时，借助基于EVBDD的安全2方计算协议处理各个不同子任务，提高了决策函数的描述效率，保障了协议的隐私安全。

4 协议的正确性、安全性和效率分析

4.1 正确性分析

1)协议1的正确性。假设Alice成功构造决策函数的EVBDD结构，在约束Xa=(x1，x2，…，xk)下，添加相应虚节点得:f|Xa。Bob无法得知约束前Alice输入的Xa及约束后的EVBDD结构。Alice为约束后EVBDD结构中的各个节点分配1个节点密钥sv，并连同解密后的节点密文一起发送给Bob。同时，Alice根据Bob的可能取值为所有非叶子节点分配1对取值密钥)，假设此时π=0。设Bob得到加密后的节点为pv，其密文中的2条子密文为c1、c2，Bob根据此节点取值π，经过不经意传输协议在Alice对应该节点的取值密钥对中，获得其中1个取值密钥。Bob根据sv和即可解出2条子密文中的1条，得到计算路径中节点pv的下一个节点的位置以及加密后新的2条子密文。重复上述步骤即可到达叶子节点，得到正确计算结果。由此，可知协议的正确性。

2)协议2的正确性。参与方通过算法2不经意传输选择协议得到边密钥wi1，wi2，…，wil，通过算法3获取节点密钥λh、安全分支程序T′和索引向量h。令叶子节点信息为M={m1，m2，…，mn}，参与方1根据输入逆向评估计算出信息M1={m1，m2，…，mk}(1≤k≤n)，用此信息替换参与方1所在决策节点信息。然后，参与方2根据其输入逆向计算出信息M2={m1，m2，…，mt}(1≤t≤k)，用此信息替换参与方2所在决策节点信息。由于分支程序决策节点内部的计算以协议1为基础协议，决策节点内部结构图的计算正确。以此类推，依次逆向评估计算，最终正确计算出唯一的一个叶子信息m。因此，协议2是正确的。

4.2 安全性分析

1)协议1的安全性。假设Alice提供节点密钥为sv(v=1，2，…，n-k)，节点的取值密钥为，。Bob首先获取相应节点密钥，然后通过1-out-of-2不经意传输协议获取唯一的取值密钥，即和两者中只能获取其中一个，同时Alice无法得知Bob的选择信息，这就确保了计算双方的隐私都能得到保护。Bob用获取的节点密钥和该节点的取值密钥可解密出该节点在相应取值后的下一节点，而且是唯一的。以此类推，能得到唯一的一条路径安全地到达叶子节点。由此可见，在这条唯一计算路径的求解过程中，参与者的信息都得到了保护。

2)协议2的安全性。服务器通过算法1混淆后的分支程序是安全的。算法2通过同态加密E［vai］对输入数据进行加密，并通过混淆值si=vai+(bimod 2l)=vai+(b′imod 2l)对输入数据进行混淆，保证了参与各方输入隐私的安全性。参与方在算法2中通过不经意传输选择协议得到不同分支中的唯一一个分支边密钥，这里的唯一性是由OT12所决定的。结合节点密钥计算出唯一的叶子节点信息。由于边密钥的唯一性，确保评估计算过程中信息安全。由于决策节点的内部评估以协议1为基础协议，其安全性分析同协议1。此外，逆向评估计算避免了参与各方之间的信息交互，提高了协议的安全性。因此，协议2是安全的。

4.3 效率分析

5 结束语

针对传统决策函数表示计算复杂度高、编码规模大以及参与者局限于2方问题，提出一种基于边值二叉决策图和分支程序逆向评估的解决方案。与文献［9］相比，不仅将协议扩展到多方，而且降低了决策函数的复杂度，提高了协议效率。

由于分支程序逆向评估计算仅考虑了2分支的情况，在下一步工作中，可对多分支程序逆向评估计算进行研究。此外，基于EVBDD的决策函数描述方式，由于边权重因子的出现，协议中节点的存储变得更加复杂。因此，基于EVBDD决策函数描述的优化将是今后研究的方向。

［1］Yao A.Protocols for secure computations［C］//Proceedings of the 23th Annual Aymposium on Foundations of Computer Science，IEEE，1982:160-164.

［2］Katz J，Malka L.Secure text processing with applications to private DNA matching［C］//Proceedings of the 17th ACM Conference on Computer and Communications Security，2010:485-492.

［3］李顺东，王道顺.基于同态加密的高效多方保密计算［J］.电子学报，2013，41(4):798-803.

［4］Yao A.How to generate and exchange secrets［C］//Proceedings of the 27th Annual Symposium on Foundations of Computer Science，IEEE，1986:162-167.

［5］Kruger L，Jha S，Goh E，et al.Secure function evaluation with ordered binary decision diagrams［C］//Proceedings of the 13th ACM Conference on Computer and Communications Security，2006:410-420.

［6］古天龙，何仲春，常亮等.基于符号ADD和线性多分支程序的分类算法安全评估［J］.电子学报，2014，42(5):940-947.

［7］Kolesnikov V，Schneider T.A Practical Universal Circuit Construction and Secure Evaluation of Private Functions［M］//Financial Cryptography and Data Security.［S.l.］:Springer Berlin Heidelberg，2008:83-97.

［8］Brickell J，Porter D，Shmatikov V，et al.Privacy-preserving remote diagnostics［C］//Proceedings of the 14th ACM Conference on Computer and Communications Security，2007:498-507.

［9］Mohassel P，Niksefat S.Oblivious Decision Programs from Oblivious Transfer:Efficient Reductions［M］//Angelos D.Financial Cryptography and Data Security.［S.l.］:Springer Berlin Heidelberg，2012:269-284.

［10］Rabin M.How toExchange Secrets by Oblivious Transfer［R］.Harvard University，1981.

［11］Paillier P.Public-key cryptosystems based on composite degree residuosity classes［C］//Advances in Cryptology-EUROCRYPT’99.［S.l.］:Springer Berlin Heidelberg，1999:223-238.

［12］古天龙，徐周波.有序二叉树决策图及应用［M］.北京:科学出版社，2009:17-57.