论文研究 一类基于安全多方计算的数据挖掘隐私保护模型的可行性分析.pdf

阐述安全多方计算（SMC）密码原语在分布式数据挖掘隐私保护中的相关应用后，对方炜炜等人提出的基于SMC的隐私保护数据挖掘模型进行分析，论证该类模型所基于的离散对数公钥加密协议不具有全同态的特性，并用简单实例验证。从而得出该类数据挖掘隐私保护模型是不可行的。第2期景征骏,等:一类基于安全多方计算的数据挖掘隐私保护模型的可行性分析545定理2基于离散对数困难问题的加密协议( CSBDLP)设数宁签名后1,有限域上的离散对数问题的难解性就成为很定的密文运算不具有全同态特性,在密文矩阵运算中仅加运算多公钥密码系统安全的理论基础,而木原根是产生离散对数问①同态,而乘运算则不同态。题的关键。根据定义3可知,若n为素数,则原根b存在证明釆用1.2节加密协议的密钥参数对密文矩阵的加、(ord=φp(n)=n-1),且模n是一个乘法循坏群Z\0},群乘运算进行推导。的阶zn=n-1。由本原根的性质知道,本原根b的乘法幂1)密文矩阵加法现取明文空间的矩阵将遍历群Z。的每个元素。囚此求解整数a对模n的以b为CSBDLP加密协议加密后得密文矩阵f(A)=(A+m)·底的离散对数的概率与在n-1个元素集合中随机选取一个元E mod n及f(C,x)=(C+)· kc mod nc令密文矩阵f素的概率是不可区分的。也就是说,当n为大素数时求解离散(Ax)和f(C相加的结果为矩阵Q,则矩阵的每个元素对数问题是困难的。虽然素数一定存在本原根1,可大部分Q按密文运算规则计算如下合数是不存在本原根的。根据定理1可知,定义5(文献[14Q;=fA×h);f(Cn×h):的定义6)描述的 CSBDLP加密协议中的参数n(n=Pxq)没有+r·phg mod n+Kc·(Crnc((A0+r,),Mmn+2,(C+,p),m则m)m0n=从而该加密协议的安全性要远低于文献141中所证明的安全C..+2性。在下面的实例验证中为了获得模n的循环群的阶,可分别因此(Q)=(b)··1·(A1;+C,+2m)modp·q取素数P、q的本原根(r1,r2),其满足ord22=lm(p-1,q-modp,因为b=(s:)modn,由定义5可得f(O,)=A,+1),即模n的阶为(P-1,q-1)的最小公倍数。通过工具C;,即f(A,+C:)=f(4,)f(C,)。从而f(4+C)=f(A) Mathematica对基于 CSBDLE加密协议的密文矩阵运算进行实④f(C)。验、本文随机选取如下的原始数据作为此隐私保护数据挖掘模2)密文矩阵乘法现取明文空间矩阵A和Bxn,经型的输入数据CSBDLE加密协议加密后得密文矩阵f(A)=(A+p)·kmodn及f(B)=(B+P)· ksmod n。令密文矩阵f(A)和f(B)相乘的结果为矩阵Nn,则矩阵的每个元索N按密文运算规则计算为N,;=(f(4),⑧H(B)1)①(f(4);2f(B)2,)(①…①((4);密钥参数:Pk:{r=7,p=17,q=13,n=pXq=221,b=6f(B))=((KA·(Ask:{k4=11,kB=3};随机选择s=32。因为p、q的本原根分别(kB·(B1,;+rp)· h gmod n))(…是3和2,所以取b=6,其满足bmp-4)=1modn。再计算(KA·(A.b+Pp)·kmdn)·(kB·(Bh,+mp)·hmxn))KA=148、K=181和解密密钥t′=2(!'满足b≡s·lcm(k1((KA.(A u+rp).kA mod n).(KB(Buj+rp).kgmod n))AiR)mod n)1+p)·k1modn)·(2,1·(B数据加密:71125rp)· hamod n))modn=(s:l)2∑((l;,+EA=M(V4+r:p)(k,An),n7=/71177171125179(A1.·B2,+(A.+Bn1)·m+r2p2)modn9021因此,根据定义5中的加密协议求密文乘法的逆得FB=Md.(a+r,p)·(kBA),n÷679011344f-1(N,)=(b′)-1·(s:l)2·∑(4.…·Bn+(A;a+B)Pp+r2n2)modp· gmod p=(s·l)∑A,n·B密文矩阵运算(E、E。分别表示密文矩阵加、乘运算的结果)也就是说f(M)≠∑A·B,从而,(A)②f(B)≠A·B)根据定义2中同态条件并结合以上的推导1)和2),可以E出=EA团Eg=ModK4·EA+KB·Eg,n]=得出定理2。证毕57165推论1基于( SBDLP公钥加密协议的多元线性回归隐Ea=ETEp= Modr Transpose[ Mod K, *EA, n11私保扩模犁不可行。ModL KB k EB, n ),n证明当数据挖掘方在使用最小二乘估计法求解回归系185119数吋,所用的数据都是参与方使用 CSBDLP公钥加密协议加密151126后得到密文矩阵,而密文空间的矩阵运算将使用④、⑧的运算密文解密(V、V分别表示Eo、E。解密后的值)规则。因此,根据定理2易得此推论。证比V= Mod[ Mod[ Power Mod[b∧k eg, n],P]推论2基丁( ' SBDLP公钥加密协议的隐私侏护聚类模57201型是不可行的Ⅵod[Md43证明同推论1211293实例验证Va= Mod[ Mod[ PowerMod[ b∧t’,-1,n]*Es,n],P185119在 Elgamal提出了具有实际应用的 ElGamal公钥体制和15112621,1711612546·计算机应用研究第31卷对原始数据进行加、乘运算,可以发现V+Vg=Vs,而[5张鹏,唐世渭.一和有效的隐私保护关联规则挖掘方法[J,软件学报,2006,17(8):1764-1774上面的实例进一步验证了基于 CSBDLP加密协议的密文[6 PINKAS B, Cryptographie techniques for privaey preserving data min-矩阵运算不具有全同态特性。从而,文献[14]试图利用此密ing[ J. ACMSIGKDD Explorations Newsletter, 2002, 4(2):12文运算规则设计的多元线性回归隐私保护模型是不能正确地[71 CLIFFTON C, KANTARCIOGLU M, VAIDYA J. Tools for privac恢复出回归系数佔计值β。preserving distributed data mining [J. ACM SIGKDD ExplorationsNewsletter,2004,4(2):28-34.4结束语8 DOSIII N. A novel approach for cryptography technique on perturbeddala for distributed environment[J]. International Journal on Cryp隐私保护是数据挖据领域中重要的课题之一,并以完成准tography and Information Security, 2012, 2(3): 101-106确的知识发现的同时不泄露敏感的原始数据为目标。文献[9 AGGARWAL C,YUPS. Privacy preserving data mining models and[14,15]试图基于全同态思想设计多方安全的密文计算,并以algorithms M. Berlin: Springer-verlag, 2007: 67此构建数据挖掘隐私保护模型,确保各个参与方的原始数据在101A, YUCEL S. Privacy preserving clustering on horizontally parti不可信的第三方进行的数据挖掘过程中不被泄露。此类通过tioned data[ J. Data Knowledge Engineering, 2007, 63(2)设计高效的SMC协议来完成数据隐私保护的方法是PPDM技[IⅠ刘英华,杨炳儒,马楠,等.分布式隐私保沪数据挖掘硏究[冂].计术发展的方向之,是种有意义的尝试。但文献[14,15]所算机应用研究,2011,28(10):3606-3610基于离散对数问题加密协议( CBSDLP)设计的密文运算规则12」DUwL,INYs. Privacy preserving multivariale statistical analy-并不具有全同态特性。因此,在此基础上构建的多元线性回归sis: linear regression and classifieation[ C]//Proc of the 4th SIAW隐私保护模型和聚类隐私保护模型都是不可行的。且前,尽管InlerTatinnal Cunferenre on Dala Mining. [S. L.-: IEFE. Press, 2004已纤设计出基于格问题的全同态加密方案,,可其效率极222-233低,还不具有实用性。除了不断优化基于格的全同态方案,研131 VAIDYA,IoNc. Privacy preserving K-means over verticallypartitioned data [C//Proc of SIGKDD International Conference on究者们也不断尝试基于经典数论难题(如离散对数问题)去设Knowledge and Data Mining. New York: ACM Press, 2003: 490-510计高效的同态加密方案。然而,是台能够构造出高效且安全的「141方炜炜,仁江,夏红科一种异构分布的多元线性回归隐私保护模基于离散对数问题的全同态加密方案仍然是一个公开的问题。型「J1.计算机研究与发展,2U11,48():1685-16)1参考文献[15]方炜炜,杨炳儒,复红科.基于SMC的隐私保护滎类模型[J].系统工程与电子技术,2012,34(7):1505-1511[1] YANG Bing-ru, GAO Jing, LI Lin-na. Research overview of regulaL 16 ROSEN K IL. Elementary number theory and its applications[ M].5thtions in the process of dynamic mining [J]. Journal of Computaed. New York Person Educat ion 2005.245tional Information Systems, 2006, 2(3): 973-979[2 AGRAWAL. R, SRIKANT R. Privacy preserving rala mining[C]/17] ELGAMAL T. A public key cryptosystem and a signature schemeProc of acm sigmod international conference on management ofbased on discrete logarithms[J. IEEE Trans on Information andData. New York. ACM Press. 2000: 439-450Theory,1985,T-31(4):469-47[3] ISALAM M, BRANKOVIC L. Privacy preserving data mining: a noise [18] GENTRY C. A fully homomorphic encryption scheme [D] [S1.addition framework using a novel clustering technique. J].KnowStanford Lniversity, 2009ledge-based Systems, 2011, 2(1): 1214-1223[19 BRAKERSKI Z, VAIKUNTANATHAN V. Efficient fully homomor「4刘峰,薛安庹,王伟.一种隐私保护关联规则挖据的混合算法phic encryption from( standard)LWELC]//Proc of the 52nd Annual「J.计算机应用研究,2012,29(3):II07-1Il0.Symposium on Foundations of Computer Science. 2011: 97-106(上接第539页)ence on Intelligent Networking and Collaborative Systems. 2011: 668[9 KHADER D. Attribute based grou2007/241[EB/OL].(2007).htp:// eprint.iaer.org/2007/241[17 MAULLER S, KATZENBEISSER S, ECKER'TC. Distributed attri-[1O] LI Jin, KIM K Attribute-based ring signatures[EB/OL].[2008-07bute-based encryption| C|//Proc of the I l th International Conference12.http://eprint.iacr.og/2008/394on Information Security and Cryptology. 2008: 20-36[11 HERRANZ J, LAGUILL. F, LIBERT B, et al. Shorl altribute-[18 BONEH D, FRANKLIN M. Identity-based encryption from the Weilpairing [C/LNCS, vol 2139. Berlin: Springer-Verlag, 2001: 213P[C//LNCS, vol 71lin: Springer-Verlag, 2012: 51-67[12] BONEH D, BOYEN X, SHACHAM H Short group signaturesLCl// [IU] WATERS B. Efficient identity-based encryption without random ora-cles[ C|//Lecture Notes in Computer Science, vol 3494. BerlinLNCS, vol 3152. Berlin: Springer-Verlag, 2004: 41-55Springer-Verlag, 2005 114-12713] CHASE M. Multi-authority attribute based encryption[ C]//Leeture [20]GE A J, MA C G, ZHANG Z F. Attribute-based signature schemeNotes in Computer Science, vol 4392. Berlin: Springer-Verlag, 2007with const Hnt size signature in the slandard m(lel J. IET Informa515-534tion Security, 2012, 6(2): 47-54[14 LIN Huang, CAO Zhen-fu, LIANG Xiao-hui, et al. Secure threshold[21] HU Chun-qiang, ZHANG \an, Ll Hong-juan, et al. Body area net-multi-authority attribute hased encryption without a central authoritywork security: a fuzzy attribute-basedon scheme[J. IEEE[C]//Lecture Notes in Computer Science, vol 5365. Berlin: Springer-Journal on Selected Areas in Communications, 2013, 31(9): 37Ⅴerag,2008:426-436L22] CIIEN Yan-li, CIIEN Jun-jun, YANG Geng. Provable secure multi[15]孙昌霞,马文平,陈知凤.多授权中心的基于属性的签名[J.四authority attribute based signatures[ J] Journal of Convergence In川大学学报:工程科学版,2011,43(1):83-86formation Technology (JCIT), 2013, 8(2Llf6」CA0pan, ZIlAO Bao-kang,wANGⅪiao-feg,etl. Multi; authority[23]张磊,曹珍富,一个适合分布式网络的属性基加密方案J].上海attribute-based signature[C]//Proc of the 3rd International Confer-交通大学学报,2010,44(11):1507-1512