最新要闻
- 学堂有名堂|30分钟午睡时间,教室里睡不着睡不好怎么办?黄浦区这所小学展开了研究
- 比亚迪高管回怼长城举报:挡别人的路 不会让自己行得更远|天天消息
- 单价6.5亿 国产大飞机快能坐了 东航C919将于近期投入实际运营 当前要闻
- 全球播报:恩怨还没完!暴雪在中国起诉网易雷火公司
- 顶配16999元 联想YOGA Air 32 4K一体机发布:13代i9+RTX 4050 一线连所有
- 1.28kg超轻身材!联想发布YOGA Air 14s 2023轻盈本 天天微资讯
- 全国护肤日(国际爱肤日):关注内外抗衰 远离皮肤疾病
- 最美小米手机!小米Civi 3亮相
- 减肥新方法!研究证实画饼真的能充饥|焦点滚动
- 新一代自拍之王!小米Civi 3前置双主摄:拍照Vlog全面兼顾 天天即时
- 称比亚迪污染物排放不达标 长城举报的是个啥:油箱成争议焦点
- 暖心!国羽苏杯夺冠黄东萍视频连线王懿律,黄鸭组合一同登台领奖
- 当前通讯!你怎么看?统计称上海人能挣钱更能花钱 全国北京人赚的钱最耐花
- 图灵奖得主:人类大脑是生物机器 一定会有超级AI超越它 今日热议
- 焦点消息!《雨血》精神续作!国产黑暗武侠大作《影之刃零》发布首支预告
- 天天关注:黄芪加枸杞大枣泡水喝的功效与作用 枸杞大枣泡水喝的功效与作用
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
KKRT-PSI
KKRT库:https://github.com/osu-crypto/BaRK-OPRF
文章:Efficient Batched Oblivious PRF with Applications to Private Set Intersection-2016
(资料图片)
方案
解读论文,参考:Efficient Batched Oblivious PRF -Private Set Intersection
关键词:两方PSI、ORFT、OTE
引言
KKRT-PSI方案使用了OTE(OT扩展)、OPRF、Cuckoo哈希等技术,在大集合场景、局域网(带宽20GB/s)下运行效果最好。
方案构造思路:先设计一个OTE,进而设计一个OPRF,最后设计一个PSI
基础
1-2 OT
协议功能:Sender不知道Receiver的选择\(r\);Receiver只知道\(X_r\)
协议实现:有基于RSA的、基于DH的、基于ECC的等。
下面介绍的是Naor-Pinkas-OT,Naor和Pinkas通过三次公钥密码学操作实现了半诚实模型下的1-2 OT:
论文:Efficient oblivious transfer protocols-2001
参考:Naor-Pinkas茫然传输协议
其中\(E_{r,2}\)表示\(E_r\)的第二部分,若\(r=0\),则:
安全性:Sender根据\(PK_0\)不能反推出\(k\);Receiver根据\(g^a\)不能反推出\(a\)。
1-2 OTE
1-2 OT在实际应用中,每次都需使用一次,效率较低,所以下一步采用“固定数量的OT来实现任意数量的OT”,例如下图只需要使用\(k\)次1-2OT即可实现,其中\(k\)是根据安全参数决定的。
Ishai、Kilian、Nissim和Petrank于2003年提出基于矩阵变化实现少量1-2OT和对称密钥构造大量OT实例的不经意传输扩展协议。
论文:Extending Oblivious Transfers Efficiently-2003
参考:[IKNP03] Extending Oblivious Transfers Efficiently
本文提出了一种OT扩展协议,即\(k\)次1-2OT实现了\(m\)次1-OT,其中\(k
分析:
注意:\(m_i\)表示列,\(m^i\)表示行
- 输入
- S:\(m\)对\((x_{j,0},x_{j,1})\),其中\(x_{j,b}\)是一个\(l\)bit的字符串
- R:选择比特\(r=(r_1,...,r_m)\in[0,1]\)
- 输出:
- R:得到\(m\)个\(x_{j,b}\)
- 协议:
- 两方执行\(OT_m^k\)协议,S得到一个矩阵\(Q_{m*k}\),其中\(q^i=(s_i*r)\oplus t^i,i\in[1,k]\)(从列看)
- 从行看,\(q_j=(s*r_j)\oplus t_j=\left\{\begin{matrix}q_j=t_j,if(r_j=0)\\q_i=s\oplus t_j,if(r_j=1)\end{matrix}\right.,j\in[1,m]\)
- 从而有:\(t_j=q_j\oplus s\)
- S:对于每对\((x_{j,0},x_{j,1}),j\in[1,m]\),计算\(y_{j,0}=x_{j,0}\oplus H(j,q_j),y_{j,1}=x_{j,1}\oplus H(j,q_j\oplus s)\),并发送给R
- R:计算\(z_j=y_{j,r_j}\oplus H(j,t_j)\)
- 两方执行\(OT_m^k\)协议,S得到一个矩阵\(Q_{m*k}\),其中\(q^i=(s_i*r)\oplus t^i,i\in[1,k]\)(从列看)
- 正确性:
1-n OTE
IKN03方案是用\(k\)次OT实现了\(m\)次1-2OT,其中\(k< 论文:Improved OT Extension for Transferring Short Secrets-2013 参考:KK13 OTE——Improved OT Extension for Transferring Short Secrets 用\(k\)次1-n OT传递了\(m\)个信息,每个消息是\(lbit\),且是n个中选1个,其中\(k>=n\)。 关于WH编码: 从KK13方案中,知道\(C_{WH}^k(a)\)是一种编码形式,即输入一个\(log^k\)bit的字符串\(a\),输出一个\(k\)个字符串\((c_0,...,c_{k-1})\),每个字符串为\(k\)bit,在进行隐私相等性测试时,即已知\(C_{WH}^k(a),C_{WH}^k(b)\),如何安全判断\(a\)和\(b\)是否相等,无需解码,只需比较\(C_{WH}^k(a),C_{WH}^k(b)\)是否相等即可,这里需要保证\(C_{WH}^k(a)\oplus C_{WH}^k(b)\)的汉明距离不小于计算安全参数。所以在KKRT16方案中的OTE,无需使用\(WH\)编码技术,只需要一个汉明距离不小于计算安全参数的伪随机函数即可。 发送方和接收者执行两方OPRF协议,发送方无输入,接收方输入元素\(x_i\),发送方输出密钥\(k\),接收方输出OPRF值\(F(k,x_i)\): 上面提到需使用伪随机函数,这里伪随机函数的功能相当于KK13中的哈希,即\(F=H(j,\mathbf{q}_{j}\oplus(\mathbf{c}_{r}\odot\mathbf{s}))\)。一共有\(m\)个\(r_i\),可以执行\(m\)次OPRF。另外在2019年PRTY19和2020年CM20都基于第3个属性对OPRF协议进行了进一步的改进,得到多点OPRF,实现了正常带宽下最快的PSI协议。 KKRT167中使用的OPRF由于是Batch、relaxed的,所以叫做BaRK-OPRF。 得到一个OPRF协议后,就可以很容易的构造一个PSI协议。例如下图: 但接收方需要进行\(O(n^2)\)次比较。 更多参考:https://www.cnblogs.com/pam-sh/p/16155650.html#cuckoo-hash Cuckoo hashing分为两个存储表,一个为Cuchoo哈希表,一个称为堆存储容器。(本文协议采用的这样的容器,之后的文章有采用无堆存储容器的Cuckoo hashing)。 Cuckoo插入元素\(x\)的算法如下: 上述基于一个理想的OPRF构造了一个简单的PSI协议,但效率(计算和通信)较低。 KKRT16-PSI协议遵循了PSZZ15基于KK13-OTE构造PSI的思路,采用Cuckoo hashing算法减少了比较次数。对于128bit的字符串和足够大的集合,求交速度比PSZZ15快3.1~3.6倍,具体说只需3.8s就能求出集合大小为\(2^{20}\)的交集。 「PSZZ15」Phasing: Private set intersection using permutation-based hashing-2015 「PSZ14」Faster private set intersection based on OT extension-2014 总结了PSI协议构造的方法:基于哈希的、基于公钥加密的、基于GC的、基于OT的等。改进了「PSZ14」方案:使用置换哈希减少 bin的位长、使用哈希和安全电路计算,降低电路深度和通信消耗、使用改进的OT协议改进计算和内存消耗。 对于在bin中的数据,\(z\)表示所用的哈希函数,OPRF的输入为\(x||z\),输出为\(F(k_{h_z(x)},x||z)\);对于在stash中的数据,OPRF的输入不变,即\(x\),输出为\(F(k_{1.2n+x},x)\),所以H和S的生成为:\(\begin{gathered}H_{i} =\{F(k_{h_t(x)},x\|i)\mid x\in X\},\text{for}i\in\{1,2,3\} \\S_{j} =\{F(k_{1.2n+j},x)|x\in X\},\text{for}j\in\{1,\ldots,s\} \end{gathered}\)。 这样PRF的值变为了\(n+ns\),且降低了OPRF的碰撞概率。 关于\(K=(k_1,....,k_{1.2n+s})\)的生成没有具体说,待补充。 环境:Centos7.6 计算6种情况下的PSI,输入数据规模为(\(2^8\),\(2^{12}\),\(2^{16}\),\(2^{20}\),\(2^{24}\))。对于每种情况,运行代码10次来计算PSI。输出包括平均在线/离线/总运行时间(显示在屏幕上)和output.txt文件。 int main(int argc, char** argv)主函数中的argc代表的是参数的数量,至少为1(argv[0]即.exe文件的路径)。argv为指针表示的参数,argv[0]表示第一个参数,argv[1]表示第二个参数,以此类推。 待补充 参考:隐私集合求交 [KKRT16] 是半诚实 OT-based PSI协议,基于 OT Extension, BaRK-OPRF 和 CuckooHash。 [KKRT16] 是第一个在千万( 224224)规模,长度(128 bits)数据集上,求交时间在1分钟之内的PSI协议. 隐语 SPU PSI 中使用了 [PSZ18] 提到的 3-way stash-less CuckooHash:
关键词:
>KKRT库:https: github com osu-crypto BaRK-OPRF>>文章:[EfficientBatchedObliviousPRFwithApplicationstoPrivateSetIntersection-2016](h1-$\infty $ OTE
BaRK-OPRF
Cuckoo 哈希
PSI协议
论文
程序
编译安装
## 下载git clone https://github.com/osu-crypto/BaRK-OPRF.git## 下载依赖库cd BaRK-OPRF/thirdpartybash all_linux.get## 会发现有些问题,需要将makelist中的"yum -Y"改为"yum -y"## 编译cd ..make## 会发现mpir安装的有问题,原来是给的下载链接失效了,重新找了一个替换上## mpir.get文件wget http://sources.buildroot.net/mpir/mpir-3.0.0.tar.bz2tar -xjf mpir-3.0.0.tar.bz2 mv mpir-3.0.0 mpirrm mpir-3.0.0.tar.bz2 cp ./mpir_patch/mpirxx.h ./mpir/cp ./mpir_patch/mpir.h ./mpir/cd mpir./configuremake## 重新编辑,即可make## 测试./Release/bOPRFmain.exe -t
测试
单元测试
# 输入数据集规模为2^{12},进行测试./Release/bOPRFmain.exe -t
模拟测试
# Sener./Release/bOPRFmain.exe -r 0# Receiver./Release/bOPRFmain.exe -r 1
# Sener./Release/bOPRFmain.exe -r 0 -ip
解读
基础
//提示函数,其中argv0指向exevoid usage(const char *argv0){std::cout << "Error! Please use:" << std::endl;std::cout << "\t 1. For unit test: " << argv0 << " -t" << std::endl;std::cout << "\t 2. For simulation (2 terminal): " << std::endl;;std::cout << "\t\t Sender terminal (localhost): " << argv0 << " -r 0" << std::endl;std::cout << "\t\t Receiver terminal (localhost): " << argv0 << " -r 1" << std::endl;std::cout << "\t\t Sender terminal (with ip input): " << argv0 << " -r 0 -ip
预处理
应用
隐语
KKRT-PSI
KKRT-PSI
环球简讯:创新应用场景下的可视化大屏:重新定义信息展示
今日视点:如何证明Servlet是单例的?
构建高可用云原生应用,如何有效进行流量管理?
天天观天下!【新华500】新华500指数(989001)25日下跌0.22%
学堂有名堂|30分钟午睡时间,教室里睡不着睡不好怎么办?黄浦区这所小学展开了研究
比亚迪高管回怼长城举报:挡别人的路 不会让自己行得更远|天天消息
单价6.5亿 国产大飞机快能坐了 东航C919将于近期投入实际运营 当前要闻
全球播报:恩怨还没完!暴雪在中国起诉网易雷火公司
顶配16999元 联想YOGA Air 32 4K一体机发布:13代i9+RTX 4050 一线连所有
1.28kg超轻身材!联想发布YOGA Air 14s 2023轻盈本 天天微资讯
【PC迁移与管理】上海道宁为每个用户和每个 PC 传输和迁移场景提供解决方案——PCmover_每日热讯
天天热推荐:Pytest - setup 和 teardown
全球即时看!yolov5+deepsort+slowfast复现
全国护肤日(国际爱肤日):关注内外抗衰 远离皮肤疾病
最美小米手机!小米Civi 3亮相
减肥新方法!研究证实画饼真的能充饥|焦点滚动
新一代自拍之王!小米Civi 3前置双主摄:拍照Vlog全面兼顾 天天即时
称比亚迪污染物排放不达标 长城举报的是个啥:油箱成争议焦点
暖心!国羽苏杯夺冠黄东萍视频连线王懿律,黄鸭组合一同登台领奖
Maven的核心解压与配置 观热点
当前通讯!你怎么看?统计称上海人能挣钱更能花钱 全国北京人赚的钱最耐花
图灵奖得主:人类大脑是生物机器 一定会有超级AI超越它 今日热议
焦点消息!《雨血》精神续作!国产黑暗武侠大作《影之刃零》发布首支预告
天天关注:黄芪加枸杞大枣泡水喝的功效与作用 枸杞大枣泡水喝的功效与作用
SRE心里话:要求100%服务可用性就是老板的无知_环球信息
助数字人民币“飞入寻常百姓家”
国外玩家吐槽PS发布会拉跨:是不是最差的一届?-环球新资讯
消失70多年 一度被认为灭绝:广西发现珍稀植物巨型蜘蛛抱蛋
世界今日讯!AMD超算三连冠!唯一投入实用的百亿亿次
高性价高颜值轻薄本代表作!华硕无畏15 2023 4299元首发抢购中|世界快播
焦点速读:老人遛狗不牵绳还将猫踢飞 网友吵翻:这是在保护猫 你怎么看?
焦点资讯:5人5月用容器技术保卫蓝天
关于 Workstation Pro 的基础知识
文物 | 博物馆文物的数字化保护与管理
马上就要过期的食品打一折:能买吗?安全吗?
马斯克计划打造世界第三大AI公司 或整合特斯拉和推特
世界快报:强对流天气预警:今天起 多地将有8-10级雷暴大风或冰雹
奇丑无比的洞洞鞋凭啥风靡全球?但是 绝对别穿它上扶梯-天天热消息
蔚来ES6上市当天 李想立下flag:10月份理想L7月销破2万辆_前沿热点
天天动态:弃“元”投“AI”,传百度副总裁马杰加入创新工场,成立AIGC公司
实时:gPTP时钟同步(时间同步服务器)助力智能驾驶应用
当前消息!直播源码技术实现游戏组队功能
【环球财经】惠誉评级把美国长期外币发行人违约评级展望列为“负面”
美媒:无人机袭击克宫或为乌特别部门策划-全球热讯
springboot~统一处理日期请求参数java.utils.Date和java.time.LocalDate_天天播报
【一步步开发AI运动小程序】七、进行运动计时、计数
36.8万起!蔚来全新ES6开卖:激光雷达、零百4.5秒 会成爆款吗
入门即高配!比亚迪宋Pro DM-i冠军版今日上市:纯电续航再提升
超110万辆特斯拉到底何时召回?时间点来了 强制单踏板再见
百公里油耗仅仅7.4升!依维柯聚星正式上市:13.68万元起
全新宝马5系发布:内饰、科技大升级 看眼后视镜就能自动变道
世界今亮点!在旧时光里注入新生机——湖南郴州“唤醒老屋”行动观察
全球快报:第六章.数据结构与算法基础(重点)
今日快讯:海康威视SDK - 门禁admin用户密码设置
当前速递!走进Linux世界,学习Linux系统的必备指南
最美不过二次元【AI】
黑人女玩家谈《Forspoken》差评如潮:种族主义者的偏见|世界观热点
结婚6年没孩子 查出丈夫非男性:医生科普是性反转综合征 网友刷新认知
焦点短讯!Windows 11打破隔阂 苹果安卓手机都能连 五大功能你用过没?
最高省1800元!iPhone 14 Pro系列京东618便宜了:抢券6499元起
当前关注:首款高通骁龙W5+智能手表!TicWatch Pro 5发布 续航45天
学系统集成项目管理工程师(中项)系列26_新兴信息技术-环球短讯
tn系统的三种适用范围_tn系统 天天新要闻
【环球时快讯】国际金融市场早知道:5月25日
四大证券报精华摘要:5月25日-环球今亮点
索尼宣布串流掌机
磁带存储不死!2022年逆市增长 2028年机械硬盘将消失?
天天微动态丨能像纸一样弯曲!我国成功研制出高柔韧性单晶硅太阳电池
世界微速讯:惠普新款暗影精灵9锐龙版上架:满血锐龙7+RTX 4060 首发6799元
今日dnf主线任务没了_dnf主线任务没了怎么办
做好持久战准备!小米自研芯片决心不动摇:盘点小米造芯之路
《刺客信条:幻景》10月12日发售:预售已开启_世界看热讯
世界焦点!小萝莉被杀真实案件 小萝莉被
快讯:将Android手机无线连接到Ubuntu实现唱跳Rap
gitlab ci 集成 eslint/prettier/tsc 做代码审查,并使用 eslint 输出作为显示代码质量 天天新视野
环球快播:人类暴露?外星文明快要联系地球了:美国算出时间
OPPO Pad 2新版开启预售:天玑9000加持 2599元|每日播报
焦点热议:国民神车MINI EV销量暴跌:五菱还有下一个爆款吗
最伟大Windows降临:操作系统彻底改变
iQOO Pad预售:最强天玑平板 2389元起
山东省高校毕业生就业信息网 山东省毕业生信息网
焦点观察:宝宝晚上睡觉不踏实总是翻来覆去_宝宝晚上睡觉不踏实翻来覆去怎么办
焦点日报:这些员工申报个税 可扣除6万元减除费用
天天速递!电子科大和四川美院第三届联合教学与创作成果展开幕式举行
神车卡罗拉迎来最新版,第五代丰田 THS 升级在哪?-今日播报
全球快播:英国通胀降至8.7%,但食品价格仍疯涨!鲍里斯又被告到警方,还是因为派对门…
湖南省湘电试研技术有限公司荣列先进制造业企业政策支持名单
Dubbo实践-全球热推荐
GPT-4通过了waitlist,私信爆了!
全球今日讯!10-阻塞赋值和非阻塞赋值
中国驻洛杉矶总领馆提醒中国公民防范电信诈骗
世界热推荐:小米机皇赢麻了!13 Ultra京东好评率超过99%
纯白千层镜!影驰RTX 4060 Ti 8GB星曜OC图赏
员工每天带薪上厕所3至6小时被解雇:法院判了 环球热闻
【天天快播报】618首销第一天Redmi霸占预售榜前三名 卢伟冰:孤独
精彩看点:Java设计模式-享元模式
这对中意“姐妹”世界遗产地 共话生态保护_世界微动态
多地加快推进基础设施工程建设
韩一季度总和生育率0.81 创历年同期最低