基于符号OBDD的保护隐私集合运算协议

陈益师,古天龙,徐周波,宁黎华

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

基于符号OBDD的保护隐私集合运算协议

陈益师,古天龙,徐周波,宁黎华

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

针对保护隐私的集合成员判定协议和集合相等判定协议泄露信息的缺陷,提出基于符号OBDD的解决方案。将集合成员编码成二进制码,提取集合的特征函数;以连分数和Cantor编码为桥梁,将集合编码为自然数,构造该自然数的比较相等函数;利用OBDD表示这2类函数,结合基于OBDD的安全函数评估协议,提出解决保护私有信息的集合相等判定问题和集合成员判定问题的2个协议。所提出的协议克服了已有解决方案存在的安全问题,且有较好的执行效率。

集合成员判定;集合相等;连分数;Cantor编码

安全多方计算[1]是指在一个分布式网络中,互不信任的参与者能够在不泄露各自私有输入信息情况下合作执行某项可靠计算任务。这一概念由Yao[2]首次提出,被人们广泛研究。由于计算效率原因,采用通用理论方案[3-5]解决安全多方计算问题中一些特殊问题不切实际,需用特殊方案才能达到高效性[1]。

在安全多方计算中,保护隐私的集合运算是研究热点。保护隐私的集合运算研究的主要问题:n个参与者提供各自秘密输入,如何在不透露参与者秘密输入的前提下,通过相应集合运算,得到输出结果。这些集合运算包括:求并集,求并集的势,求交集,求交集的势,求集合的包含关系,集合成员判定,判断集合是否相等或相交等。在此研究其中的集合成员判定问题和集合相等关系判断问题。解决这2个问题的协议有很强的应用背景,例如:在保护客户信息前提下,银行C想要判断某客户是否在银行D的不良信用客户名单中;互不信任的通信者,想要在不泄露自己口令的前提下判断双方口令是否一致。2个问题的安全计算协议输出为1 bit,如0表示b不属于集合A或集合A与集合B不相等,而1则相反。

李顺东等[6]利用可交换加密提出一个集合成员判定安全计算协议,通过该协议构造解决集合交集势的方案。Freedman等[7]利用多项式表示集合,通过哈希组分配降低多项式阶数以提高计算效率,利用同态加密机制安全计算多项式的值,解决集合成员判定问题,进而提出参与双方的集合是否有交集和交集势的解决方案。Kissner等[8]改进文献[7]中集合的多项式表示方法,使集合的多项式表示不仅可用于解决集合交集问题,而且适用于集合求并集问题和求差集问题。但是,该协议需要门限同态加密机制,解密过程比较复杂,需要分享解密密钥的各个成员共享一个解密值。李荣花等[9]用多项式表示待比较的集合,利用不同多项式判断集合包含关系的方法,结合叠加密和加法同态加密机制分别提出3种协议,用于判断集合包含关系,但是,这3种协议都会泄露一方参与者的信息。豆永丽等[10]采用混沌加密机制和同态加密机制,借助第3方判断提出2个协议,用于解决保护隐私的集合成员判定问题,但是,这2个解决方案会泄露集合的成员个数,第3方会得到比较结果,造成信息泄露。夏峰等[11]等利用格上LWE(learning with error)困难性假设,提出能够抵抗量子攻击的安全判断2数是否相等的解决方案,并以该方案为基本模块,解决集合成员判定,求集合交集和集合相等的判定,该方案同样会泄露集合的成员个数。

当前,大部分保护隐私的集合运算协议利用多项式表示集合。但是,由于多项式系数个数决定了集合大小,协议不可避免会泄露某个参与者集合成员个数,且加密方式为复杂度较高的同态加密。其他对集合成员加密的解决方案虽然不暴露集合成员的值,但会泄露集合成员个数以及集合成员比较情况。鉴于此,利用有序二叉决策图(OBDD)表示集合特征函数和比较相等函数,提出基于OBDD安全评估协议的集合成员判定协议和判断集合相等协议,避免了泄露参与者集合成员个数以及成员比较情况。

1 预备知识

定义1 连分数。连分数是一种重要的实数表示方法,其一般形式为:当r1为整数,r2,r3,…均为正整数时,称式(1)为连分数,记为[r1,r2,r3,…],并称r1,r2,r3,…为该连分数的部分商。当部分商的个数有限时,称为有限连分数。

