这是一个创建于 171 天前的主题，其中的信息可能已经有所发展或是发生改变。
起源是我 2022 年 2 月 19 日回顾 @sillydaddy 的帖子 gpg 加密文件：一份加密文件，可以被不同的密码解密，彼时刚刚研究过叛徒追踪问题，于是就结合了一下，想法大概是这样的：
- 一种公钥加密算法，每个人生成自己的密钥对（去中心化）；
- 加密的时候可以给任意一组人加密（使用这些人的公钥）；
- 解密的时候那组人里面的任意一个都可以解密（使用任意一个人的私钥）；
- 如果某些人制造了程序 D 用来解密针对一组人 L 的密文，则可以找出 D 里蕴涵着 L 里哪个人的私钥（“叛徒追踪”），即使不能查看 D 的代码（比如 D 是一个网络 API ）。
想要解决的问题有三个：
- 怎么定义这个玩意儿？
- 怎么造这个玩意儿？
- 能有多好的效率？
这些基础问题在 7 月 15 日完整解决，不过论文出版的问题一直难产（读作：一直被拒稿），直到 2024 年 6 月 3 日才被 IACR 最近新推出的期刊 Communications in Cryptology （密码学通讯）接受，并在 7 月 8 日出版。
本研究带来了我首篇单作者论文，并且得以实践一些我的新想法：
力求“思维透明”，以飨他人，论文的修订过程可以在 GitHub 仓库 GeeLaw/ahbtr 查看。
关于原帖比较有趣的 take-home message 是：
最朴素的实现也是最环保的实现。
虽然运用密码学技巧，可以让密文比收件人列表还要短，但每个收件人解密都要付出额外的代价，总能耗（在渐近意义下）相比朴素算法会增加——而且这并不是因为人类很笨（不知道怎么做得更好），而是可以（无条件）证明安全的加密算法必然有此性质（不可能做得更好）。
那么，最后再向 @sillydaddy 说一声谢谢！
90 条回复 • 2024-07-19 16:55:56 +08:00
 |
1
wowo243 171 天前  4
虽然看不懂，但是看起来很🐮🍺
|
 |
2
enchilada2020 171 天前 via Android
很强 🐮🍺
|
 |
3
yolee599 171 天前 via Android
研究密码学的都很🐂🍺
|
 |
4
xiangchen2011 171 天前
蛮好的，支持！！
|
 |
5
zapper 171 天前
别人摸鱼和我摸鱼的区别
|
 |
6
pridealloverme 171 天前
老哥真的很🐂🍺
|
 |
7
3M 171 天前 via Android
好兄弟，重新定义摸鱼😁
|
 |
8
bruce0 171 天前
别人摸鱼和我摸鱼的区别
|
 |
9
luzemin 171 天前
这**的叫摸鱼？谁家摸鱼能摸出论文？！
 |
 |
10
microchang 171 天前
真好！祝贺楼主！
|
 |
11
lovelylain 171 天前 via Android 3
没点开看链接，可以这样实现吧：结果分为两部分，一部分是 aes 等对称加密的密文，另一部分是公钥及公钥加密的对称密钥列表。
1.每个人都生成公私钥，提交公钥； 2.加密的时候随机生成对称密钥并加密内容，再使用公钥列表加密对称密钥； 3.每个人都可以用自己的私钥解密出对称密钥，再解密内容； 4.可以通过逐一破坏密钥列表的方法，破坏后解密不了，没被破坏的能解密，来定位是哪个公钥对应的私钥被泄露。 |
 |
12
aks 171 天前
作者叫罗辑？
|
 |
13
lingeo 171 天前
理解了，密码学版的黄点追踪，为了做泄露溯源。
|
 |
14
sillydaddy 171 天前 via Android 43
我有点受宠若惊，刚开始看到我还以为是我另外一篇关于匿名授权的帖子给了人启发，我更希望是那个帖子。。
gpg 的帖子只是吐槽 gpg 的没啥营养的帖子，没想到却能在某天收到特意的感谢，这种事情只能用“gee 猿巧合”来形容了。补充感谢站长提供的平台让美好的事情发生。 |
 |
15
stardew 171 天前
牛哇
|
 |
16
geelaw OP @lovelylain #11 朴素做法是这样的。不朴素的话，可以用程序混淆（ program obfuscation ）压缩密文，当然要保持逐一破坏的功能，最短可以让密文长度和收件人数无关。
|
 |
