起源是我 2022 年 2 月 19 日回顾 @sillydaddy 的帖子 gpg 加密文件:一份加密文件,可以被不同的密码解密,彼时刚刚研究过叛徒追踪问题,于是就结合了一下,想法大概是这样的:
想要解决的问题有三个:
这些基础问题在 7 月 15 日完整解决,不过论文出版的问题一直难产(读作:一直被拒稿),直到 2024 年 6 月 3 日才被 IACR 最近新推出的期刊 Communications in Cryptology (密码学通讯)接受,并在 7 月 8 日出版。
本研究带来了我首篇单作者论文,并且得以实践一些我的新想法:
关于原帖比较有趣的 take-home message 是:
虽然运用密码学技巧,可以让密文比收件人列表还要短,但每个收件人解密都要付出额外的代价,总能耗(在渐近意义下)相比朴素算法会增加——而且这并不是因为人类很笨(不知道怎么做得更好),而是可以(无条件)证明安全的加密算法必然有此性质(不可能做得更好)。
那么,最后再向 @sillydaddy 说一声谢谢!
1
wowo243 163 天前 4
虽然看不懂,但是看起来很🐮🍺
|
2
enchilada2020 163 天前 via Android
很强 🐮🍺
|
3
yolee599 163 天前 via Android
研究密码学的都很🐂🍺
|
4
xiangchen2011 163 天前
蛮好的,支持!!
|
5
zapper 163 天前
别人摸鱼和我摸鱼的区别
|
6
pridealloverme 163 天前
老哥真的很🐂🍺
|
7
3M 163 天前 via Android
好兄弟,重新定义摸鱼😁
|
8
bruce0 163 天前
别人摸鱼和我摸鱼的区别
|
9
luzemin 163 天前
|
10
microchang 163 天前
真好!祝贺楼主!
|
11
lovelylain 163 天前 via Android 3
没点开看链接,可以这样实现吧:结果分为两部分,一部分是 aes 等对称加密的密文,另一部分是公钥及公钥加密的对称密钥列表。
1.每个人都生成公私钥,提交公钥; 2.加密的时候随机生成对称密钥并加密内容,再使用公钥列表加密对称密钥; 3.每个人都可以用自己的私钥解密出对称密钥,再解密内容; 4.可以通过逐一破坏密钥列表的方法,破坏后解密不了,没被破坏的能解密,来定位是哪个公钥对应的私钥被泄露。 |
12
aks 163 天前
作者叫罗辑?
|
13
lingeo 163 天前
理解了,密码学版的黄点追踪,为了做泄露溯源。
|
14
sillydaddy 163 天前 via Android 43
我有点受宠若惊,刚开始看到我还以为是我另外一篇关于匿名授权的帖子给了人启发,我更希望是那个帖子。。
gpg 的帖子只是吐槽 gpg 的没啥营养的帖子,没想到却能在某天收到特意的感谢,这种事情只能用“gee 猿巧合”来形容了。补充感谢站长提供的平台让美好的事情发生。 |
15
stardew 163 天前
牛哇
|
16
geelaw OP @lovelylain #11 朴素做法是这样的。不朴素的话,可以用程序混淆( program obfuscation )压缩密文,当然要保持逐一破坏的功能,最短可以让密文长度和收件人数无关。
|
17
pwelyn 163 天前
牛
|
18
Sawyerhou 163 天前
恭喜恭喜!
|
19
0312birdzhang 163 天前
看不懂,🐂🍺
|
20
Lyv5 163 天前
说好的大家一起摸鱼你们却在写论文。最后给大佬倒一杯卡布奇诺🐂🍺
|
21
nealHuang 163 天前
|
22
nealHuang 163 天前
|
23
sniperboy0829 163 天前 2
这不就是 blockchain 里面的 MPC 吗?早就有现成论文,算法了
|
24
yyancy517 163 天前 2
说好的大家一起摸鱼你们却在写论文。最后给大佬倒一杯卡布奇诺🐂🍺
|
25
zdw189803631 163 天前
摸条鲨鱼出来了,属于是
|
26
cxmokai 163 天前
罗辑你好,我是你的破壁人
|
27
bglucas 163 天前
好家伙, 我以为的摸鱼是摸小鱼. 大佬的摸鱼是摸鲸鱼
|
28
nomagick 163 天前
什么乱七八糟,民科?
攻击者持有两个密钥你怎么办?三个呢? 每增加一个你的查询复杂度怎样增加? |
29
RHG 163 天前
罗辑:摸鱼❌写论文✔️这是计划的一部分!🎭
|
30
BeforeTooLate 163 天前
我看到第一个在 V2 做学术的。
|
31
qqjt 163 天前
不是哥们,还能不能好好摸鱼了
|
32
objectxiang 163 天前
|
33
brant2ai 163 天前
解决内部加密及溯源的问题?
|
34
unii23i 163 天前
翻了一下看不懂
|
35
heywin 163 天前 4
v2 越来越高大上了 我都怀疑方滨兴也在这里摸鱼
|
36
awinds 163 天前
虽然看不懂,但是看起来很🐮🍺
|
37
phub2020 163 天前
不是,哥们,你来真的?我以为大家都是在这里摸鱼的,你怎么?我破防了~
|
38
jhdxr 163 天前
我也想问和 MPC 相比差异在哪?是在于“叛徒追踪”吗?
|
39
wentx 163 天前
这叫摸鱼?
|
40
2exhjx 163 天前
罗辑?是你吗罗教授
|
41
jadehare 163 天前
别人摸鱼摸出一篇论文。我摸鱼...那真的是在摸鱼
|
42
geelaw OP @nealHuang #22 原帖是这个意思。
@sniperboy0829 #23 MPC 不是 blockchain “里面的”,不太理解您在说啥。 我、审稿人认为该问题是新的,早期文献已经考虑或解决这个问题的概率微乎其微。 @jhdxr #38 这个问题和 MPC 可能都不算 remotely related 吧。没有涉及“多个人有秘密且他们想要计算多元函数”的情况。在“追踪”这个步骤里面,是任何一个想要找出叛徒的人都可以通过调用 D 来找到,在“脑内模型”里面 D 就是一个坐在云端的接口,或者(在中心化的版本里)可以想象成一个不理睬 DRM 的 DVD 盗播机器。 @nomagick #28 第 2 、3 、4 个问题的答案是,我在本帖的表述也力求准确: >某 *些* 人制造了程序……找出……哪 *个* 人的私钥…… 考虑的问题本来就涵盖了使用多个私钥建立 D 的情况。 你也可以参考现在版本里:摘要第一段最后一句话、定义 12 、脚注 8 、构造 2 、构造 3 。 关于民科的问题,拜资格主义( credentialism )不好。 |
43
Fred0410 163 天前 via iPhone
每个人的摸鱼并不一样..
|
44
wy315700 163 天前 6
|
45
Tumblr 163 天前
恭喜大佬!两位大佬可以说是强强联手了!
另外,在大佬的很多回复中学到了不少东西,在此感谢! |
46
barlogscc 163 天前
大佬你这论文是连着投了两年才被接收吗,太强了
|
48
cheneydog 163 天前
没意思,还是现有的对称加非对称的应用。
而不是新的密码学应用,协同解密、环签名、隐私计算什么的。 |
49
cccb 163 天前
清华大佬摸鱼都是看技术贴的吗,祝贺!
|
50
kaedea 163 天前 via Android
好奇,上世纪欧美那批大佬是不是也是在这样的氛围中取得学术突破的。
|
51
Webpoplayer 163 天前
不是,怎么你的`摸鱼` 跟我认知的摸鱼不一样啊??[/狗头]
|
52
cat9life 163 天前
牛 x 啊,中排祝贺
|
53
chf007 163 天前
最近正好有个业务场景要用到这种加密算法,大佬们看看还有其它方案不
有没有一种算法可以对一份文件加入 n 个用户(可以控制在可控范围内,不是无限多)标识进行加密或签名,然后对加密的文件进行分发,每个用户可下载这同一份加密后的文件,但是只能用自已的标识或密钥之类的来解密,不解密则不能正常查看。解密后的文件能够查看原文且能够判断出就是该用户解密的,该用户解密后的文件再次分发也能判断出是该用户解密的。 |
54
j5159UqX6UKa360u 163 天前 via Android
作为一个菜鸡有一个问题,解密后的文件能不能修改?如果能,如何追踪?
|
55
goforwardv2 163 天前
虽然看不懂,但是祝贺,牛掰
|
56
sniperboy0829 163 天前
@geelaw 你说的对,MPC 不是 blockchain “里面的”,MPC 最初我是通过 Blockchain MPC wallet 了解到的,MPC 是 Cryptography 领域的
|
58
dryadent 163 天前
楼主厉害,密码专业前来祝贺
|
59
insignificance 163 天前
追踪方法有用到 零知识证明?
|
60
Stoney 163 天前 via iPhone
清华大佬重新定义摸鱼
|
61
mustcool 163 天前
太强了
|
62
p1gd0g 163 天前 1
听着很像群签名、环签名啊。梦回研究生时代。
能中就好,祝贺。 |
63
qingshengwen 163 天前
群晖的 Sync Cloud 有个加密功能,解密的时候可以选择用密码(字符串),也可以选择用私钥文件
这两种都可以支持,我之前也很好奇这个是怎么实现的,看到 op 这个我觉得有异曲同工之妙 |
64
jocover 163 天前 via iPhone
可以用在 drm 系统上,追查谁泄漏的解密 key ,但是如果很多 key 都能解密,会有人暴力破解
|
65
haiyun81192 163 天前
祝贺楼主,太强了!
|
66
yuruizhe 163 天前
卧槽摸出 paper 来了
|
67
chengandc 163 天前
楼主可以把 LaTex 写的论文托管到 https://scienhub.com 免费 LaTex 论文编译以及托管
|
68
rekulas 163 天前
很 cool 我也喜欢加密学
|
69
zsmj1024 163 天前 via iPhone
恭喜楼主,祝楼主明年大满贯
|
70
justNoBody 163 天前
小弟能力有限,看不懂 op 写的论文。
但是我很好奇是如何追踪是谁破解的?这个破解的解密的过程不是离线的么?离线的情况还可以追踪到是谁解密的么? 不知道 op 可否再简单描述一下,感谢感谢 |
71
swordspoet 163 天前
@nomagick 不懂的时候,少说,多听,没坏处。
|
72
YsHaNg 163 天前
有没有兴趣做 MPC FHE
|
73
tryrain 163 天前 via Android
Congratulations!!
另外,说民科的先麻烦考上姚班再说吧。 |
74
fxyr123456 163 天前 1
@justNoBody 我以为我大致看懂了皮毛,故而斗胆解释一下。
- 追踪的前提是假定一个解密谕言机来扮演“破解器”的角色,当秘密(比如一篇小说)被盗版网站盗取发布之后,盗版网站就成为了这个谕言机。 - 追踪的原理大致是,我向这个谕言机 query n 段不同公钥加密的密文 ,当且仅当谕言机概率回复正确解密的明文,我们认为谕言机(也即破解器)拥有当前公钥所对应的密钥。 浅薄的理解,不确定对不对,还请指正。 |
75
CRVV 162 天前 1
@nomagick
@sniperboy0829 @jhdxr 11 楼 lovelylain 的回复已经给出了详细的方案,楼主也认可了他说的内容。 有人 “没点开看链接” 就直接给出了答案,所以,这论文真没多少干货。 核心内容只有不到 10 行的汉字,楼主写了三十多页的论文。 虽然这么说,这个论文也不是全无新意,要获得 “密文长度和收件人数无关” 这个性质,还是需要折腾一些花样进去。 我相信楼主说的 “该问题是新的”,而且这个问题显然和 MPC 没关系,MPC 是比这个复杂多了。 而且确实不民科,这个论文是一个典型的正经科研的玩法。把一些实际上没啥意思的东西套上各种高级的词汇,当然也确实包含了一点点的新东西,写一遍超长的 “论文”,发表在一个没人听说过的期刊上,然后得到 毕业证/学位证/职称 之类的东西。确实是很正经的科研,只不过不是我做事的风格,我更喜欢看到一遍半页的小文章来讲解这个花样。 而且能写出这么长的论文也是高级能力,这东西给我就只能写出来半页的内容,所以我早就不玩这些 “科研” 的东西了。 另外,关于环保,为什么不讨论消息变长带来的额外能耗?数据的存储传输都要消耗能量,凭啥这部分就当零来算了? |
76
geelaw OP @wy315700 #44 这个图好好玩,不过其实不像。比如,至少这个加密算法是安全的,但这个门上的锁和没有一样(
@barlogscc #46 投了两年才接受,不应该是太弱了吗……? @chf007 #53 要想多个人解密结果不同,需要泛函加密( functional encryption )。要想解密后的结果可以识别是谁,需要水印、指纹码( fingerprinting code )。不过这两个都不实用。 @insignificance #59 没有。 @iamyourking #54 @justNoBody #70 能够被追踪的不是单个解密结果,而是解密的 *能力*。 @fxyr123456 #74 其实 #11 就是答案了。 更具体一点的话,加密算法有一种特殊的模式,可以禁用 L 中一些人的解密能力。平常加密不禁用任何人。要追踪的时候,用特殊模式,测试禁用前 0, 1, ..., |L| 个人之后 D 解密能力的变化: 1. 禁用前 0 个人(平常)的时候 D 解密能力较强,禁用前 |L| 个人(所有人)的时候 D 的解密能力归零,因此在禁用的途中 D 的解密能力会逐步下降。 2. 如果 D 不蕴涵 i 的私钥,则根据加密算法的安全性,禁用 i 前后 D 的解密能力不能发生变化( D 此时不能知道 i 是否被禁用)。 综合这两点,如果禁用 i 前后 D 的解密能力明显下降,则指认 i 是叛徒。这个框架是 2006 年 [BSW06] 就知道的了。 实际的保障更强一些,用人话来说:如果 D 导致加密给 L 的密文稍微有一点儿不安全( D 不需要“能够完全解密”),那么可以识别 D 中蕴涵 L 里哪个人的私钥。 |
77
geelaw OP @CRVV #75 环保的考虑里面是计算了存储和传输数据需要的能量的,请注意“总能耗”的“总”字。
>要获得 “密文长度和收件人数无关” 这个性质,还是需要折腾一些花样进去。 获得这个性质所需要的技巧,我称之为“繁琐但常规的体操”。从技巧评判,这篇文章比较有趣的是环保问题,毕竟证明不可能性比证明可能性困难一些。至于问题本身是否有趣,每个人有不同的想法很正常。 您所谓“科研的玩法”,不可否认科研用作赖以生存的职业会有那种考量,但我的建议是晚一会儿想这个问题是一会儿。 |
78
CRVV 162 天前
@geelaw #77
根据 c24-ver1.pdf 第 25 页的内容,两个方案,一个有 Ω(N) 的时间复杂度和常数的空间复杂度,另一个有 Ω(N) 的空间复杂度和常数的时间复杂度,你能得到了结论说 > 总能耗(在渐近意义下)相比朴素算法会增加 你自己觉得这个结论能成立么? 我给出一个我能想到的最简单的模型,x y 都未知的情况下,Nx+y 和 x+Ny 哪个大?或者说你凭什么认为 x>y 或者 x<y ? 还是说这个“渐近意义”是指把数据加载到内存里面然后把解密跑 N 遍? |
79
geelaw OP @CRVV #78 你可能没有理解“总”能耗的含义。考虑发送电子邮件给 N 个人,自然期待 N 个人分别需要解密一次。
考虑 N 时间 1 长度的方案,那么每个收件人需要下载长度是 1 的密文,然后用 N 的时间运行解密算法,因此总能耗是 1*N+N*N = Theta(N^2)。 考虑 1 时间 N 长度的朴素方案,每个收件人需要下载的密文长度不是 N ,因为在 1 的解密所需时间内,整个长度是 N 的密文只有常数个位置被访问,因此每个收件人的下载是 1 ,解密时间是 1 ,总能耗是 1*N+1*N = Theta(N)。 两种情况里存储 O(N) 的密文以及在 O(N) 时间内加密所消耗的能量都被 Omega(N) 的下载、解密所吸收。 |
80
tcdh 162 天前 via Android
恭喜
|
81
sankooc 162 天前
不明绝历
|
82
nomagick 162 天前 1
一个违和的地方,就是一种基于不对称加密的通信机制,在一个攻击者持有了密钥之后,不是单纯对外披露解密后的密文,而是使用私钥本体制作一种解密程序并对外披露
而进行检测的时候,参与方却都能够 100% 7x24 及时有效地参与检测,毫不考虑信道故障 根本的问题是将密码和通信混合起来, 以通信为背景但却不考虑通信的问题 |
83
ZiLong 162 天前
同 V 鱼汝何秀
|
84
DannyVim 162 天前
同样是摸鱼,却摸出了不一样的境界。🧐
|
85
ContentProvider 162 天前
虽然看不懂,但是看起来很牛逼
|
86
814084764 161 天前
我有个实际的需求:如果将密钥安全的存在本地 并且 能离线解密使用? 有什么现成的方案吗?
|
87
814084764 161 天前
如果 --> 如何
|
88
RedSA 161 天前
GeeLaw...基佬。。。
|
89
good1uck 153 天前
这哥们清华的,之前有幸被他回答过一些 Leetcode 问题..
|