Hardy等[12]证明了当限制连分数最后一位分量不为1时,实数与连分数一一对应。

定义2 Cantor编码[13]。称如下函数h(x,y)对自然数对(x,y)的编码方式为Cantor编码:

Cantor编码建立了自然数对与自然数的一一对应关系。

定义3 不经意传输协议。1-out-of-n不经意传输协议(OTn1)是一个2方交互协议。协议包括发送者和接收者,其中发送者有n个秘密消息mi(i=0, 1,2,…,n),接收者拥有一个选择数字b(1≤b≤n),执行协议后接收者获得选择的mb,但是不知道发送者中的其他mi的内容,发送者不知道接收者的选择数字b。

这里应用1-out-of-2(OT12)不经意传输协议,可实例化为文献[14]中的高效解决方案。

定义4 半诚实参与者。在执行协议的过程中会忠实地履行协议,但会保留所有中间结果,试图从中间结果推导出协议之外信息,这样的参与者称为半诚实参与者。

一个恶意参与者在执行协议过程中可能任意地偏离协议、拒绝参与协议、更换自己的本地输入、甚至可能终止协议。Goldreich指出:在半诚实参与者条件下的安全计算协议中,利用比特承诺和零知识证明可以迫使恶意参与者以半诚实方式参与执行,否则就会被发现[1]。因此,很多时候只需要研究半诚实参与者条件下的安全多方计算解决方案即可。在此,假设协议参与者都是半诚实的。

定义5 OBDD(ordered binary decision diagrams)[15]。对于从{0,1}n到{0,1}的布尔函数f(x1, x2,…,xn),一个OBDD就是在给定变量序π下用于表示布尔函数的f(x1,x2,…,xn)的有向无环图。

在OBDD的图形表示中,一般非终节点用圆圈表示,终节点用方框表示。每个非终节点均具有2个输出分支弧,将非终节点和2个分支节点连接起来,当非终节点变量取1时输出弧记为1-边,用实线表示;当非终节点变量取0时输出弧记为0-边,用虚线表示。

例如布尔函数f=x1x2+x3,在给定变量序π: x1＜x2＜x3下对应的OBDD如图1所示。

图1 函数f=x1x2+x3的OBDD表示Fig 1 OBDD for the function f=x1x2+x3

定义6 对称加密。对称加密是指采用单钥密码系统的加密方法,同一个密钥可以同时用作信息的加密和解密,也称为单密钥加密。在对OBDD中的节点进行加密时,使用的对称加密机制要求语义安全。所谓语义安全类似于Shannon给出的完善保密理论,要求从密文中不能得到有关明文的任何消息。相对非对称加密机制,对称加密机制具有加解密算法开销小以及密钥生成算法简单等优点。

2 解决方案

2.1 基于OBDD的安全函数评估协议

基于OBDD的安全函数评估由Louis Kruger等[16]提出,具有良好的协议效率,可应用于保护隐私的集合成员判定和集合相等关系判定。假设协议的参与者为服务端Alice和客户端Bob,协议的主要步骤为:

1)Alice利用变量序为x1＜x2＜…＜xn的OBDD表示函数f(x1,x2,…,xn)。函数f的自变量x1,x2,…,xk对应Alice的输入(i1,i2,…,ik); xk+1,xk+2,…,xn对应Bob的输入(ik+1,ik+2,…, in)。

2)Alice用其输入约束OBDD,添加伪节点和混淆节点后进行混淆加密,将混淆加密后的OBDD密文发送给Bob。

3)Bob根据其输入,与Alice共同执行不经意传输协议,得到解密OBDD密文的取值密钥。

4)Bob根据得到的取值密钥解密OBDD密文,得到OBDD的叶子节点信息,即函数f(x1,x2,…, xn)的计算结果。

由于使用语义安全的对称加密对OBDD节点进行加密,且Alice与Bob进行交互时执行不经意传输,双方均不能得到对方的输入。

2.2 集合成员判定安全计算协议

OBDD表示集合的特征函数:设一个集合S= {赤色,橙色,红色},若将S中的每一个成员编码为:赤色-00,橙色-01,红色-10,则集合S的特征函数为f(x1,x2)=x1′x2′+x1′x2+x1x2′。规定变量序π为:x2＜x1,存在唯一的OBDD表示集合S的特征函数,如图2所示。表示集合特征函数的OBDD可作为基于OBDD的安全函数评估的输入,解决集合成员判定问题。