17
pwelyn 171 天前
牛
|
 |
18
Sawyerhou 171 天前
恭喜恭喜！
|
 |
19
0312birdzhang 171 天前
看不懂，🐂🍺
|
 |
20
Lyv5 171 天前
说好的大家一起摸鱼你们却在写论文。最后给大佬倒一杯卡布奇诺🐂🍺
|
 |
21
nealHuang 171 天前
|
|
22
nealHuang 171 天前
[img]
 [/img] |
 |
23
sniperboy0829 171 天前 2
这不就是 blockchain 里面的 MPC 吗？早就有现成论文，算法了
|
 |
24
yyancy517 171 天前 2
说好的大家一起摸鱼你们却在写论文。最后给大佬倒一杯卡布奇诺🐂🍺
|
 |
25
zdw189803631 171 天前
摸条鲨鱼出来了，属于是
|
 |
26
cxmokai 171 天前
罗辑你好，我是你的破壁人
|
 |
27
bglucas 171 天前
好家伙, 我以为的摸鱼是摸小鱼. 大佬的摸鱼是摸鲸鱼
|
 |
28
nomagick 171 天前
什么乱七八糟，民科？
攻击者持有两个密钥你怎么办？三个呢？ 每增加一个你的查询复杂度怎样增加？ |
 |
29
RHG 171 天前
罗辑：摸鱼❌写论文✔️这是计划的一部分！🎭
|
 |
30
BeforeTooLate 171 天前
我看到第一个在 V2 做学术的。
|
 |
31
qqjt 171 天前
不是哥们，还能不能好好摸鱼了
|
 |
32
objectxiang 171 天前
 其实和 BitLocker 的加密思路差不多，用户密码和恢复密钥都能解密。 |
 |
33
brant2ai 171 天前
解决内部加密及溯源的问题？
|
 |
34
unii23i 171 天前
翻了一下看不懂
|
 |
35
heywin 171 天前 4
v2 越来越高大上了 我都怀疑方滨兴也在这里摸鱼
|
 |
36
awinds 171 天前
虽然看不懂，但是看起来很🐮🍺
|
 |
37
phub2020 171 天前
不是，哥们，你来真的？我以为大家都是在这里摸鱼的，你怎么？我破防了～
|
 |
38
jhdxr 171 天前
我也想问和 MPC 相比差异在哪？是在于“叛徒追踪”吗？
|
 |
39
wentx 171 天前
这叫摸鱼？
|
 |
40
2exhjx 171 天前
罗辑？是你吗罗教授
|
 |
41
jadehare 171 天前
别人摸鱼摸出一篇论文。我摸鱼...那真的是在摸鱼
|
|
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 171 天前 via iPhone
每个人的摸鱼并不一样..
|
 |
44
wy315700 171 天前 6
 是不是就是这个意思。 谁泄露了钥匙一清二楚。 |
 |
45
Tumblr 171 天前
恭喜大佬！两位大佬可以说是强强联手了！
另外，在大佬的很多回复中学到了不少东西，在此感谢！ |
 |
46
barlogscc 171 天前
大佬你这论文是连着投了两年才被接收吗，太强了
|
 |
48
cheneydog 171 天前
没意思，还是现有的对称加非对称的应用。
而不是新的密码学应用，协同解密、环签名、隐私计算什么的。 |
 |
49
cccb 171 天前
清华大佬摸鱼都是看技术贴的吗，祝贺！
|
 |
50
kaedea 171 天前 via Android
好奇，上世纪欧美那批大佬是不是也是在这样的氛围中取得学术突破的。
|
 |
51
Webpoplayer 171 天前
不是,怎么你的`摸鱼` 跟我认知的摸鱼不一样啊??[/狗头]
|
 |
52
cat9life 171 天前
牛 x 啊，中排祝贺
|
 |
53
chf007 171 天前
最近正好有个业务场景要用到这种加密算法，大佬们看看还有其它方案不
有没有一种算法可以对一份文件加入 n 个用户（可以控制在可控范围内，不是无限多）标识进行加密或签名，然后对加密的文件进行分发，每个用户可下载这同一份加密后的文件，但是只能用自已的标识或密钥之类的来解密，不解密则不能正常查看。解密后的文件能够查看原文且能够判断出就是该用户解密的，该用户解密后的文件再次分发也能判断出是该用户解密的。 |
 |
