首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 密码应用
    3. 发新帖
[求助]两个人各持有一个[1,5]之间的整数，如何在不泄露各自持有数字的情况下，比较持有的数字是否相等
发表于: 2018-8-31 14:40 6242

[求助]两个人各持有一个[1,5]之间的整数，如何在不泄露各自持有数字的情况下，比较持有的数字是否相等

cejay 活跃值
2018-8-31 14:40
6242
两个人各持有一个[1,5]之间的整数，如何在不泄露各自持有数字的情况下，比较持有的数字是否相等。
一个类似的问题是“姚氏百万富翁问题”，但是这个问题解决的是如何在不公开的情况下判断两个人持有数字的大小。在我这里只是判断持有的数字是否相等，即使连大小都不能被猜出来
求熟悉相关问题的同志给点思路，或者现成的算法，感激不尽！！！

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

收藏
免费 ・0
支持
分享
最新回复 (13)
bambooqj
雪    币： 783
活跃值： (1121)
能力值： ( LV5，RANK：78 )
在线值：
发帖
回帖
粉丝
私信
2 楼
数学问题不懂..有个思路不知道对不对..

持有数字  1 - 5  

已知 随机数不随机 . 大部分编程语言随机数算法基本相同  比如  srand(0)  rand 第一次必为38.当然 这个随机数算法 你可以自己去实现.

我以1为 随机数种子    循环X次 这个X可以用时间戳计算 最好不要太大. 得到 结果  X=666  结果=26740   
发送  666.26740 到你那边    带入 1-5 进行查询对比.比较笨 主要好写  2333 资源耗费也比较大..不过 我这种小学毕业的只能这个程度了.

数学算法的话 应该 用  圆周法或者方程模式吧..反正 我就是水个经验.说的不对别打我.