图2 集合S的OBDD表示Fig 2 OBDD for the set S

保护隐私的集合成员判定问题:假定Alice拥有一个成员为自然数的秘密集合SA={a1,a2,…, an},Bob拥有一个自然数b,双方想判断b∈SA或者b∉SA,但都不想泄露自己的信息。

协议1 保护隐私的集合成员判定协议。输入: Alice秘密输入集合SA={a1,a2,…,an},Bob秘密输入b。输出:b∈SA或b∉SA。

协议步骤:

1)Alice和Bob共同确定SA成员和b所采用二进制编码位数k。

2)Alice将SA中的各个成员编码为k位的二进制码,并根据二进制码得到集合的特征函数。Bob将b编码为二进制码。

3)Alice利用OBDD表示集合的特征函数,添加伪节点对其进行混淆加密,将OBDD密文发送给Bob。

4)Bob根据b的二进制码与Alice共同执行不经意传输协议,得到取值密钥,利用取值密钥计算叶子节点信息,即b∈SA或b∉SA。

5)Bob将判断结果告诉Alice。

2.3 判断集合相等的安全计算协议

有限集合转换成自然数:假设有限集合S中的成员为非零自然数,按如下步骤可将集合S转换成自然数。

1)将集合S中的成员按递增顺序排序为一个递增序列,该序列可看成分量互异的连分数的部分商,求出部分商对应的分数。

2)分数的分子和分母看成自然数对,经过Cantor编码得到一个自然数。

OBDD表示比较相等函数:设f(x,c)为比较相等函数,其中x为函数输入,c为待比较常数,函数输出为0或1。当x=c时,函数输出为1;当x≠c时,函数输出为0。将比较相等函数表示为OBDD的步骤为:假设函数输入x和待比较常数c的取值范围为[0,N],则需要log2(N+1)⏋位变量x1,x2,…, xlog2(N+1)⏋的OBDD进行表示。若c的二进制码为c1,c2,…,clog2(N+1)⏋,则变量x1,x2,…,xlog2(N+1)⏋分别取值为c1,c2,…,clog2(N+1)⏋的分支路径指向的叶子节点的值为1;变量的其他取值确定的分支路径指向的叶子节点值为0。比如一个比较相等函数为f(x,c),其中x和c的取值范围为[0,15],待比较常数c=10,则OBDD表示该比较相等函数如图3所示。

图3 比较相等函数的OBDD表示Fig 3 OBDD for the equal function

保护隐私的集合相等关系判定问题:假定Alice和Bob各自拥有一个成员为非零自然数的秘密集合SA={a1,a2,…,am}和SB={b1,b2,…,bn},双方想判断SA和SB是否相等,但都不想泄露自己的信息。

协议2 集合相等关系判定协议。输入:Alice秘密输入集合SA={a1,a2,…,am},Bob秘密输入SB={b1,b2,…,bn}。输出:SA=SB或SA≠SB。

协议步骤:

1)Alice和Bob各自将集合成员按递增顺序排序,2个有序集合经过连分数和Cantor编码转换成自然数NA和NB。

2)Alice和Bob各自将NA和NB编码成k位的二进制码,其中k大于log2(NA+1)⏋和log2(NB+1)⏋中的较大值。

3)Alice利用OBDD表示待比较常数为NA的比较相等函数,添加伪节点并对其进行混淆加密,将OBDD密文发送给Bob。

4)Bob根据NB的二进制码与Alice共同执行不经意传输协议,得到解密OBDD密文的取值密钥,利用取值密钥计算得到叶子节点信息,即SA=SB或者SA≠SB。

5)Bob将判断结果告诉Alice。

3 分析

3.1 正确性分析

所提出的集合成员判定协议和判断集合相等协议基于OBDD安全函数评估协议,文献[10]证明了OBDD安全函数评估协议的正确性。因此,只对OBDD表示集合、将集合表示成自然数以及OBDD表示比较相等函数的正确性进行分析。