54
j5159UqX6UKa360u 171 天前 via Android
作为一个菜鸡有一个问题，解密后的文件能不能修改？如果能，如何追踪？
|
 |
55
goforwardv2 171 天前
虽然看不懂，但是祝贺，牛掰
|
|
56
sniperboy0829 171 天前
@geelaw 你说的对，MPC 不是 blockchain “里面的”，MPC 最初我是通过 Blockchain MPC wallet 了解到的，MPC 是 Cryptography 领域的
|
 |
58
dryadent 171 天前
楼主厉害，密码专业前来祝贺
|
 |
59
insignificance 171 天前
追踪方法有用到 零知识证明？
|
 |
60
Stoney 171 天前 via iPhone
清华大佬重新定义摸鱼
|
 |
61
mustcool 171 天前
太强了
|
 |
62
p1gd0g 171 天前 1
听着很像群签名、环签名啊。梦回研究生时代。
能中就好，祝贺。 |
 |
63
qingshengwen 171 天前
群晖的 Sync Cloud 有个加密功能，解密的时候可以选择用密码（字符串），也可以选择用私钥文件
这两种都可以支持，我之前也很好奇这个是怎么实现的，看到 op 这个我觉得有异曲同工之妙 |
 |
64
jocover 171 天前 via iPhone
可以用在 drm 系统上，追查谁泄漏的解密 key ，但是如果很多 key 都能解密，会有人暴力破解
|
 |
65
haiyun81192 171 天前
祝贺楼主，太强了！
|
 |
66
yuruizhe 171 天前
卧槽摸出 paper 来了
|
 |
67
chengandc 171 天前
楼主可以把 LaTex 写的论文托管到 https://scienhub.com 免费 LaTex 论文编译以及托管
|
 |
68
rekulas 171 天前
很 cool 我也喜欢加密学
|
 |
69
zsmj1024 171 天前 via iPhone
恭喜楼主，祝楼主明年大满贯
|
 |
70
justNoBody 170 天前
小弟能力有限，看不懂 op 写的论文。
但是我很好奇是如何追踪是谁破解的？这个破解的解密的过程不是离线的么？离线的情况还可以追踪到是谁解密的么？ 不知道 op 可否再简单描述一下，感谢感谢 |
 |
71
swordspoet 170 天前
@nomagick 不懂的时候，少说，多听，没坏处。
|
 |
72
YsHaNg 170 天前
有没有兴趣做 MPC FHE
|
 |
73
tryrain 170 天前 via Android
Congratulations!!
另外，说民科的先麻烦考上姚班再说吧。 |
 |
74
fxyr123456 170 天前 1
@justNoBody 我以为我大致看懂了皮毛，故而斗胆解释一下。
- 追踪的前提是假定一个解密谕言机来扮演“破解器”的角色，当秘密（比如一篇小说）被盗版网站盗取发布之后，盗版网站就成为了这个谕言机。 - 追踪的原理大致是，我向这个谕言机 query n 段不同公钥加密的密文 ，当且仅当谕言机概率回复正确解密的明文，我们认为谕言机（也即破解器）拥有当前公钥所对应的密钥。 浅薄的理解，不确定对不对，还请指正。 |
 |
75
CRVV 170 天前 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 170 天前
@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 170 天前 via Android
恭喜
|
 |
81
sankooc 170 天前
不明绝历
|
|
82
nomagick 170 天前 1
一个违和的地方，就是一种基于不对称加密的通信机制，在一个攻击者持有了密钥之后，不是单纯对外披露解密后的密文，而是使用私钥本体制作一种解密程序并对外披露
而进行检测的时候，参与方却都能够 100% 7x24 及时有效地参与检测，毫不考虑信道故障 根本的问题是将密码和通信混合起来， 以通信为背景但却不考虑通信的问题 |
 |
83
ZiLong 170 天前
同 V 鱼汝何秀
|
 |
84
DannyVim 170 天前
同样是摸鱼，却摸出了不一样的境界。🧐
|
 |
85
ContentProvider 170 天前
虽然看不懂，但是看起来很牛逼
|
 |
86
814084764 169 天前
我有个实际的需求：如果将密钥安全的存在本地 并且 能离线解密使用？ 有什么现成的方案吗？
|
|
87
814084764 169 天前
如果 --> 如何
|
 |
88
RedSA 169 天前
GeeLaw...基佬。。。
|
 |
89
good1uck 161 天前
这哥们清华的，之前有幸被他回答过一些 Leetcode 问题..
|
Select Language