在 V2EX 摸鱼引出的密码学研究，论文终于出版了，感谢一下 @sillydaddy

[geelaw]

起源是我 2022 年 2 月 19 日回顾 @sillydaddy 的帖子 gpg 加密文件：一份加密文件，可以被不同的密码解密，彼时刚刚研究过叛徒追踪问题，于是就结合了一下，想法大概是这样的：

• 一种公钥加密算法，每个人生成自己的密钥对（去中心化）；
• 加密的时候可以给任意一组人加密（使用这些人的公钥）；
• 解密的时候那组人里面的任意一个都可以解密（使用任意一个人的私钥）；
• 如果某些人制造了程序 D 用来解密针对一组人 L 的密文，则可以找出 D 里蕴涵着 L 里哪个人的私钥（“叛徒追踪”），即使不能查看 D 的代码（比如 D 是一个网络 API ）。

想要解决的问题有三个：

1. 怎么定义这个玩意儿？
2. 怎么造这个玩意儿？
3. 能有多好的效率？

这些基础问题在 7 月 15 日完整解决，不过论文出版的问题一直难产（读作：一直被拒稿），直到 2024 年 6 月 3 日才被 IACR 最近新推出的期刊 Communications in Cryptology （密码学通讯）接受，并在 7 月 8 日出版。

本研究带来了我首篇单作者论文，并且得以实践一些我的新想法：

力求“思维透明”，以飨他人，论文的修订过程可以在 GitHub 仓库 GeeLaw/ahbtr 查看。

---

关于原帖比较有趣的 take-home message 是：

最朴素的实现也是最环保的实现。

虽然运用密码学技巧，可以让密文比收件人列表还要短，但每个收件人解密都要付出额外的代价，总能耗（在渐近意义下）相比朴素算法会增加——而且这并不是因为人类很笨（不知道怎么做得更好），而是可以（无条件）证明安全的加密算法必然有此性质（不可能做得更好）。

---

那么，最后再向 @sillydaddy 说一声谢谢！

[wowo243]

虽然看不懂，但是看起来很🐮🍺

[enchilada2020]

很强 🐮🍺

[yolee599]

研究密码学的都很🐂🍺

[xiangchen2011]

蛮好的，支持！！

[zapper]

别人摸鱼和我摸鱼的区别

[pridealloverme]

老哥真的很🐂🍺

[3M]

好兄弟，重新定义摸鱼😁

[bruce0]

别人摸鱼和我摸鱼的区别

[luzemin]

这**的叫摸鱼？谁家摸鱼能摸出论文？！

[microchang]

真好！祝贺楼主！

[lovelylain]

没点开看链接，可以这样实现吧：结果分为两部分，一部分是 aes 等对称加密的密文，另一部分是公钥及公钥加密的对称密钥列表。
1.每个人都生成公私钥，提交公钥；
2.加密的时候随机生成对称密钥并加密内容，再使用公钥列表加密对称密钥；
3.每个人都可以用自己的私钥解密出对称密钥，再解密内容；
4.可以通过逐一破坏密钥列表的方法，破坏后解密不了，没被破坏的能解密，来定位是哪个公钥对应的私钥被泄露。

[aks]

作者叫罗辑？

[lingeo]

理解了，密码学版的黄点追踪，为了做泄露溯源。

[sillydaddy]

我有点受宠若惊，刚开始看到我还以为是我另外一篇关于匿名授权的帖子给了人启发，我更希望是那个帖子。。
gpg 的帖子只是吐槽 gpg 的没啥营养的帖子，没想到却能在某天收到特意的感谢，这种事情只能用“gee 猿巧合”来形容了。补充感谢站长提供的平台让美好的事情发生。

[stardew]

牛哇

[geelaw]

@lovelylain #11 朴素做法是这样的。不朴素的话，可以用程序混淆（ program obfuscation ）压缩密文，当然要保持逐一破坏的功能，最短可以让密文长度和收件人数无关。

[pwelyn]

牛

[Sawyerhou]

恭喜恭喜！

[0312birdzhang]

看不懂，🐂🍺

[Lyv5]

说好的大家一起摸鱼你们却在写论文。最后给大佬倒一杯卡布奇诺🐂🍺

[nealHuang]

原帖是这个意思吗

https://imgur.com/NS1rf3e

[nealHuang]

[img][/img]

[sniperboy0829]

这不就是 blockchain 里面的 MPC 吗？早就有现成论文，算法了

[yyancy517]

说好的大家一起摸鱼你们却在写论文。最后给大佬倒一杯卡布奇诺🐂🍺

[yusf]

摸条鲨鱼出来了，属于是

[cxmokai]

罗辑你好，我是你的破壁人