1)集合特征函数的OBDD表示的正确性:将集合成员编码成n位二进制码,存在唯一一个n变量布尔函数f(x1,x2,…,xn),使得当输入的变量值x1, x2,…,xn为某个成员的二进制码时,布尔函数的输出为1,否则布尔函数的输出为0。而OBDD是给定的变量序π用于表示布尔函数的f(x1,x2,…,xn)的规范式,因此,可用OBDD表示集合。当变量x1,x2,…,xn取集合成员的二进制码时,有一条路径指向值为1的叶子节点;当变量x1,x2,…,xn不是取集合成员的二进制码时,有一条与输入对应的路径指向值为0的叶子节点。因此,利用OBDD可正确表示集合,可用于集合成员判定协议。

2)有限集合通过连分数和Cantor编码转换成自然数的正确性:非零自然数有限集合的成员按递增顺序排序为一个递增序列,此序列可看成分量互异的连分数的部分商,而连分数与对应的分数存在一一对应关系,不同的有限集合经过递增排序得到的递增序列通过连分数为桥梁编码为不同的分数。如此转换,不同的集合对应不同的分数。另外,分数的分子和分母组成的自然数对通过Cantor编码与自然数一一对应,即分数与自然数通过Cantor编码建立一一对应关系。因此,不同的有限集合通过连分数和Cantor编码转换成不同的自然数,继而可由自然数的比较相等判断集合相等关系。

比较相等函数的OBDD表示与集合特征函数的OBDD表示类似,当OBDD变量取待比较常数的二进制码时,得到唯一一条指向值为1的叶子节点的路径。

综上,由OBDD表示集合的特征函数、集合通过连分数和Cantor编码表示为自然数以及OBDD表示比较相等函数的正确性,结合基于OBDD安全函数评估协议的正确性,可知协议1、2均可以得到正确的计算结果。

3.2 安全性分析

在半诚实参与者模型中,对称加密机制具有语义安全性且不经意传输协议安全假设下的安全性分析。

协议参与者双方交互基于OBDD安全函数评估协议的执行过程。此过程中Alice用语义安全性的对称加密机制混淆加密OBDD,使Bob得到OBDD密文后,只能通过执行不经意传输协议得到与其输入对应的取值密钥和上一节点的节点密钥共同解密。在一次不经意传输协议中,Alice不会获知Bob的输入。另外,由于执行一次不经意传输协议只能得到与其输入对应的取值密钥,不能得到另外分支的取值密钥。因此,Bob只能解密得到与其输入对应的下一节点标签和节点密钥,n次不经意传输得到唯一一条从源节点指向表示集合运算结果的叶子节点的路径。因此,在整个协议过程中,不经意传输协议和节点信息加密的安全性保护了Alice和Bob的各自隐私。

3.3 效率分析

保护隐私的集合运算协议是一种分布式安全计算协议,其计算复杂度用协议中各种类型计算的执行次数描述;而通信复杂度通常用通信轮数描述。协议参与者交互过程中只进行模指数运算,其他运算均可在准备阶段完成。另外,相对于协议中的其他运算,如异或运算和加减乘除运算,模指数运算需要较高的运算代价。因此,协议中只考虑模指数运算的计算代价。由于执行不经意传输协议,协议引入模指数运算,协议采用文献[14]中效率较高的不经意传输协议,2个协议所需模指数运算次数为2n,n为在协议1、2中OBDD中的变量个数。另外,2个协议的通信轮数均为4。

3.4 协议的扩展性分析

保护隐私的多方集合成员判定:假设有n个参与者P1,P2,…,Pn;P1拥有一个秘密集合,希望在不泄露参与者信息的前提下计算P2,P3,…,Pn中拥有的自然数属于P1集合的个数。

对协议1作如下修改,可由2方协议拓展到多方协议,用于解决保护隐私的多方集合运算问题。Alice对OBDD进行混淆加密时,引入加法同态加密机制对叶子节点进行加密后,发送给P2,P3,…,Pn; P2,P3,…,Pn与P1进行不经意传输得到取值密钥,对OBDD进行遍历得到各自利用加法同态加密机制加密的叶子节点信息;P2,P3,…,Pn将叶子节点信息相加后传递给P1;最后P1解密得到P2,P3,…,Pn中拥有的自然数属于P1集合的个数。

协议2经过类似修改,可得到在不泄露参与者信息前提下,计算P2,P3,…,Pn中拥有秘密集合与P1集合相同的个数的协议。另外,在协议2中,若集合的成员不经过排序,则可用于解决保护隐私的向量比较相等问题。

4 结束语

