基于安全多方计算的隐私保护图查询.pdf
《基于安全多方计算的隐私保护图查询.pdf》由会员分享,可在线阅读,更多相关《基于安全多方计算的隐私保护图查询.pdf(9页珍藏版)》请在咨信网上搜索。
1、数据与计算发展前沿,2 0 2 3,5(5)第5 卷第5 期2 0 2 3年10 月Vol.5No.5Oct.2023专刊:数据要素安全高效流通的关键技术Special Issue:Key Technologies for Safe and Efficient Circulation of Data ElementsMulti-Party ComputationISSN2096-742XCN 10-1649/TPdoiePIcOPersistent Identifiers foreResearch文献CSTR:32002.14.jfdc.CN10-1649/TP.2023.05.008文献DO
2、I10.11871/jfdc.issn.2096-742X.2023.05.008页码:98-10 6获取全文基于安全多方计算的隐私保护图查询汤世源,袁野北京理工大学,北京10 0 0 8 1摘要:【目的 在互联网时代,图数据凭借着其丰富语义和结构信息,在众多的领域中发挥着独特的作用。同时,越来越多的公司选择使用“云服务”作为基础设施平台,个人敏感数据的保护问题愈发受到人们的关注。这为隐私保护的图计算带来了严峻的挑战。方法】本文针对图计算中至关重要的子图匹配问题,首次提出了基于安全多方计算的图查询保护策略,将隐私保护图查询问题转化为关系表的安全连接问题,并根据图数据的特性对安全连接子协议进行改
3、进。【结果】相比于之前的隐私保护图查询工作,本文协议不仅提供了更低的计算和通讯开销,并且具有更高的安全保障性和可信度。关键词:安全多方计算;云服务;隐私保护;图查询;安全连接Privacy-Preserving Graph Query Based on SecureTANG Shiyuan,YUANYeBeijing Institute of Technology,Beijing 100081,ChinaAbstract:Objective In the era of the Internet,graph data,with its rich semantics and structural
4、informa-tion,plays a unique role in numerous fields.At the same time,more and more companies arechoosing to use cloud services as their infrastructure platform,and the protection of personalsensitive data is increasingly attracting peoples attention.This poses severe challenges to priva-cy-preservin
5、g graph computing.Methods This paper focuses on the crucial subgraph match-ing problem in graph computing and proposes,for the first time,a privacy-preserving graphquery strategy based on secure multi-party computation.The privacy-preserving graph queryproblem is transformed into a secure join probl
6、em for relational tables,and the secure join sub-protocol is improved according to the characteristics of graph data.Results Compared withprevious works on privacy-preserving graph query,our protocol not only provides lower com-putation and communication overhead,but also has higher security and cre
7、dibility.Keywords:secure multi-party computation;cloud services;privacy preserving;graph query;secure join基金项目:国家自然科学基金(6 1932 0 0 4)*通信作者:袁野(E-mail:yuan-)98数据与计算发展前沿,2 0 2 3,5(5)汤世源等:基于安全多方计算的隐私保护图查询引言随着互联网和大数据的快速发展,传统的关系型数据库在处理海量数据时面临着不可避免的挑战,尤其是在处理复杂的图数据时,关系型数据库的效率和可扩展性无法满足需求。因此,图数据库应运而生,其凭借着丰富语义
8、和结构信息,在众多的领域中发挥着独特的作用,例如社交网络、金融2 、医疗3、物联网等。考虑到数据量的日益膨胀,越来越多的公司选择使用“云服务”作为其IT基础设施平台。使用云服务可以让用户避免昂贵的前期基础设施成本,并将重点放在使其业务与众不同的项目上,而不是放在基础设施上。当前有许多公共的图数据库系统同时支持云服务平台,如GraphLab5、Ne o 4j 0 等,其提供SaaS(软件即服务)风格的云服务。换而言之,他们允许用户将图数据上传到他们的云平台,并通过外包图数据提供基于云的计算服务。然而在互联网时代,除了注重成本上的收益,个人敏感数据的保护问题愈发受到人们的关注。将大量数据图存储在云
9、中以节省存储、提高计算,带来了另一个不可避免的挑战,即如何在不损害云中敏感信息的情况下处理用户的查询。本文章将以图计算的重要组成部分一一子图匹配(SubgraphMatching)算法8 为例,着重介绍隐私保护图查询的发展情况,列举并分析经典的隐私保护策略,并提出基于安全多方计算9的图查询保护协议。本文协议仅需要O(logn)轮通讯,且计算上的时间复杂度为O(nlogn),其中n为数据图的边数;在安全性上,允许查询者和数据持有者之间互不信任。本文第1节介绍隐私查询以及图数据隐私的相关概念;第2 节介绍相关技术的国内外研究现状;第3节提出基于安全多方计算的图查询保护协议;最后对全文进行总结,并提
10、出展望。1隐私查询与图数据隐私1.1系统模型提及隐私查询,首先要确定系统模型,即应用场景存在哪些角色,根据角色之间的信任关系,以此作为安全协议设计的基本标准。云服务是指由云端计算能力强大的服务器集群提供的云计算服务,如图1所示,在云服务的系统模型中,通常存在3种角色:数据持有者(Data Own-er)、客户端(Client)、云服务器(Cloud Server)。由于数据的规模通常非常大,数据持有者利用云服务器计算与存储能力的优势,将持有的数据图G保存在云服务器上,当有客户发送查询图Q作为查询请求时,由云服务器在数据图上进行查询,并将匹配结果R查询结果返回至客户端。ClientsqueryQ
11、Cloud ServersUploadGraph data GData Owners图1常见的图查询系统模型Fig.1Common graph query system model1.2图图数据隐私云服务器通常不受数据持有者和客户端的信任,数据持有者和客户端也可能存在互不信任的关系,这便对图数据隐私的保护提出了要求。图数据相比于传统的关系型数据,除了需要不泄露顶点与边上的文本信息之外,还需保证图中拓扑结构信息的安全性。在使用云服务进行图计算时,往往要考虑到以下两种敏感信息:(1)文本隐私。即顶点与边上存储的文本信息。无论是在简单的标签图,还是包含更多样化信息的属性图,顶点与边本身都包含了文本信
12、息,从特定的角度出发这些文本都可以被视为敏感信息。例如在社交网络中,使用属性图存储表示人际关系。每个顶点代表一个用户,边表示用户间result R99数据与计算发展前沿,2 0 2 35(5)汤世源等:基于安全多方计算的隐私保护图查询的关系,用户的基本信息由属性与属性值成键值对的形式保存。当使用云服务对人际关系网进行搜索时,用户的基本信息以及用户间的关系都应当作为敏感数据进行隐私保护处理。(2)结构隐私。即顶点与边之间的拓扑结构信息。这是图数据库特有的敏感数据,也是相比传统数据库隐私保护的一大挑战。可由拓扑结构泄露的信息有:在社交网络中,其图数据往往是成幂律分布,可以根据用户顶点的度判断一个用
13、户在社会上的影响力,当攻击者结合其他统计信息推测,可能导致出该用户的身份信息泄露。1.3敌手模型根据攻击者的行为,可以将敌手模型分为半诚实敌手(Semi-honest Adversary)和恶意敌手(M a l i c i o u s A d v e r s a r y)。在本文中,假设云服务器是半诚实的,即“诚实但好奇”的攻击者,这与大多数相关工作定义一致。云服务器“诚实”地遵循协议规则,但会“好奇”地推断和分析数据,以了解更多信息。初看半诚实敌手模型的安全性很弱,但实际上,构造出半诚实安全的协议并非易事,且构造可抵御更强大攻击者的协议通常是在半诚实安全协议的基础之上进行改进的。2国内外研究
14、现状为了保护图数据在查询过程中隐私免受攻击,学者们针对子图匹配问题,提出了在保护图数据隐私的前提下,安全进行子图匹配的算法。其中典型的方法包括:构造特征索引与k-自同构图(k-automorphism),接下来本文将对这两种典型方法进行简要的分析。2.1基于特征索引Cao等人10 最早提出并解决云服务中的隐私保护图查询问题。在先前的研究中,与隐私查询最相关的技术是可搜索加密,然而直接使用可搜索加密来处理语义丰富的图数据一定是不适合的。故Cao等人设计了一种加密查询机制,利用k近邻(k-Nearest Neighbor)技术12 ,在不侵犯隐私的情况下支持图语义的查询,是隐私保护图查询上一次大胆
15、的尝试。正如上一节所讲述的,Cao等10 考虑的系统模型包含了数据持有者、客户端、云服务器3种角色。其中,云服务器被视作为诚实但好奇的,数据持有者和客户端对云服务器并不信任。云服务器在系统中的作用是根据客户端的查询图Q,筛选出存在匹配结果的候选超图集,并发送给客户端。文中假设,客户端与数据持有者之间是相互信任的,即客户端可以在明文环境下与数据持有者进行图查询,而云服务器所返回的候选集可以大大减少客户端的工作量。具体而言,数据持有者将图数据集G中阈值大于o的频繁子图称为特征,并为每个特征构建加密的可搜索索引I;然后数据持有者将加密后的数据图集合G以及加密的索引I外包到云服务上。对于每一个查询图Q
16、,授权的客户端通过搜索控制机制,获取相应的陷门To,并将其发送到云服务器。云服务器根据用户的T。,通过索引I执行查询,并返回加密的候选超图集。最后,授权用户通过访问控制机制解密候选超图集,在明文状态下与数据持有者进行子图查询,来验证每一个候选图。在成本上,该方法客户端的存储和计算的开销很大。客户端需保存大量频繁子图的编码,并且实际上子图匹配的过程是在客户端上完成。在安全性上,虽然保证了云服务器上图数据集的隐私不被泄露,但要求客户端和数据持有者相互信任,客户端在明文下完成后续图查找工作。此外该方法主要针对图结构的保护,并未提及如何对图上文本信息进行保护。2.2基于k-自同构k-自同构技术最早由Z
17、ou等人13 提出,用于解决图发布问题。具体来说,给定图G,通过引人一些噪声边将G变换为k自同构图G,其中每个顶点至少具有(k1)个与之对称的顶点。这意味着顶点v和它的(k1)个对称顶点之间没有结构差异。因此,攻击者无法将v与其他(k-1)个对称顶点区分开来,k-自同构的策略可以防御任100数据与计算发展前沿,2 0 2 3,5(5)汤世源等:基于安全多方计算的隐私保护图查询何基于结构的攻击。Zou等人以这项技术作为基础,实现了隐私保护的图查询4。基于k-自同构的方法采用了与Cao相同的系统模型,将云服务器视为诚实但好奇的,客户端与数据持有者相互信任。但相比于基于特征索引的方法,数据持有者所拥
18、有的图数据结构为属性图G=(V,E,L,A),其中L代表顶点的标签,不同标签的顶点具有不同的属性集合(i)二A,属性采用键值对的结构存储。除了使用k-自同构对图结构进行保护之外,还会对图上文本信息(即属性值)使用k-匿名(k-anonymous)15)进行加密保护。数据持有者使用k-自同构与k-名技术将数据图转为外包图G后上传至云服务器。客户端采用k-匿名技术对查询图的属性值进行泛化,转化为外包查询图Q后向云服务器发起请求。在查询时,作者提出了一种两阶段的查询评估策略。在云中,首先评估G上的子图查询Q,以获得查询结果R(Q,G)。最终,客户端基于G过滤掉R(Q,G)中的假阳性,以找到正确结果R
19、(Q,G),即Q在原始图G上的子图匹配。作者在后续对G的大小,以及客户端过滤假阳性结果的效率进行了优化。基于k-自同构的思路在一些新的隐私保护图查询策略上仍然在使用。但在安全性上,其同样要求客户端与数据持有者是相互信任的关系,需利用原图G过滤假阳性结果;此外,在文本信息的保护上仅考虑对属性值的保护,而属性名和顶点标签是对外可见的,这会在一定程度上泄露顶点的信息。3安全多方的子图匹配协议安全多方计算(Secure Multi-PartyComputa-tion,MPC)通常代指一类协议,它允许多个参与方在不披露任何参与方私有输入的条件下实现联合计算。MPC的思想最早由Yaol9提出,如今已经成为
20、隐私保护应用系统的重要工具之一。据我们所知,其文章是第一个将安全多方计算技术运用到隐私保护的图查询上的。相比于之前的隐私保护图查询工作,基于安全多方计算的策略规避了传统加密技术在计算上的高额开销,通过使用秘密共享、不经意传输等更加高效的密码学原语,提供了更低计算和通讯开销。同时,安全多方计算带来了更加严格的安全定义,本文所提出的基于安全多方计算的图查询协议中,并不要求数据持有者与客户端之间互相信任,这将让更普遍客户端能从数据图中进行查询,但同时不泄露数据图整体的信息,更具实用价值。本节将提出一个基于安全多方计算的图查询协议,当输人的数据图边数为n时,协议仅需要O(logn)轮交互,和O(nlo
21、gn)计算和通讯的复杂度。根据MPC协议的可组合性,首先介绍具有关键功能的子协议,然后介绍如何使用这些协议实现安全的图查询。当出现功能性相同且效率更高的子协议时,直接地替换并不会对本协议造成任何影响,同时又提高了本协议的执行效率。3.1关键技术3.1.1通通用计算协议通用计算协议实现了功能函数FMPc,其可以安全的执行参与方约定的任何函数。本文所提协议将使用到Mohassel等人 提出的ABY通用协议。参与方将输入以秘密共享的形式发送到3个独立且诚实占多数的具有计算能力的机器上,这些机器通过对秘密共享形式的数据进行一系列的转化与计算,在不重建出原始数据的前提下,计算出任何参与方约定的函数,并返
22、回秘密共享的结果,由参与方自行重建出实际结果。秘密共享17 是隐私保护重要的加密原语,简单来说是将一个秘密值s拆分成n个秘密份额,参与计算的各方只持有其中的一份。在文中,统一用x表示x的秘密共享形式,x,代表秘密值x的第i个秘密份额。例如假设xi、x 2、x 3为均匀分布的随机数,满足x=xi+x2+x3,那么xi=xix2=X2、x ;=x 3是x的秘密共享。直观的看起来每一个份额与一串均匀分布的随机数不可区分,故各计算在仅持有一份秘密份额的情况下完成计算,不会获得秘密值的任何信息。3.1.2安全连接协议在本文中,连接指关系型数据上的自然连101数据与计算发展前沿,2 0 2 35(5)汤世
23、源等:基于安全多方计算的隐私保护图查询接,安全连接协议所实现的功能函数Fioin指输人两个秘密共享类型的数据表,构造出包含两个表自然连接的秘密共享表,过程中不会获得任何关于原数据表的信息。以文献18-19 为例,根据两表中作为连接条件的元素是否唯一可分为一对一(1-to-1)、一对多(1-to-multi)、多对多(multi-to-multi)3种类型的安全连接协议。其中1-to-1安全连接协议的相关研究最为广泛,大多文献将作为连接条件的元素与集合中的元素进行类比,根据集合元素的唯一性,巧妙的运用隐私集合求交(Private Set Intersection,PSI)协议2 0 。而一对多、
24、多对多协议的相关研究较少,主要采用安全的排序(Sort)与置换(Permutation)协议2 1 进行设计。两者皆以秘密共享数据作为输入与输出,使得协议具有很好的可组合性。当两张表的连接条件都不唯一时,即multi-to-multi连接,若每张表的元组数为n,一个朴素的思想是将两表中任意两个元组都进行比较,通过n次比较来构造连接。然而许多自然的计算连接的方法需要一个深度为O(n)的电路,哪怕其不需要进行n次比较,这对于n很大时是不切实际的,假定消息传递的延迟为相对较快的10 ms,当对两张元组数为n=1,000,000的表进行连接需要2.8 h。本文使用Badrinarayanan等人 9提
25、出的多对多安全连接协议,将任意两元素的比较操作转化为排序与复制,进而将通讯轮次降低到了O(logn),对于上述连接仅需要0.2 s。3.2协议描述根据ABY的思想,本文规定“云服务”是由3个独立且诚实占多数的云服务器提供。协议的大致流程为:客户端与数据持有者将需要上传的数据以秘密共享的形式发送,即将秘密份额分别发送给3个独立的云服务器;3个云服务器之间进行通讯与安全计算,在不重建出原始数据的前提下计算出秘密共享的结果。客户端接收3个云服务器秘密共享形式的结果,自行重建出结果。接下来对协议的具体流程进行详细阐述。3.2.1问题定义定义一个无向标签图G=(V,E,L),其中V是102顶点集合,每个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 安全 多方 计算 隐私 保护 查询
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。