[bglucas]

好家伙, 我以为的摸鱼是摸小鱼. 大佬的摸鱼是摸鲸鱼

[nomagick]

什么乱七八糟，民科？

攻击者持有两个密钥你怎么办？三个呢？ 每增加一个你的查询复杂度怎样增加？

[RHG]

罗辑：摸鱼❌写论文✔️这是计划的一部分！🎭

[BeforeTooLate]

我看到第一个在 V2 做学术的。

[qqjt]

不是哥们，还能不能好好摸鱼了

[objectxiang]

其实和 BitLocker 的加密思路差不多，用户密码和恢复密钥都能解密。

[brant2ai]

解决内部加密及溯源的问题？

[unii23i]

翻了一下看不懂

[heywin]

v2 越来越高大上了 我都怀疑方滨兴也在这里摸鱼

[awinds]

虽然看不懂，但是看起来很🐮🍺

[phub2020]

不是，哥们，你来真的？我以为大家都是在这里摸鱼的，你怎么？我破防了～

[jhdxr]

我也想问和 MPC 相比差异在哪？是在于“叛徒追踪”吗？

[wentx]

这叫摸鱼？

[2exhjx]

罗辑？是你吗罗教授

[jadehare]

别人摸鱼摸出一篇论文。我摸鱼...那真的是在摸鱼

[geelaw]

@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 ）不好。

[Fred0410]

每个人的摸鱼并不一样..

[wy315700]

是不是就是这个意思。

谁泄露了钥匙一清二楚。

[Tumblr]

恭喜大佬！两位大佬可以说是强强联手了！

另外，在大佬的很多回复中学到了不少东西，在此感谢！

[barlogscc]

大佬你这论文是连着投了两年才被接收吗，太强了

[nealHuang]

@geelaw 感觉有点像数字签名

[cheneydog]

没意思，还是现有的对称加非对称的应用。
而不是新的密码学应用，协同解密、环签名、隐私计算什么的。

[cccb]

清华大佬摸鱼都是看技术贴的吗，祝贺！

[kaedea]

好奇，上世纪欧美那批大佬是不是也是在这样的氛围中取得学术突破的。

[Webpoplayer]

不是,怎么你的`摸鱼` 跟我认知的摸鱼不一样啊??[/狗头]

[cat9life]

牛 x 啊，中排祝贺

[chf007]

最近正好有个业务场景要用到这种加密算法，大佬们看看还有其它方案不

有没有一种算法可以对一份文件加入 n 个用户（可以控制在可控范围内，不是无限多）标识进行加密或签名，然后对加密的文件进行分发，每个用户可下载这同一份加密后的文件，但是只能用自已的标识或密钥之类的来解密，不解密则不能正常查看。解密后的文件能够查看原文且能够判断出就是该用户解密的，该用户解密后的文件再次分发也能判断出是该用户解密的。

[j5159UqX6UKa360u]

作为一个菜鸡有一个问题，解密后的文件能不能修改？如果能，如何追踪？

[goforwardv2]

虽然看不懂，但是祝贺，牛掰

[sniperboy0829]

@geelaw 你说的对，MPC 不是 blockchain “里面的”，MPC 最初我是通过 Blockchain MPC wallet 了解到的，MPC 是 Cryptography 领域的

[chhtdd]

@nomagick 觉得是民科的话，建议去 Comment

[dryadent]

楼主厉害，密码专业前来祝贺

[insignificance]

追踪方法有用到 零知识证明？

[Stoney]

清华大佬重新定义摸鱼

[mustcool]

太强了

[p1gd0g]

听着很像群签名、环签名啊。梦回研究生时代。
能中就好，祝贺。

[qingshengwen]

群晖的 Sync Cloud 有个加密功能，解密的时候可以选择用密码（字符串），也可以选择用私钥文件
这两种都可以支持，我之前也很好奇这个是怎么实现的，看到 op 这个我觉得有异曲同工之妙

[jocover]

可以用在 drm 系统上，追查谁泄漏的解密 key ，但是如果很多 key 都能解密，会有人暴力破解

[haiyun81192]

祝贺楼主，太强了！

[yuruizhe]

卧槽摸出 paper 来了

[chengandc]

楼主可以把 LaTex 写的论文托管到 https://scienhub.com 免费 LaTex 论文编译以及托管

[rekulas]

很 cool 我也喜欢加密学

[zsmj1024]

恭喜楼主，祝楼主明年大满贯

[justNoBody]

小弟能力有限，看不懂 op 写的论文。
但是我很好奇是如何追踪是谁破解的？这个破解的解密的过程不是离线的么？离线的情况还可以追踪到是谁解密的么？
不知道 op 可否再简单描述一下，感谢感谢