协议1、2构建集合的特征函数和集合通过连分数以及Cantor编码转换成自然数的比较相等函数,基于OBDD的安全函数评估协议对集合的特征函数和比较相等函数进行安全评估,分别用于解决保护隐私的集合成员判定和集合相等关系判定问题。避免了多项式表示集合的解决方案和对集合成员进行加密的解决方案泄露集合成员个数和集合成员比较情况等信息安全问题。给出将协议1、2由2方拓展到多方的方法。由于其他保护隐私的集合运算也存在类似安全问题,今后工作针对其他集合运算构造安全性能更高的安全计算协议。

[1] Goldreich O.Foundations of Cryptography,Volume 2, Basic Applications[M].Cambridge:Cambridge University Press,2009:24-29.

[2] Yao A.Protocols for secure computations[C]//2013 IEEE 54th Annual Symposium on Foundations of Computer Science,1982:160-164.

[3] Henecka W,Sadeghi A R,Schneider T,et al.TASTY: tool for automating secure two-party computations [C]//Proceedings of the 17th ACM Conference on Computer and Communications Security,2010:451-462.

[4] Goldwasser S.Multi-party computations:past and present[C]//Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing,1997:1-6.

[5] Yao A.How to generate and exchange secrets[C]//27th Annual Symposium on Foundations of Computer Science.IEEE,1986:162-167.

[6] 李顺东,司天歌,戴一奇,集合包含与几何包含的多方保密计算[J].计算机研究与发展,2005,42(10):1647-1653.

[7] Freedman M J,Nissim K,Pinkas B.Efficient private matching and set intersection[C]//Advances in Cryptology-EUROCRYPT 2004.Springer Berlin Heidelberg, 2004:1-19.

[8] Kissner L,Song D.Privacy-preserving set operations [C]//Advances in Cryptology-CRYPTO 2005,2005: 241-257.

[9] 李荣花,武传坤,张玉清.判断集合包含关系的安全计算协议[J].计算机学报,2009,32(7):1337-1345.

[10] 豆永丽,王海春,康剑.集合成员判定问题的安全多方计算解决方案[J].计算机应用,2013,33(12):3527-3530.

[11] 夏峰,杨波,张明武,等.基于LWE的集合相交和相等的两方保密计算[J].电子与信息学报,2012,34(2): 462-467.

[12] Hardy G H,Wright E M,Heath-Brown D R,et al.An Introduction to the Theory of Numbers[M].Oxford: Clarendon Press,1979:22-25.

[13] 张立昂.可计算性与计算复杂度导引[M].北京:北京大学出版社,2003:51-52.

[14] Tzeng W.Efficient 1-out-n oblivious transfer schemes [C]//Public Key Cryptography-5th International Workshop on Practice and Theory in Public Key Cryptosystems,2002:159-171.

[15] 古天龙,徐周波.有序二叉决策图及应用[M].北京:科学出版社,2009:22-40.

[16] Kruger L,Jha S,Goh E J,et al.Secure function evaluation with ordered binary decision diagrams[C]//Proceedings of the 13th ACM Conference on Computer and Communications Security.New York:ACM Press, 2006:410-420.

编辑:翁史振 见习编辑:陈汝伟

Privacy-preserving set operations protocols based on symbolic OBDD

Chen Yishi,Gu Tianlong,Xu Zhoubo,Ning Lihua
(Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China)

Because the existing set member decision protocol and set equality protocol leak the private information of the sets, the protocols based on ordered binary decision diagram are proposed.The characteristic function of a set is extracted by encoding the set members into binary code.In addition,using continued fraction and Cantor coding as a bridge,the set is encoded into a natural number,and then an equal function of the natural number is constructed.OBDD is used to represent the two kinds of functions,combined with security function evaluation protocols based on the OBDD,set member decision problem and set equality problem are solved.Compared with the existing protocols,the two new ones can solve the security issues,and they have good execution efficiency.

set member decision;set equality;continued fraction;Cantor coding

TP309

:A

:1673-808X(2015)04-0315-06

2015-03-16

国家自然科学基金(61100025,61262030,61363030);广西自然科学基金(2014GXNSFAA118354)

古天龙(1964―),男,山西芮城人,教授,博士,研究方向为形式化方法、符号计算、知识工程。E-mail:cctlgu@guet.edu.cn

陈益师,古天龙,徐周波,等.基于符号OBDD的保护隐私的集合运算协议[J].桂林电子科技大学学报,2015,35(4):315-320.