最新要闻
- 每日快讯!元旦假期首日火车票今开抢!迎出行小高峰:五大热门目的地出炉
- 观天下!Find N2系列发布背后:OPPO再次展示对产品精益求精态度
- 天天要闻:全国冻哭预警地图来了:周末20余省份或被冻哭 冷到破纪录
- 热议:售价超300万!乔布斯亲手编号Apple-1电脑落锤成交:46年后 开机画面眼前一亮
- 世界最大独立圆柱体水族馆爆裂:1500多条鱼全军覆没
- 世界杯决战前夕 法国又有两大主力倒下!5人感染神秘流感
- 【环球热闻】被加价千元:AMD喊话正加大RX 7900系生产!NV 4080笑而不语
- 世界上最大的鱼缸今日突然破裂:100万升水泄露 1500条鱼死亡
- 放假3天不调休!2023年元旦假期首日火车票开售 除夕票这一天就能买
- 天天报道:学谁不好学特斯拉!几十万的宝马车 容不下一个收音机
- 观天下!骗子诈骗1250万 买彩票中1450万:已退还给39名聋哑人
- 全球热讯:XSX性能比PS5强 但为何游戏性能总是输?
- 天天热点!女子发烧敷20分钟面膜揭下变3D立体面具 医生提醒:影响退热 当心面瘫
- 方便面消费第一大国是我们:超6成人每周吃三次
- 热推荐:锂金属电池爱长枝晶?韩国科学家找到破解之法
- 【当前独家】确认了!《阿凡达2:水之道》没有片尾彩蛋
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
安全多方计算(1):不经意传输协议
学习&转载文章:安全多方计算(1):不经意传输协议
(相关资料图)
前言
在安全多方计算系列的首篇文章(安全多方计算之前世今生)中,我们提到了百万富翁问题,并提供了百万富翁问题的通俗解法,该通俗解法可按图1简单回顾。
图1 百万富翁问题通俗解法
百万富翁问题通俗解法场景中,我们可以将Alice和Bob的诉求总结如下:
Alice:有9个装有物品的箱子,Bob只能打开其中一个箱子看到物品,看不到其他箱子内的物品。
Bob:不希望Alice知道自己打开的是哪个箱子。
百万富翁问题通俗解法可以通过密码学中的n选1的不经意传输协议(Oblivious Transfer,OT)完美解决。
通过百万富翁问题通俗解法场景描述,对OT协议解决的问题可抽象为:Alice拥有\(n\)条消息\({m_1,…,m_n}\),Bob想知道其中一条消息\(m_i\);通过执行OT协议,Bob可以正确获得想要知道的消息\(m_i\),且无法获得其它\(n-1\)条消息,而Alice无法知道Bob获得的是哪条消息。
OT协议按研究类别区分,可以分为以下3种OT协议:
- 2选1的OT协议(\(2\)条消息中正确解密(选)\(1\)条)
- n选1的OT协议(\(n\)条消息中正确解密(选)\(1\)条)
- OT扩展协议(\(n\)条消息中正确解密(选)\(m\)条,\(m
受篇幅所限,本文仅介绍2选1与n选1的OT协议,OT扩展协议则在后续系列文章中进行介绍。
利用RSA加密实现n选1的OT协议
自1981年提出以来,OT协议有多种多样的实现形式,其中最容易理解的是基于RSA公钥算法实现的n选1的OT协议[1]。
RSA加解密过程简介
此处不讲解RSA原理,只介绍RSA加解密过程和用到的参数,便于密码学知识储备不足的读者理解后面的OT协议。
RSA密钥参数:\(N=p*q\),\(L=(p-1)*(q-1)\)其中\(p\)和\(q\)为大素数。
RSA公私钥对:生成\(d\)和\(e\),满足\(d\)与\(L\)互质,\(e\)与\(L\)互质,且\(d*e(mod L)=1\),则令\((d,N)\)为公钥,\(e\)为私钥。
则RSA算法对明文\(m\)(\(m\)为大整数)的加解密过程如图2所示。
图2 RSA算法加解密计算过程
RSA实现n选1的OT协议过程描述
基于RSA公钥算法实现的n选1的OT协议执行过程如图3所示。
图3 基于RSA公钥算法实现n选1的OT协议执行过程
协议执行过程分为4个步骤:
- Alice有\(n\)条消息,则产生\(n\)个RSA公私钥对,并将\(n\)个私钥保留,\(n\)个公钥发送给Bob。
- Bob随机产生一个大整数key,假定Bob想要获得第\(t\)条消息,则Bob用收到的第\(t\)个RSA公钥加密大整数key,加密计算结果为\(s\),Bob将\(s\)发送给Alice。
- Alice用保留的\(n\)个RSA私钥,依次解密\(s\),获得\(n\)个解密结果,依次为\({key1,key2,…,keyt,…,keyn}\);利用对称加密算法,利用\((key1,...,keyn)\),加密对应的消息\((m1,...,mn)\),得到密文消息\((M1,...,Mn)\),将\((M1,...,Mn)\)发送给Bob。
- Bob利用自己掌握的大整数\(key\)作为密钥,对第\(t\)条密文\(Mt\)进行对称解密,则得到想要的第\(t\)条原始明文消息\(mt\)。
n选1的OT协议解决百万富翁问题
将图1中的百万富翁问题和图3中的n选1的OT协议结合,我们可以对图1中的操作步骤做如图4的改造:
Step1:Alice构造9条明文消息,序号\(
Step2:Alice与Bob执行9选1的OT协议,解密第7条消息,看到0,\(y
图4 基于n选1的OT协议实现百万富翁问题
协议分析
该协议执行过程可以满足OT协议中Alice和Bob的核心诉求,关键在于第2步和第3步。
第3步中,Alice利用\(n\)个私钥逐个尝试解密\(s\),得到\((key1,...,keyn)\),由于\(s\)是由Bob利用第\(t\)个公钥加密整数key计算得到的,因此只有keyt=key,但对于Alice来说,\((key1,...,keyn)\)都是大整数,根本无法区分哪个才是Bob掌握的key,实现了Bob的诉求,即Alice无法知道Bob选择的是哪条消息。
对于Bob来说,拿到了\(n\)个密文消息\((M1,...,Mn)\),但是自己只有一个key,此key只能解密消息\(Mt\),对于其他\(n-1\)条消息则无法解密,实现了Alice的诉求,即Bob只能正确得要Bob想要得到1条消息,无法正确得到其他\(n-1\)条消息。
如果\(n=2\),则该n选1的OT协议就退化成了2选1的OT协议。
虽然基于RSA实现的n选1的OT协议简单易懂,但是却存在如下缺陷:
- key为0或1时,Alice的诉求无法保证。Bob如果将key指定为0或1,则根据图2中RSA的加解密计算方法,无论私钥\(e\)是否正确,解密后的\(m0=m\)均成立,意味着第3步中,Alice强行解密\(s\)得到的\((key1,...,keyn)\)均等于key(看加密就懂了~),则Bob可以解密所有的消息,获得所有的明文\((m1,...,mn)\)。
- 协议计算效率有待优化。第1步Alice需要产生\(n\)个RSA公私钥对,而RSA公私钥对的产生比较耗时。
为了提高安全性和计算效率,还有基于其他密码学方法的OT协议,如基于离散对数的OT协议,将在本文第四节和第五节中进行介绍。(如果您仅希望简单了解OT协议的原理和能解决的问题,则读到此处足矣,本文后面的内容适合有一定密码学基础读者。)
基于离散对数实现2选1的OT协议
为了优化OT协议计算效率和安全性,学者一般对2选1的OT协议和n选1的OT协议分开进行研究。对于2选1的OT协议,Tung Chou[2]于2015年基于离散对数问题,在DH密钥协商协议的基础上设计的2选1的OT协议,被认为是一个简单清晰的2选1的OT协议。
离散对数简介
离散对数问题通俗理解:有限域\(F_p\)(\(p\)为大素数,\(F_p\)中元素共\(p-1\)个整数,取值\([1,p-1]\))上的大整数幂乘取模容易计算,即\(a*b mod p=c,a,b\in F_p\),而计算对数是很困难的,即 \(log_a^c(mod p)=b\)。
离散对数实现2选1的OT协议过程描述
基于离散对数实现2选1的OT协议执行过程如图5所示:
图5 离散对数实现2选1的OT协议执行过程
协议执行过程分为4个步骤:
- Alice有消息\(m0、m1\in F_p\)*,则Alice挑选\(g,a\in F_p\),并计算\(A=g^a mod p\),将\(A、g、p\)发送给Bob。
- Bob想要第\(\sigma\)条消息(\(\sigma=0\)或1),Bob挑选\(b\in F_p\)*,并计算\(B=A^\sigma *g^b mod p\),将B发送给Alice。
- Alice利用\(a、A、B\),按照图4中的步骤3计算\(C0\)和\(C1\)的值,然后用\(C0\)为密钥,对称加密\(m0\);用\(C1\)为密钥,对称加密\(m1\)。将加密后的密文\(M0\)和\(M1\)传递给Bob。
- 这里的密文\(M_0\)和\(M_1\)只有一个是“可用”的,也就是说\(C_0\)和\(C_1\)只有一个是可用的,当\(\sigma =0\)时,\(C_0\)是可用的;当\(\sigma =1\)时,\(C_1\)是可用的。
- Bob利用\(A\)和\(b\)计算解密密钥\(g^{ab} mod p\),对称解密对应的密文后拿到想要的正确消息。
协议分析
该协议的核心步骤是步骤2和步骤3,对这两步中的参数B、C0、C1进行展开,展开后如图6所示。
图6 2选1的OT协议部分参数展开
从图6的展开式可知,无论\(\sigma =0\)还是\(\sigma =1\),\(C0\)和\(C1\)始终只有一个为\(g^{ab}\),而另一个对于Bob而言则不可计算(Bob不知道\(a\)的值),\(g^{ab}\)的计算实质上就是DH密钥协商协议。
对于Alice来说,仅知道\(B、A、g\),不知道\(b\)的情况下,由于离散对数问题难解,因此是无法推断出\(\sigma =0\)还是\(\sigma =1\)。
与2.2的协议相比,该协议不存在Bob选择特殊的\(b\)会导致密文消息\(M0\)和\(M1\)同时正确解密这一缺陷(只能正确解密其中一个)。
基于离散对数实现n选1的OT协议
本章节将以Wen-Guey Tzeng[3]提出的高效n选1的OT协议为例,讲解如何基于离散对数实现基本的n选1的OT协议。
离散对数实现n选1的OT协议过程描述
基于离散对数实现n选1的OT协议执行过程如图7所示。
图7 离散对数实现n选1的OT协议执行过程
协议执行过程分为4个步骤:
- Alice有\(n\)条消息\({m1,…,mn}\),\(mi\in G\)(\(G\)代表素数域\(F_p^*\)),挑选\(G\)的两个生成元\(g\)和\(h\),将\(g,h,p\)发送给Bob。
- 假定Bob想获得第\(t\)条消息,则Bob随机选择大整数\(r\in G\),并计算\(y=g^r*h^tmod p\),将\(y\)发送给Alice。
- Alice利用\(y,g,h\),分别对\(n\)条消息,重复执行图6中左下角的计算步骤,每一次执行都会随机选择大整数\(k_i\in G\),并结合消息\(mi\)计算\(ai\)和\(bi\)。然后将\(n\)组\((ai,bi)\)发送给Bob。
- Bob拿到\(n\)组\((ai,bi)\)后,利用掌握的大整数\(r\),计算想要的第\(t\)条消息\(m_t=b_t∕(a_t)^r\)。
协议分析
对于第4步Bob的操作,我们把消息\(m_t\)泛指为\(m_x\),则对\(m_x\)的计算公式展开后如图8所示。
图8 消息mx的计算公式展开
从图8可以看出,要想获得消息\(m_x\),要么令\(x=t\),此时消息为Bob想要获得的消息;要么计算出\(h^{(t-x)*k_x}\),由于\(k_x\)是Alice的秘密数字,因此保证了Bob不可能正确解密除消息\(m_t\)之外的其余\(n-1\)条消息。
对于Alice来说,虽然知道\(y,g,h\),但是不知道\(r\)的情况下,由于离散对数问题难解,因此是无法推断出\(t\)的正确值。
与2.2的协议相比,该协议不存在Bob选择特殊的\(r\)会导致\(n\)条消息同时正确解密这一缺陷,同时也不存在需要产生\(n\)对公私钥这一耗时操作。
总结
本文介绍了OT协议和3个基于密码学实现的OT协议实例,并结合百万富翁问题的通俗解法看到了OT协议的应用实例,这样的实例很难看出OT协议的重要性。
其实OT协议是安全多方计算中很重要的一个协议,在安全多方计算系列的首篇文章(安全多方计算之前世今生)中,我们提到,安全多方计算的通用技术路线可以用混淆电路解决,而混淆电路的构建离不开OT协议。因此,下期文章将会讲解如何通过OT协议实现混淆电路,以及如何实现基于混淆电路的通用安全多方计算路线。
参考文献
[1] https://en.wikipedia.org/wiki/Oblivious_transfer
[2] Chou T , Orlandi C . The Simplest Protocol forOblivious Transfer[C]// International Conference on Cryptology and InformationSecurity in Latin America. Springer International Publishing, 2015.
[3] Tzeng W G . Efficient 1-out-of-noblivious transfer schemes with universally usable parameters[J]. IEEETransactions on Computers, 2004, 53(2):p.232-240.
安全多方计算(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金角大王掉什么?
传闻中的陈芊芊韩烁失忆是第几集?传闻中的陈芊芊韩烁失忆是真的吗?
爱情公寓决战紫禁之巅是第几集?爱情公寓决战紫禁之巅花了多少经费?
曾小莲是什么梗?爱情公寓曾小莲是哪一集?
睢宁县属于哪个市?睢宁县旅游景点有哪些?
类似于惊天魔盗团的电影有哪些?惊天魔盗团剧情解析
独家首发是什么意思?独家首发和普通授权有什么区别?
环球短讯!认证管理(锐捷网关篇)
世界即时看!C语言字符串拆分的两种方式strtok和正则表达式
全球通讯!低代码靠不靠谱?看看低代码在智能物联系统搭建中的应用
美国一战机垂直降落失控 飞行员弹射7秒落地:现场机头先撞地
世界时讯:可拆卸手柄神似Switch!OnexPlayer 2掌机海外发布:起售价超6200元
全球要闻:混动车鼻祖上新 全新丰田普锐斯售价公布:约19.10万元起
一加10T漫威限定版上架:用4年仍然很流畅 4700元
天天观焦点:三连降稳了!新一轮油价三天后开调:预计下跌0.41元/升
世界资讯:因MacBook Pro蝶式键盘翻车:苹果赔了3个多亿
速递!贾跃亭造车梦要成了?FF91交付计划公布 还差10几亿资金
全球热议:爱奇艺VIP会员今起涨价:连续包月黄金25元/月
今日热讯:浙江“火流星”现场被砸大坑!专家:捡到陨石碎片别用水清洗
焦点精选!机械硬盘真没人买!西数股价大跌 公司业绩要暴雷:或将大清库存
每日精选:V2Board机场项目泄露400余万条数据
环球快报:《阿凡达2:水之道》今日内地正式上映:票房瞬间破亿
日系车为什么在中国卖不动了?你为什么不买了?
每日速讯:Blazor和Vue对比学习(进阶.路由导航五):路由守卫
观点:【从零开始学爬虫】采集收视率排行数据
mvn 打包报错:no compiler is provided in this environment
天天微动态丨JavaScript DOM的性能优化详解
每日资讯:VUE的实例的生命周期
每日热门:河洛肉鸽卡牌《天外武林》上架Steam 明年1月发售
别急换机!本月还有6场发布会:劝你先等等再买
世界微动态丨《阿凡达:水之道》预测票房仅25.11亿!远不到《长津湖》一半
【环球新要闻】Epic大促开启 连续15天免费送游戏!75折套娃优惠券来了
【天天播资讯】RTX 4070 Ti跑分首曝:猛升46%、超越RX 7900 XTX