最新要闻
- 环球报道:韩国载有216人客机飞行中出现异常:靠一台发动机平安降落
- 天天热文:特斯拉股价年内大跌60%!最大空头:明年可能会更惨
- 每日动态!还差14亿刀回本!《阿凡达2》全球票房破6亿美元 说中国影迷不感兴趣尚早
- TCL华星13.3英寸定制全隐私屏研发成功!全屏防窥、防窃听
- 今日看点:二次伤害猛于虎 事故后驾驶员留在现场:半小时后被撞身亡
- 全球信息:国产CPU力挺国产OS!x86兆芯加入deepin深度社区
- 焦点速讯:《炉石传说》国服停运倒计时!官方补偿来了:10个卡包你领吗?
- 车门都不给配 新款雪铁龙My ami Buggy官图发布:年满14就能开
- 全球热文:有了AMD RX7900、4090深受市场青睐:RTX 4080还一无是处?
- 比亚迪仰望来了!首发极具颠覆性技术
- 马斯克给全球车主发福利:每人可“白嫖”30天免费EAP试用服务
- 阵容十分豪华 2023最受期待的十大游戏来了:暗黑4位列第三
- 首发天玑8100:荣耀平板V8 Pro带来超级笔记 自动去广告
- 起点读书宣布百部经典作品限时免费:包括《诛仙》《红楼梦》等
- 世界热点!男子修车时发现4S店虚报维修定损金额 要求退一赔三胜诉
- 每日动态!2023春运车票24日开售 除夕车票要等到1月7日
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
短讯!安全多方计算(5):隐私集合求交方案汇总分析
学习&转载文章:安全多方计算(5):隐私集合求交方案汇总分析
前言
随着数字经济时代的到来,数据已成为一种基础性资源。然而,数据的泄漏、滥用或非法传播均会导致严重的安全问题。因此,对数据进行隐私保护是现实需要,也是法律要求。隐私集合求交(Private Set Intersection, PSI)作为解决数据隐私保护的方案之一,受到广泛关注和研究。
(资料图片)
隐私集合求交使得持有数据参与方通过计算得到集合的交集数据,而不泄露任何交集以外的数据信息,其功能如图1所示。作为安全多方计算中的一个重要分支,其不仅具有重要的理论意义,也具有广泛的应用场景。例如:隐私保护位置共享[1]、在线广告的有效转换率衡量以及基于人类基因组序列[2]的亲子鉴定、疾病预测和血统测试等。
图1 隐私集合求交功能示意图
PSI分类
隐私集合求交的研究主要聚焦在两个参与方,因此,本文主要针对两方隐私集合求交进行阐述。两方PSI可根据参与方的数据集大小分为三类,如图2所示。根据双方数据集大小差异可将其分为对称数据集和非对称数据集(非平衡),对于对称数据集,又可分为大数据集和小数据集。本文针对对称数据集及不同场景的需求,介绍与之对应的隐私集合求交方案。
图2 隐私集合求交分类示意图
- 小集合:百
- 大集合:百万
- 非对称:100亿
PSI方案介绍
基于DH的PSI方案
基于DH的PSI方案[3]流程如图3所示,该方案基于DH密钥交换的思路,实现两次可以交换加密顺序的加密操作,使得参与双方对于交集数据,得到完全相同的不可逆密文。
图3 基于DH的PSI方案流程示意图
基于DH的PSI方案主要分为以下3个步骤:
这里所谓说的“公钥加密”,公钥是:\((H(x)^a)^b\)
Alice选择随机数\(s\)作为私钥。对于每一个数据\(x\),Alice首先对其进行哈希操作,再基于其哈希值使用私钥对其加密,生成密文,并将此密文发送给Bob。
Bob选择随机数\(b\)作为私钥,对于每一个数据\(y\),Bob首先对其进行哈希操作,再基于其哈希值使用私钥对其加密,并将此密文发送给Alice。对于接收到Alice的密文,Bob使用私钥对其进行二次加密。
Alice对于接收到的密文,基于私钥对其进行二次加密
结论:若Alice和Bob拥有相同的数据,则两次加密得到的密文一致。
- 以上实际上就是基于DH实现的OPRF。
基于DH的PSI方案思想简单,易于实现,但也具有一定的局限性,例如:基于公钥加密实现PSI功能会产生较大的计算开销。因此,适用于数据量较小的场景。
- 基于公钥加密的PSI会产生较大的计算开销。
基于OT的PSI方案
预备知识
不经意传输(Oblivious Transfer, OT)[4]是安全多方计算最基础的协议之一,在之前的文章中已做了详细介绍安全多方计算(1):不经意传输协议。
本部分我们仅使用了2选1的不经意传输协议,其功能如图4所示。Alice有两条消息,Bob可以通过比特\(b\)获取消息,而无法获得的任何消息。Alice无法获得关于\(b\)的任何信息,即:Alice不知道Bob获取了哪条消息。
图4 不经意传输功能示意图
方案详解
在本部分,我们简述经典的基于OT的PSI方案,其流程如图5所示。该方案的核心思想为执行多次二选一的不经意传输协议,并结合伪随机函数,使得参与双方对于交集数据得到相同的随机数。
图5 基于OT的PSI方案流程示意图
基于OT的PSI方案主要分为以下4个步骤:
Alice生成随机数\(w\);Bob生成随机数\(r_0\),并基于与本方数据的伪随机函数值生成\(r_1\).
Alice与Bob基于\(w\)和\(r_0,r_1\)执行次二选一的不经意传输,其中\(\lambda\)为比特长度。
Alice基于多次不经意传输结果生成\(q\),Bob计算\(r_0\)的哈希值。
Alice计算本方数据的随机值。
结论:若Alice和Bob拥有相同的数据,则两份数据得到相同的随机值,即\(\boldsymbol{x}_{\boldsymbol{j}}=\boldsymbol{y}_{\boldsymbol{i}} \leftrightarrow H\left(q \oplus\left(F\left(x_{j}\right) \cdot w\right)\right)=H\left(r_{0}\right)\)。
- 我们以两种极端情况论述方案的正确性:
图6 基于OT的PSI方案正确性验证
- 普通情况,假设\(w=010\),则\(q=r_0[1]||r_1[2]||r_0[3]=r_0[1]||r_0[2]\oplus F(y_i)[2]||r_0[3]=r_0\oplus F(y_i)[2]\),即\(q \oplus\left(F\left(x_{j}\right) \cdot w\right.)=r_0\oplus F(y_i)[2]\oplus F(x_j)[2]=r_0\)
- 以上推到不完全正确,欢迎交流~
基于OT的PSI方案规避了大量的公钥加密,使用效率更高的对称加密完成大部分操作,但通信开销较大,适用于数据量较大的场景。
经典的基于OT的PSI方案仍具有很大的计算开销及通信开销,但是OT的扩展协议为构建高效的PSI方案提供了理论支撑。在3.3中,我们以OPRF为例,介绍基于OT扩展协议的高效PSI方案。
基于OPRF的PSI方案
预备知识
不经意伪随机函数(Oblivious Pseudorandom Function, OPRF)[5]属于不经意传输的扩展协议,它允许执行少量的基础OT,通过轻量级的对称加密来实现大量的OT实例,OPRF的功能如图7所示。
对OPRF的定义是不对的,OPRF可以有多种方式实现,其中OT/OTE只是其中之一。
Alice生成伪随机函数的密钥\(k\),可基于\(k\)获得本方数据\(x\)的伪随机函数值\(F_k(x)\)。Bob以本方数据\(y\)作为OPRF协议的输入,协议执行完成后,Bob可得到\(y\)的伪随机函数值\(F_k(y)\),但无法获得关于\(k\)的任何信息。
图7 不经意伪随机函数功能示意图
方案详解
在本部分,我们简述基于OPRF的PSI方案[6],其总体流程如图8所示。为便于阐述,我们将Alice作为数据拥有者,记为DO(Data Owner);Bob作为请求者,记为Re(Requester)。
图8 基于OPRF的PSI方案总体流程示意图
我们将基于OPRF的PSI方案分为以下步骤进行阐述:
- 请求者(Bob)将数据映射:映射过程如图9所示。首先,请求者随机生成\(m\)行\(w\)列的二进制矩阵\(A\in (0,1)\),其中\(m\)为数据集大小。对于每个数据,请求者计算其伪随机函数值,并将伪随机函数值与二进制矩阵A相结合,获取二进制比特串。同时,将对应位置标记为数据位(如图9中蓝色部分)。然后基于二进制比特串执行哈希操作,得到数据映射值【留着待比较】。
- 将\(v_i\)映射到\(A\)中,以下面为例:\(v_1[1]=3\),则选择\(A_1[v_1[1]]=A[v_1[1],0]=0\)
图9 请求者数据映射流程图
- 请求者(Bob)生成矩阵\(B\):请求者生成一个\(m\)行\(w\)列的全1矩阵\(D\in (1)\),将第1步标记的数据位部分置为0【这里是两个数据\(x_1,x_2\)】。然后将矩阵\(A\)与矩阵\(D\)执行异或操作得到矩阵\(B\)。因此,矩阵\(A、B\)具有如下特性:矩阵\(A、B\)对于(标记的)数据位的比特值相同;对于(没有标记的)非数据位的比特值相反。这一步主要是为了二选一的不经意传输做准备。
图10 矩阵B生成示意图
- 数据拥有者(Alice)获得矩阵\(C\):这一步的核心思想是请求者与数据拥有者执行\(w\)次不经意传输,其执行过程如图11所示。通过1、2步,请求者已获得\(A、B\)矩阵;在第3步,数据拥有者生成长度为\(w\)的二进制比特串【如何生成?】。在每一次OT执行中,请求者以\(A、B\)矩阵的第\(i\)列作为输入;数据拥有者以比特串\(s\)的第\(i\)位{\(s[i]\)}作为输入,若\(s[i]=0\),则数据拥有者得到\(A\)的列;若\(s[i]=1\),则数据拥有者得到\(B\)的列,最终数据拥有者得到矩阵\(C\)。矩阵\(A、B、C\)具有如下特性:此三个矩阵对于(标记的)数据位的比特值相同;而通过不经意传输,矩阵\(C\)的非数据位已被置乱。
图11 不经意传输执行示意图
- 数据拥有者(Alice)将数据映射,映射过程如图12所示。对于每个数据,这一步与第1步的流程类似,其目的是为了对于参与双方的交集数据生成完全相同的随机映射值。首先数据拥有者计算其本方数据的伪随机函数值,并将伪随机函数值与第3步得到的二进制矩阵C相结合,获取二进制比特串\(C_1[v_i[1]]||...||C_w[v_i[1]]\),然后基于二进制比特串执行哈希操作,得到数据映射值【发送过去比较】。
图12 数据拥有者数据映射流程图
- 数据拥有者(Alice)将其本方所有数据映射值发给请求者,请求者对比两方数据映射值确定交集数据,而其不会获得数据拥有者的任何非交集数据信息。至此协议完成。
总结
本文介绍了基于两方对称数据集的三种隐私集合求交方案,其中基于DH的PSI方案适用于小数据的场景;基于OT的PSI方案适用于大数据集的场景,但其依然有较大的通信开销,因此,介绍了基于OPRF的PSI方案,其在计算开销和通信开销方面均具有良好的表现。
方案 | 效率 | 适合数据集 |
---|---|---|
基于DH的PSI | 计算开销大 | 小数据集 |
基于OT的PSI | 通信开销大 | 大数据集 |
基于OPRF的PSI | 计算和通信均好 |
随着隐私计算技术的发展,多方及外包隐私集合求交方案也在被逐渐关注与研究,我们在后续文章中进行介绍。
参考文献
[1] NARAYANAN A, THIAGARAJAN N, LAKHANI M, et al. Location Privacy via Private Proximity Testing[C]//Proceedings of the Network and Distributed System Security Symposium, NDSS 2011, San Diego, California, USA, 6th February - 9th February 2011. 2011.
[2] SHAFIN K, PESOUT T, LORIG-ROACH R, et al. Nanopore sequencing and the Shasta toolkitenable efficient de novo assembly of eleven human genomes[J]. Nature Biotechnology, 2020(Suppl.2).
[3] Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]//1986 IEEE Symposium on Security and Privacy. IEEE, 1986: 134-134.
[4] RABIN M O. How to Exchange Secrets by Oblivious Transfer[J]. Technical Memo TR-81, 1981.
[5] FREEDMAN M J, ISHAI Y, PINKAS B, et al. Keyword Search and Oblivious PseudorandomFunctions[C]//KILIAN J. Theory of Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg,2005: 303-324.
[6]CHASE M, MIAO P. Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF[C]//MICCIANCIO D, RISTENPART T. Advances in Cryptology – CRYPTO 2020. Cham: Springer International Publishing, 2020: 34-63.
-
天天观速讯丨论文解读()《Detect Rumors in Microblog Posts for Low-Resource Domains via Adver
论文信息论文标题:DetectRumorsinMicroblogPostsforLow-ResourceDomainsviaAdversarialContrastiveLear
来源: 短讯!安全多方计算(5):隐私集合求交方案汇总分析
天天观速讯丨论文解读()《Detect Rumors in Microblog Posts for Low-Resource Domains via Adver
每日讯息!GitHub实用开源项目
环球报道:韩国载有216人客机飞行中出现异常:靠一台发动机平安降落
天天热文:特斯拉股价年内大跌60%!最大空头:明年可能会更惨
每日动态!还差14亿刀回本!《阿凡达2》全球票房破6亿美元 说中国影迷不感兴趣尚早
TCL华星13.3英寸定制全隐私屏研发成功!全屏防窥、防窃听
今日看点:二次伤害猛于虎 事故后驾驶员留在现场:半小时后被撞身亡
世界热议:上干货 | 园区智慧物联管理解决方案
Shell脚本3
全球信息:国产CPU力挺国产OS!x86兆芯加入deepin深度社区
焦点速讯:《炉石传说》国服停运倒计时!官方补偿来了:10个卡包你领吗?
车门都不给配 新款雪铁龙My ami Buggy官图发布:年满14就能开
全球热文:有了AMD RX7900、4090深受市场青睐:RTX 4080还一无是处?
比亚迪仰望来了!首发极具颠覆性技术
微头条丨AcWing341. 洛谷P1073, NOIP2009 最优贸易
百事通!面向对象与面向过程
全球速递!Flex布局总结
马斯克给全球车主发福利:每人可“白嫖”30天免费EAP试用服务
阵容十分豪华 2023最受期待的十大游戏来了:暗黑4位列第三
首发天玑8100:荣耀平板V8 Pro带来超级笔记 自动去广告
起点读书宣布百部经典作品限时免费:包括《诛仙》《红楼梦》等
世界热点!男子修车时发现4S店虚报维修定损金额 要求退一赔三胜诉
Codeforces 1630 E Expected Components 题解 (组合数学)
头条:Java基础项目:超市管理项目
每日动态!2023春运车票24日开售 除夕车票要等到1月7日
《妮姬》首月收入突破6.9亿!腾讯海外收入占比提升达12.5%
今日热门!超越电竞机!Redmi K60要榨干第二代骁龙8:画质、帧率、亮度三不降
每日精选:效果堪比镀铬 2.2万元的特斯拉Model Y新配色值不值?
环球观察:高可用 Canal集群 实操( 秒懂 + 史上最全)
微头条丨认证管理(锐捷业软篇)
Intel拆分GPU部门 一把手重回技术岗 累计亏损超20亿美金
天天通讯!iPhone 14 Pro爆出“闪线门” :屏幕出现诡异的绿色和黄色细横线
全球热点评!当ChatGPT遇上弱智吧:全程爆笑
夫妻的世界翻拍哪部电视剧?夫妻的世界最后结局是什么意思?
滕王阁为什么叫阁不叫楼?滕王阁为什么是三大名楼之首?
情非情砸车是第几集?情非情盖总和保姆的结局是什么?
小昭去波斯是哪一集?小昭去波斯后她母亲去哪儿了?
男人是大猪蹄子是什么意思?男人是大猪蹄子女人是什么?
排序算法模板(更新中)
当前速读:机器学习——果蔬分类
每日消息!性能超越电竞手机!Redmi K60 Pro综合跑分达135万
信息:千万别强忍 20岁小伙憋气压抑咳嗽导致昏厥
特斯拉今年股价累计暴跌超60%!马斯克透露大跌原因
收购动视暴雪遇阻 微软哭弱:根本打不过索尼、任天堂
到手9袋!良品铺子坚果礼盒1440 仅44元包邮
每日讯息!教你用JavaScript实现背景图像滑动
户外运动有哪些项目?户外运动品牌排行榜
什么鱼营养价值最高?什么鱼只会逆流而上?
金木水火土命怎么算出来的?金木水火土哪个腿长?
玉面小飞龙是什么意思?玉面小飞龙出自哪里?
Redmi K60系列上架:三颗口碑最好的芯片都拿到了 12月27日发
每日聚焦:最快闪充旗舰!真我GT Neo5充电头曝光:支持240W充电
环球热讯:紫米裁员80%并入小米?官方澄清:ZMI品牌将继续存在
全球新资讯:9.99万元遭疯抢 五菱宏光MINI EV敞篷版下线:能跑280km
苯胺皮是什么皮?苯胺皮和纳帕皮有什么区别?
世界新动态:CloudCanal实战-五分钟搞定Oracle到StarRocks数据迁移与同步
(一)elasticsearch 编译和启动
【速看料】马斯克辞任CEO,产品经理如何用项目协作软件武装自己?
焦点速讯:字节鏖战美团的关键一役
重点聚焦!糗事百科宣布将关闭服务 自侃“享年17岁”
全球观点:神似苹果AirPower!特斯拉推出无线充电板:最高功率15W
手慢无 民族品牌两面针牙膏大促:四支到手20元还送牙刷
又一新能源品牌官宣涨价:最少涨5千 今年买车还剩最后一周“窗口期”
全球速看:盘点适合《战神》奎爷的演员:道恩·强森、杰森·莫玛等
新型复兴号CR200J首次亮相:Wi-Fi全覆盖 充电插口增加
环球微动态丨比亚迪DM-i再外放 东风小康风光蓝电E5官图发布:综合续航1150km
霍乱疫情卷土重来:已致马拉维国410人死亡
环球今热点:随身咖啡馆 精神X小时:Nevercoffee咖啡1.99元(京东5元)
天天微头条丨什么是 HTML5?
每日消息!Ubuntu:Docker 容器操作
天天关注:苹果降低中国工厂依赖:真要搬走?iPhone 14制造难度降低
全球聚焦:不装了!日本万亿重新发展核能:新一代核反应堆准备中
【热闻】冬至湖南浏阳全城燃放烟花 满城烟花一河诗画:网友羡慕哭
焦点简讯:顺丰又上热搜!买Chanel耳钉顺丰运掉五颗珍珠
焦点热门:修复RX 7900显卡功耗异常 AMD新驱动实测:有用 但没什么大用
天天简讯:比iPhone 14 Pro Max更轻更便宜 OPPO Find N2首销:7999元
4插槽怪兽 华硕、猫头鹰合作打造最安静、最冷静的RTX 4090/4080显卡
动态:5.2万亿财富没了 特斯拉股东喊话马斯克:别只顾着推特了
世界微速讯:小岛秀夫:只有Xbox懂我
天天通讯!本田思域Type R各国/地区售价曝光 在日本才卖20多万?
每日短讯:负债585.68亿:国美获黄光裕公司三笔贷款累计5亿港元
全球快看点丨新能源车国补退场倒计时!车企打响价格战:现金立减、保险补贴
时隔半年 终于不寂寞!讯景发布全球第二款RX 6700
中国哪里的羊肉最好吃?这5个地方 你最爱谁?
后壳质感堪比玉石!vivo S16 Pro图赏
微软重构资源管理器进程:Windows 11运行速度大提升
支付宝接入技术
Python requests库指定IP请求,并使用HTTPS证书验证
世界今热点:MAUI新生4.5-字体图像集成Font&Image
精彩看点:Codeforces 1654 G Snowy Mountain 题解 (重心分治)
美国遭史上最严重禽流感疫情:鸡蛋价格创纪录 真吃不起节奏
环球速看:FreeSWITCH学习笔记:Lua脚本
每日短讯:剪映上线团队剪辑“神技”:异地多端一起剪视频成为可能
3299元起 vivo S16 Pro手机发布:首发双面柔光人像拍摄
环球信息:童年的味道 大白兔奶糖促销:1斤20元到手
环球聚焦:自拍绝了!vivo发布新机S16e:2099元起、行业首创“玉质玻璃”工艺
软链接和硬链接
世界热消息:渗透实录-02
雷军宣布小米人事调整:总裁王翔退休 卢伟冰晋升