最后于 2018-8-31 15:13 被bambooqj编辑 ，原因：
2018-8-31 15:10
0
yeyeshun
雪    币： 775
活跃值： (3420)
能力值： ( LV7，RANK：140 )
在线值：
发帖
回帖
粉丝
私信
3 楼
加入一个相同的第三方数据，增加复杂度，然后求出一个HASH，对比HASH是否相等就知道了。如果比大小的话不行，但是只判断是否相等是足够的
2018-8-31 15:31
0
bambooqj
雪    币： 783
活跃值： (1121)
能力值： ( LV5，RANK：78 )
在线值：
发帖
回帖
粉丝
私信
4 楼
yeyeshun 加入一个相同的第三方数据，增加复杂度，然后求出一个HASH，对比HASH是否相等就知道了。如果比大小的话不行，但是只判断是否相等是足够的
还是岳父大人懂.
2018-8-31 15:34
0
cejay
雪    币： 19
活跃值： (40)
能力值： ( LV3，RANK：20 )
在线值：
发帖
回帖
粉丝
私信
5 楼
谢谢 回复，此方法最终需要每个数带入对比，如果数字不相同，也是应该会导致知道对方持有的数字的吧
2018-8-31 15:34
0
cejay
雪    币： 19
活跃值： (40)
能力值： ( LV3，RANK：20 )
在线值：
发帖
回帖
粉丝
私信
6 楼
yeyeshun 加入一个相同的第三方数据，增加复杂度，然后求出一个HASH，对比HASH是否相等就知道了。如果比大小的话不行，但是只判断是否相等是足够的
谢谢回复，您的方案 如果加入了相同的第三方数据，会导致可以根据对方hash，通过自己的遍历得到对方原始值得（因为就5个数，挨个数算下hash就知道了）
2018-8-31 15:44
0
bambooqj
雪    币： 783
活跃值： (1121)
能力值： ( LV5，RANK：78 )
在线值：
发帖
回帖
粉丝
私信
7 楼
cejay 谢谢 回复，此方法最终需要每个数带入对比，如果数字不相同，也是应该会导致知道对方持有的数字的吧
算法在你自己手里啊...就算我用圆周法 我也是要带数做差啊.
2018-8-31 15:48
0
cejay
雪    币： 19
活跃值： (40)
能力值： ( LV3，RANK：20 )
在线值：
发帖
回帖
粉丝
私信
8 楼
感谢回复，但是您的方案会导致手中持有的数字会泄露的
2018-8-31 15:59
0
轩辕之风
雪    币： 2291
活跃值： (938)
能力值： ( LV8，RANK：130 )
在线值：
发帖
回帖
粉丝
私信
9 楼
cejay 谢谢回复，您的方案 如果加入了相同的第三方数据，会导致可以根据对方hash，通过自己的遍历得到对方原始值得（因为就5个数，挨个数算下hash就知道了）
根据这个思路扩展一下，如果这个第三方数据是个不可预测的数呢？比如引入一个执行时动态获取时间毫秒数，你不就不能根据HASH值去反推了吗
2018-8-31 17:17
0
cejay
雪    币： 19
活跃值： (40)
能力值： ( LV3，RANK：20 )
在线值：
发帖
回帖
粉丝
私信
10 楼
轩辕之风 根据这个思路扩展一下，如果这个第三方数据是个不可预测的数呢？比如引入一个执行时动态获取时间毫秒数，你不就不能根据HASH值去反推了吗
感谢回复，两个互不信任的人即使同时引入不可预测的数据，也是可以遍历反推的，你想想看
2018-8-31 17:22
0
arab
雪    币： 8050
活跃值： (3749)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
11 楼
抽象一下, 楼主的需求是在指定的区间[a,b]内, 求算法F, 使得在不泄露x1, x2的情况下, 能通过F(x1), F(x2)的值比较x1, x2的大小或是否相同.
那么这就有个问题了, 谁来比较 F(x1), F(x2)? 
如果不引入双方可信的第三方的话, 在[a,b]范围很小的情况下, 无论用什么算法F, 双方都可以使用遍历的方式穷举出所有数x对应的F(x), 从而由F(x)得到对方的数据x.
2018-9-3 16:10
0
jmpcall
雪    币： 3352
活跃值： (10987)
能力值： ( LV9，RANK：240 )
在线值：
发帖
回帖
粉丝
私信
12 楼
数字是几，就拿几克的砝码，天平中间用东西隔开。
2018-9-3 18:02
0
cejay
雪    币： 19
活跃值： (40)
能力值： ( LV3，RANK：20 )
在线值：
发帖
回帖
粉丝
私信
13 楼
arab 抽象一下, 楼主的需求是在指定的区间[a,b]内, 求算法F, 使得在不泄露x1, x2的情况下, 能通过F(x1), F(x2)的值比较x1, x2的大小或是否相同. 那么这就有个问题了, 谁来比 ...
你说的对，需要规避可穷举的问题。
2018-9-4 17:00
0
wawal哇
雪    币： 20
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
14 楼
用姚教授的安全两方计算没问题啊，判断相等这个命题是可以转换成门电路的。
具体的，设两方为A、B;  A为证明方，B是验证方；GC阶段A为A1至A5和B1至B5分配随机数标识r1-r10，kdf得出所有密钥，k1=(r1,r6)...k25=(r5,r10)，A模拟所有执行结果，相同标1，不同标0，用k的哈希对执行结果加密，计算y1=enc(h(k1),1)....y25=enc(h(k25),1); 把Y数组顺序置乱发给B;同时，A将自己选的数的标签ra(r1-r5中的一个)发给B.
B的视角：25个密文(y1-y25，乱序), A的标签ra，如果B能拿到A对自己选的数打的标签rb，就可以计算kdf(ra,rb)=k,进而计算25次dec(y,k)，其中只有一次能正确解密，解密后得到1代表相同，0代表不同。如果A将B的五个标签都发给B，B就可以通过解密穷举出A的数，但A也不能直接问B你选的哪个数。
这里B需要用到OT(oblivious transfer)协议来得到rb，里面有rsa的交互，具体不展开了，OT达到的目的是：A拥有r6-r10五个标签，B确定自己选的数，直到协议完成，A不知道B选的是哪个，B能获得与所选数对应的rb，但不能获得其他四个r。
2018-9-28 17:17
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//