最新要闻
- 全球快资讯:基于海拉克斯打造 丰田推出首款纯电皮卡原型车 网友:丑到我眼睛了
- 天天快资讯丨卡神离开Meta 批老东家效率低下:GPU利用率5%简直是侮辱
- 全球热点评!小米MIX Fold 2新配色下周首销:5.4mm厚度已是行业极限 8999元
- 今热点:同价位无敌手!小米万兆路由器更新
- AMD、NVIDIA齐发新品 显卡厂商的好日子来了:加速去库存
- 世界快报:男子1199元买长江存储2TB SSD吐槽是翻新 手指划痕:网友看完笑死
- 世界快消息!用户真实评价小米13:太惊艳了 这就是小米13带给我的感觉
- 精彩看点:北欧品质 口感清爽:OATLY燕麦奶4.1元/斤新低(商超29.8元)
- 【天天新视野】男子称买到过期3月沐浴露获赔5元:看不起谁呢
- 全球热资讯!BBA的禁脔 垂涎者不止蔚来
- 环球热点评!冬天空调取暖不热 可能是这些问题
- 环球观速讯丨小米13成了!线下门店卖断货 供不应求
- 世界速看:挑战行业多项不可能 一加11即将发布:最强性能旗舰
- 令人气愤!女子曝无良汽修店为赚钱高速路上撒钉子专扎车胎
- 天天视讯!刘作虎:OPPO一加正式开启双品牌战略 100亿投资扶植一加
- 环球观速讯丨义乌开始生产阿根廷夺冠球衣 还是三颗星 阿根廷辟谣:假的 侵权
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
【世界时快讯】安全多方计算:(2)隐私信息检索方案汇总分析
学习&转载文章:安全多方计算:(2)隐私信息检索方案汇总分析
前言
多头贷问题是网络小额贷款平台放款时所要考虑的一个重要问题。假设银行A有一潜在贷款客户小张,银行A为了足够多的了解小张的信用情况,希望向其他多家银行查询小张贷款情况或信用记录。但因为害怕其他银行抢走该客户,所以银行A不希望泄露自己在查询小张这一事实。是否可以通过技术手段解决银行A的诉求?答案是肯定的,即图1漫画中的“隐私信息检索技术”——一种不泄露查询条件和查询结果的加密技术。
图1 隐私信息检索技术应用示例漫画
(资料图片仅供参考)
隐私信息检索(Private InformationRetrieval – PIR,也叫匿踪查询)是安全多方计算中很实用的一项技术,用来保护用户的查询隐私。其目的是保证用户向服务器(数据源方)提交查询请求时,在用户查询信息不被泄漏的条件下完成查询[1]。即整个查询过程中服务器不知道用户具体查询信息及查询出的数据项。
一句话总结就是:不泄漏查询条件和查询结果
为什么可搜索加密技术无法替代隐私信息检索技术
通过前面对PIR技术的描述,可知PIR的目的是保护用户查询隐私。提到“保护用户查询隐私”,会有人想到可搜索加密技术,但可搜索加密技术并不能替代PIR技术。
先来简单了解可搜索加密技术。
顾名思义,可搜索加密就是在加密的情况下实现搜索功能,常用于云计算当中。可搜索加密应用示例如图2所示,能够实现将用户的数据进行特殊的加密后上传到云服务器上, 并且可以实现根据关键字进行检索的功能。(更详细内容可阅读本公众号文章:防止云端数据与查询行为泄露—可搜索加密)
图2 可搜索加密应用示例
可搜索加密实现密文检索时,过程示例如图3所示。可简单描述为:检索用户提交密文关键字(keyword3),云服务器将密文关键字与密文数据库比对,比对成功后则将对应的密文数据(数据3)返回给检索用户,最终检索用户对拿到的密文数据进行解密。
图3 可搜索加密密文检索示例
整个过程中云服务器不知道检索关键字(keyword3)和检索结果(数据3)对应的原始明文是什么。但是,数据拥有者(不一定是云服务器)监听到检索结果的话,可以直接解密并得到对应的明文。即可搜索加密技术仅能阻止云服务器获得用户查询隐私,不能阻止数据拥有者获得用户查询隐私(这很正常,云计算环境下,云服务器中一段密文数据的拥有者和检索者,可能是同一用户)。
- 总结一下:可搜索加密仅能保护查询条件,不能保护查询结果
3类场景隐私信息检索方案
为了加强保护用户查询隐私,使得查询条件和查询结果仅查询用户可知,安全多方计算中的PIR技术应运而生。目前常见的PIR方案实现有3类,分别是基于不经意传输(Oblivious Transfer,OT)的PIR实现、基于同态加密的PIR实现和keyword PIR实现。
其中基于不经意传输的PIR和基于同态加密的PIR需要检索用户提前知道被检索数据在服务端数据库中索引号。
3类方案的实现过程介绍如下。
基于不经意传输的PIR实现
基于不经意传输的PIR实现过程如图4所示(不经意传输协议此处不在赘述,更多内容可阅读本公众号文章:安全多方计算(1):不经意传输协议),主要利用的是n选1的OT协议。
图4 基于不经意传输的PIR实现过程
基于OT的PIR实现过程有5个重要步骤:
- 服务端有\(n\)条数据,则产生\(n\)个RSA公私钥对,并将\(n\)个私钥保留,\(n\)个公钥发送给用户端。
- 用户随机产生一个大整数key(key为第5步中的解密密钥),已知用户要检索第\(t\)条数据,则用户用收到的第\(t\)个RSA公钥加密大整数key,将加密结果\(s\)发送给服务端。
- 服务端用保留的\(n\)个RSA私钥,依次尝试解密\(s\),获得\(n\)个解密结果,依次为\((key1,key2,…,keyt,…,keyn)\)。
- 服务端利用对称加密算法(此处为AES算法),利用\((key1,...,keyn)\),加密对应的消息\((m1,...,mn)\),将产生的密文消息\((M1,...,Mn)\)发送给用户。
- 用户利用第2步中的key,对第\(t\)条密文\(M_t\)进行对称解密「即检索用户需要提前知道检索索引」,则得到想要检索的第\(t\)条原始明文消息\(m_t\)。
代码实现
基于同态加密的PIR实现
基于同态加密的PIR实现过程如图5所示,此处采用paillier加法半同态加密算法[2],paillier同态加密算法计算过程参见文献2,此处不赘述,但强调3个paillier算法特点:
(1)可以实现两个密文加法计算【c+c】;
(2)可以实现一个密文与一个明文相乘【c*m】;
(3)由于加密时用到随机数,所以相同的明文、相同的密钥,可以产生很多个不同的密文,这些不同的密文解密后都能得到相同的原始明文。
图5 基于同态加密的PIR实现过程
基于paillier同态加密的PIR实现过程有4个重要步骤:
- 用户端产生同态加密公钥\(pk\)和私钥\(sk\)。
- 已知服务端有\(n\)条数据,用户要检索第\(t\)条数据,则产生一个\(n\)维密文向量\(vector=(v1,…,vn)\),其中第\(t\)项是公钥\(pk\)加密数字1后的密文「即检索用户需要提前知道检索索引」,其他项是公钥\(pk\)加密数字0后的密文。将\(vector\)和公钥\(pk\)发送给服务端,paillier算法第3个特点保证了\(vector\)中的\(n\)条密文都不重复,保证服务端无法猜出哪一条是数字1的密文。
- 服务端将\(vector\)和\(n\)条明文数据集做向量内积运算,得到密文结果\(en\_result\),将\(en\_result\)发送给用户端。同态加密的密文计算结果解密后与明文计算结果相等,相当于\(en\_result=E(m1*0 + … + mt-1*0 + mt*1 + mt+1*0+ … + mn*0, pk) = E(mt, pk)\)。
- 用户端利用私钥\(sk\)对\(en\_result\)进行解密,得到想要检索的第\(t\)条原始明文消息\(mt\)。
代码实现
keyword PIR实现
实际上,在大多数的查询场景中,查询方往往不知道自己要查询的数据的索引号【即要检索的是第几个(索引)】,而大多根据关键词进行查询,此类方案又称keyword PIR,可以利用paillier同态加密和拉格朗日插值多项式实现(拉格朗日插值多项式细节可阅读本公众号文章:秘密共享—隐私计算和区块链共识中的榫卯),具体实现过程如图6所示。
图6 keyword PIR实现过程
keyword PIR实现过程有5个重要步骤:
- 服务端有明文数据集【关键词,数据】\(((x1,m1),…,(xn,mn))\),对此明文数据集进行拉格朗日多项式插值,插值结果即为最高次幂为\(n-1\)的多项式\(g(x)\);对于图6中的多项式\(f(x)\),\(f(x) = (x-x1)*(x-x2)*…*(x-xn)\),展开后即为图6中的\(f(x)\)。数据集中任意一个点(\(xi,mi)\),满足\(f(xi)=0,g(xi)=mi\)。
- 用户生成paillier同态加密公钥\(pk\)和私钥\(sk\)。
- 对于待查关键字\(xt\),用户利用\(pk\)分别加密\(xt\)的1次方到\(xt\)的\(n\)次方,组成密文向量\(vector\),发送给服务端。
- 服务端利用密文向量\(vector\),和\(f(x)、g(x)\)的系数,分别计算同态密文\(E(f(xt))、E(g(xt))\),将计算结果发送给用户。
- 用户利用私钥\(sk\)对两条密文进行解密,如果\(f(xt)=0\),则\(g(xt)\)即为检索结果;否则检索结果为空。
代码实现
方案验证及总结分析
前文对3类PIR方案实现方法做了描述,此处对3类方法做一个全面的比对分析,方便读者对3类方案有一个更直观的理解。
本文所提PIR方案理论分析
表1所示的表格,分别从依赖技术、通信开销、计算开销等方面对3类PIR方案特点做了总结。
表1 3类PIR方案特点总结
依赖技术 | 通信量与数据集(n条)关系 | 需要提前知道被检索数据索引号 | 计算开销与数据集(n条)关系 | |
---|---|---|---|---|
基于OT的PIR | 公钥密码,对称密码 | n个RSA公钥n条AES密文 | 是 | n次公钥解密n次对称加密 |
基于同态加密PIR | 同态加密 | n+1条同态密文 | 是 | 3n次同态加密 |
Keyword-PIR | 多项式插值;同态加密 | n+2条同态密文 | 否 | 5n次同态加密2次多项式构造 |
- 在计算开销上,由于同态加密计算开销大于RSA计算开销,所以基于OT的PIR方案计算开销有优势;
- 通信开销上,如果服务端每条明文数据都较长,如数千字节,则基于同态加密PIR通信开销较小。
代码实例验证
本环节,我们用python代码分别实现了基于OT的PIR和基于同态加密的PIR,让读者对PIR性能有更清晰的了解。我们模拟服务端有一个漏洞库,共有2245条数据(数据为绿盟真实漏洞库数据,原始数据数十万条,此处仅选取一部分用于实验),用户输入“软件名称+具体版本号”可查询对应的漏洞信息,查询过程中不会泄漏检索条件和检索结果。此部分仅展示用户获知检索项在服务端中的索引号后(索引号如何获取非本文重点,此处略过),分别模拟利用基于OT的PIR和基于同态加密的PIR实现漏洞信息检索。
图7 基于OT的PIR代码实验结果
图7为基于OT的PIR代码实现,网络为内部局域网,服务端为低配Ubuntu虚拟机,模拟结果总耗时3.3秒,通信开销RSA公钥传输消耗约0.68MB,全量AES密文传输消耗约5.6MB。
图8 基于paillier同态加密的代码实验结果
图8为基于paillier同态加密的PIR代码实现,相同配置下,计算开销耗时117秒,通信开销密文查询向量消耗约1.3MB网络开销,检索结果传输消耗约0.14MB。可以明显比对出前两类PIR方案在计算开销和网络开销上的差异。
总结
本文介绍了安全多方计算中很实用的一类方案——隐私信息检索方案,此类方案可在保护用户隐私的前提下,实现多方数据安全查询。另外,分别介绍了3种不同的实现方法原理,并对其进行理论对比分析,且对其中的两类方法做了代码实现。通过理论分析和实验对比,能够让读者对隐私信息检索有一个更直观的认识。
参考文献
[1]https://blog.csdn.net/hellompc/article/details/103784360
[2]Paillier P . Public-key cryptosystemsbased on composite degree residuosity classes[J]. Advances in CryptologyLeurocrypt, 2004.
- 程序实现:
- 拉格朗日插值法
- OT代码
- 基于RSA的
- 基于DH的
- PIR
- 基于OT的
- 基于Paillier的
- 带关键词的PIR
【世界时快讯】安全多方计算:(2)隐私信息检索方案汇总分析
全球快资讯:基于海拉克斯打造 丰田推出首款纯电皮卡原型车 网友:丑到我眼睛了
天天快资讯丨卡神离开Meta 批老东家效率低下:GPU利用率5%简直是侮辱
全球热点评!小米MIX Fold 2新配色下周首销:5.4mm厚度已是行业极限 8999元
今热点:同价位无敌手!小米万兆路由器更新
全球观热点:第八天 循环的花里胡哨的用法
重学c#系列——linq(4) [三十]
【速看料】400行的象棋程序
AMD、NVIDIA齐发新品 显卡厂商的好日子来了:加速去库存
世界快报:男子1199元买长江存储2TB SSD吐槽是翻新 手指划痕:网友看完笑死
世界快消息!用户真实评价小米13:太惊艳了 这就是小米13带给我的感觉
精彩看点:北欧品质 口感清爽:OATLY燕麦奶4.1元/斤新低(商超29.8元)
【天天新视野】男子称买到过期3月沐浴露获赔5元:看不起谁呢
焦点信息:java基础面试题
【报资讯】Docker的资源控制管理
全球热资讯!BBA的禁脔 垂涎者不止蔚来
当前通讯!Docker网络模式
环球热点评!冬天空调取暖不热 可能是这些问题
环球观速讯丨小米13成了!线下门店卖断货 供不应求
热点!web项目的开发---第二天
世界今头条!SpringCloud-Ribbon学习笔记
世界速看:挑战行业多项不可能 一加11即将发布:最强性能旗舰
世界动态:python语法笔记
令人气愤!女子曝无良汽修店为赚钱高速路上撒钉子专扎车胎
天天视讯!刘作虎:OPPO一加正式开启双品牌战略 100亿投资扶植一加
环球观速讯丨义乌开始生产阿根廷夺冠球衣 还是三颗星 阿根廷辟谣:假的 侵权
世界快播:“顶级大众” 宾利Batur公布工艺细节:210克黄金3D打印
老人手指被卡:消防员用开塞露救了差点被剪的蓝宝石戒指
全球快资讯:一文了解 Dubbo 的代码架构
今日报丨关于整数二分的详解
滚动:预编译#error的使用
全球要闻:YoloV7 标签匹配机 loss 计算详解
安全多方计算(1):不经意传输协议
每日快讯!元旦假期首日火车票今开抢!迎出行小高峰:五大热门目的地出炉
观天下!Find N2系列发布背后:OPPO再次展示对产品精益求精态度
天天要闻:全国冻哭预警地图来了:周末20余省份或被冻哭 冷到破纪录
热议:售价超300万!乔布斯亲手编号Apple-1电脑落锤成交:46年后 开机画面眼前一亮
世界最大独立圆柱体水族馆爆裂:1500多条鱼全军覆没
世界杯决战前夕 法国又有两大主力倒下!5人感染神秘流感
【环球热闻】被加价千元:AMD喊话正加大RX 7900系生产!NV 4080笑而不语
世界简讯:VUE数据双向绑定
第一百一十四篇: JS数组Array(三)数组常用方法
世界上最大的鱼缸今日突然破裂:100万升水泄露 1500条鱼死亡
放假3天不调休!2023年元旦假期首日火车票开售 除夕票这一天就能买
天天报道:学谁不好学特斯拉!几十万的宝马车 容不下一个收音机
观天下!骗子诈骗1250万 买彩票中1450万:已退还给39名聋哑人
全球热讯:XSX性能比PS5强 但为何游戏性能总是输?
天天速看:Python函数/动态参数/关键字参数
天天热点!女子发烧敷20分钟面膜揭下变3D立体面具 医生提醒:影响退热 当心面瘫
方便面消费第一大国是我们:超6成人每周吃三次
世界速读:注解在Android中的使用场景
热推荐:锂金属电池爱长枝晶?韩国科学家找到破解之法
【当前独家】确认了!《阿凡达2:水之道》没有片尾彩蛋
天天观速讯丨1152分区+4K 144Hz 联合创新32寸miniLED显示器首发5399元
终于修好了!Win11新补丁解决22H2大文件复制缓慢Bug
首款第二代骁龙8游戏旗舰!红魔8 Pro来了
今日最新!王思聪投资百万成立新公司 经营范围包括动漫游戏开发
全球最资讯丨全自动门锁比半自动更人性化!但半自动更受青睐 真相终于揭开
世界简讯:Hessian2序列化支持这一点,让重构dubbo接口更容易了
【热闻】-真正的国产亲民MPV 新款传祺M6 PRO上市:11.98万起
看点-旗下新作首月收入超4.8亿!腾讯成为《妮姬》开发商Shift Up第二大股东
女子高烧39.8度喊妈 妈妈以为鸭子叫没搭理 网友:怎么又变异了
观察-《三体》动画明天开播第3集 官方公布史强、古筝行动档案
【天天聚看点】微信小程序报错“getLocation:fail the api need to be declared in the requiredPriva
【全球快播报】记录--三分钟打造自己专属的uni-app工具箱
视点!小米万兆路由器用上企业级处理器!卢伟冰:降维打击
【天天报资讯】LCD面板价格连连下跌!LG P7 LCD工厂停产
环球关注:中国高速看山东!山东高速施工用上北斗卫星:精度达到毫米级
世界要闻:三大板卡品牌之一的微星缺席RX 7900首发 原因揭晓:直接非公版
世界快消息!女生手捏温度计度数直线飙到38度!腋下一测39.5度
天天日报丨项目经理的核心价值:以目标为导向做正确的事
环球热点评!Vue3项目-生成Cron表达式组件
世界今亮点!MIUI 14终于再次成为最好用的操作系统
ChatGPT已经牛到取代谷歌了?测试结果来了
男子每天点赞上万次被处罚 当庭演示一分钟才点赞91个
【当前独家】“智轨列车”亮相咸阳:可识别虚拟轨道 载客达300人
全球新动态:研究揭示马桶不盖盖后果多严重:致病菌满屋乱飞
全球滚动:Java 反射概念的引入
天天热议:小米13太火爆了 博主准点抢购结果秒没:最后等了20分钟捡漏 成功上车
【天天速看料】“火流星”掉落 专家判断陨石来自46亿年前:比地球上所有石头都古老
当前速看:《阿凡达2》成2022进口片首日票房冠军!时隔69天单日再破亿 豆瓣8.4分
价格能顶半套正版Win11 老牌压缩软件WinZip 27发布 你会买吗?
快播:44岁的泰国长公主因心脏问题失去知觉:紧急送医
渗透实录-01
要闻:Nacos 2.2 正式发布,这次更新太炸了!
世界关注:Kerberos身份验证在ChunJun中的落地实践
IM通讯协议专题学习(五):Protobuf到底比JSON快几倍?全方位实测!
【聚看点】多数据源事务处理-涉及分布式事务
怎么硬盘安装ubuntu?硬盘ubuntu安装教程
佳能5d系列哪个最好?佳能5DX相机参数
诺基亚6200上市价格是多少?诺基亚6200手机参数
烤箱如何预热?烤箱预热的方法有哪些?
短讯!IDEA没有新建jsp文件按钮
VS2022生成控制台引用程序,.net应用导出成exe文件,发部成独立文件的详细图解
MySQL学习笔记2
网页字体变大是怎么回事?网页字体变大了怎么还原?
洞庭连天是什么意思?洞庭连天九疑高是什么生肖?
国庆一词最早出现在什么时候?国庆一词最早出现在什么地方?
蝴蝶发现花蜜靠的是什么?蝴蝶发现花蜜的句子有哪些?
造梦西游3金角大王怎么打?造梦西游3金角大王掉什么?