在 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 说一声谢谢！

geelaw

180 天前

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

chf007

180 天前

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

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