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

起源是我 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 说一声谢谢！

fxyr123456

181 天前

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

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

CRVV

181 天前

@nomagick
@sniperboy0829
@jhdxr

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

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

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

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

geelaw

181 天前

@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

181 天前

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

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

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

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

CRVV

181 天前

@geelaw #77

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

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

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

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

geelaw

181 天前

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