[swordspoet]

@nomagick 不懂的时候，少说，多听，没坏处。

[YsHaNg]

有没有兴趣做 MPC FHE

[tryrain]

Congratulations!!
另外，说民科的先麻烦考上姚班再说吧。

[fxyr123456]

@justNoBody 我以为我大致看懂了皮毛，故而斗胆解释一下。
- 追踪的前提是假定一个解密谕言机来扮演“破解器”的角色，当秘密（比如一篇小说）被盗版网站盗取发布之后，盗版网站就成为了这个谕言机。
- 追踪的原理大致是，我向这个谕言机 query n 段不同公钥加密的密文 ，当且仅当谕言机概率回复正确解密的明文，我们认为谕言机（也即破解器）拥有当前公钥所对应的密钥。

浅薄的理解，不确定对不对，还请指正。

[CRVV]

@nomagick
@sniperboy0829
@jhdxr

11 楼 lovelylain 的回复已经给出了详细的方案，楼主也认可了他说的内容。
有人 “没点开看链接” 就直接给出了答案，所以，这论文真没多少干货。
核心内容只有不到 10 行的汉字，楼主写了三十多页的论文。

虽然这么说，这个论文也不是全无新意，要获得 “密文长度和收件人数无关” 这个性质，还是需要折腾一些花样进去。
我相信楼主说的 “该问题是新的”，而且这个问题显然和 MPC 没关系，MPC 是比这个复杂多了。

而且确实不民科，这个论文是一个典型的正经科研的玩法。把一些实际上没啥意思的东西套上各种高级的词汇，当然也确实包含了一点点的新东西，写一遍超长的 “论文”，发表在一个没人听说过的期刊上，然后得到 毕业证/学位证/职称 之类的东西。确实是很正经的科研，只不过不是我做事的风格，我更喜欢看到一遍半页的小文章来讲解这个花样。
而且能写出这么长的论文也是高级能力，这东西给我就只能写出来半页的内容，所以我早就不玩这些 “科研” 的东西了。



另外，关于环保，为什么不讨论消息变长带来的额外能耗？数据的存储传输都要消耗能量，凭啥这部分就当零来算了？

[geelaw]

@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 里哪个人的私钥。

[geelaw]

@CRVV #75 环保的考虑里面是计算了存储和传输数据需要的能量的，请注意“总能耗”的“总”字。

>要获得 “密文长度和收件人数无关” 这个性质，还是需要折腾一些花样进去。

获得这个性质所需要的技巧，我称之为“繁琐但常规的体操”。从技巧评判，这篇文章比较有趣的是环保问题，毕竟证明不可能性比证明可能性困难一些。至于问题本身是否有趣，每个人有不同的想法很正常。

您所谓“科研的玩法”，不可否认科研用作赖以生存的职业会有那种考量，但我的建议是晚一会儿想这个问题是一会儿。

[CRVV]

@geelaw #77

根据 c24-ver1.pdf 第 25 页的内容，两个方案，一个有 Ω(N) 的时间复杂度和常数的空间复杂度，另一个有 Ω(N) 的空间复杂度和常数的时间复杂度，你能得到了结论说

> 总能耗（在渐近意义下）相比朴素算法会增加

你自己觉得这个结论能成立么？

我给出一个我能想到的最简单的模型，x y 都未知的情况下，Nx+y 和 x+Ny 哪个大？或者说你凭什么认为 x>y 或者 x<y ？
还是说这个“渐近意义”是指把数据加载到内存里面然后把解密跑 N 遍？

[geelaw]

@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) 的下载、解密所吸收。

[tcdh]

恭喜

[sankooc]

不明绝历

[nomagick]

一个违和的地方，就是一种基于不对称加密的通信机制，在一个攻击者持有了密钥之后，不是单纯对外披露解密后的密文，而是使用私钥本体制作一种解密程序并对外披露
而进行检测的时候，参与方却都能够 100% 7x24 及时有效地参与检测，毫不考虑信道故障

根本的问题是将密码和通信混合起来， 以通信为背景但却不考虑通信的问题

[ZiLong]

同 V 鱼汝何秀

[DannyVim]

同样是摸鱼，却摸出了不一样的境界。🧐

[ContentProvider]

虽然看不懂，但是看起来很牛逼

[814084764]

我有个实际的需求：如果将密钥安全的存在本地 并且 能离线解密使用？ 有什么现成的方案吗？

[814084764]

如果 --> 如何

[RedSA]

GeeLaw...基佬。。。

[good1uck]

这哥们清华的，之前有幸被他回答过一些 Leetcode 问题..

[good1uck]

@good1uck 我指楼主