V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
geelaw
V2EX  ›  分享创造

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

  geelaw ·
GeeLaw · 12 天前 · 12427 次点击

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

90 条回复    2024-07-19 16:55:56 +08:00
wowo243
    1
wowo243  
   12 天前   ❤️ 4
虽然看不懂,但是看起来很🐮🍺
enchilada2020
    2
enchilada2020  
   12 天前 via Android
很强 🐮🍺
yolee599
    3
yolee599  
   12 天前 via Android
研究密码学的都很🐂🍺
xiangchen2011
    4
xiangchen2011  
   12 天前
蛮好的,支持!!
zapper
    5
zapper  
   12 天前
别人摸鱼和我摸鱼的区别
pridealloverme
    6
pridealloverme  
   12 天前
老哥真的很🐂🍺
3M
    7
3M  
   12 天前 via Android
好兄弟,重新定义摸鱼😁
bruce0
    8
bruce0  
   12 天前
别人摸鱼和我摸鱼的区别
luzemin
    9
luzemin  
   12 天前
这**的叫摸鱼?谁家摸鱼能摸出论文?!
microchang
    10
microchang  
   12 天前
真好!祝贺楼主!
lovelylain
    11
lovelylain  
   12 天前 via Android   ❤️ 3
没点开看链接,可以这样实现吧:结果分为两部分,一部分是 aes 等对称加密的密文,另一部分是公钥及公钥加密的对称密钥列表。
1.每个人都生成公私钥,提交公钥;
2.加密的时候随机生成对称密钥并加密内容,再使用公钥列表加密对称密钥;
3.每个人都可以用自己的私钥解密出对称密钥,再解密内容;
4.可以通过逐一破坏密钥列表的方法,破坏后解密不了,没被破坏的能解密,来定位是哪个公钥对应的私钥被泄露。
aks
    12
aks  
   12 天前
作者叫罗辑?
lingeo
    13
lingeo  
   12 天前
理解了,密码学版的黄点追踪,为了做泄露溯源。
sillydaddy
    14
sillydaddy  
   12 天前 via Android   ❤️ 43
我有点受宠若惊,刚开始看到我还以为是我另外一篇关于匿名授权的帖子给了人启发,我更希望是那个帖子。。
gpg 的帖子只是吐槽 gpg 的没啥营养的帖子,没想到却能在某天收到特意的感谢,这种事情只能用“gee 猿巧合”来形容了。补充感谢站长提供的平台让美好的事情发生。
stardew
    15
stardew  
   12 天前
牛哇
geelaw
    16
geelaw  
OP
   12 天前
@lovelylain #11 朴素做法是这样的。不朴素的话,可以用程序混淆( program obfuscation )压缩密文,当然要保持逐一破坏的功能,最短可以让密文长度和收件人数无关。
pwelyn
    17
pwelyn  
   12 天前
Sawyerhou
    18
Sawyerhou  
   12 天前
恭喜恭喜!
0312birdzhang
    19
0312birdzhang  
   12 天前
看不懂,🐂🍺
Lyv5
    20
Lyv5  
   12 天前
说好的大家一起摸鱼你们却在写论文。最后给大佬倒一杯卡布奇诺🐂🍺
nealHuang
    21
nealHuang  
   12 天前
原帖是这个意思吗

https://imgur.com/NS1rf3e
nealHuang
    22
nealHuang  
   12 天前
[img][/img]
sniperboy0829
    23
sniperboy0829  
   12 天前   ❤️ 2
这不就是 blockchain 里面的 MPC 吗?早就有现成论文,算法了
yyancy517
    24
yyancy517  
   12 天前   ❤️ 2
说好的大家一起摸鱼你们却在写论文。最后给大佬倒一杯卡布奇诺🐂🍺
zdw189803631
    25
zdw189803631  
   12 天前
摸条鲨鱼出来了,属于是
cxmokai
    26
cxmokai  
   12 天前
罗辑你好,我是你的破壁人
bglucas
    27
bglucas  
   12 天前
好家伙, 我以为的摸鱼是摸小鱼. 大佬的摸鱼是摸鲸鱼
nomagick
    28
nomagick  
   12 天前
什么乱七八糟,民科?

攻击者持有两个密钥你怎么办?三个呢? 每增加一个你的查询复杂度怎样增加?
RHG
    29
RHG  
   12 天前
罗辑:摸鱼❌写论文✔️这是计划的一部分!🎭
BeforeTooLate
    30
BeforeTooLate  
   12 天前
我看到第一个在 V2 做学术的。
qqjt
    31
qqjt  
   12 天前
不是哥们,还能不能好好摸鱼了
objectxiang
    32
objectxiang  
   12 天前
其实和 BitLocker 的加密思路差不多,用户密码和恢复密钥都能解密。
brant2ai
    33
brant2ai  
   12 天前
解决内部加密及溯源的问题?
unii23i
    34
unii23i  
   12 天前
翻了一下看不懂
heywin
    35
heywin  
   12 天前   ❤️ 4
v2 越来越高大上了 我都怀疑方滨兴也在这里摸鱼
awinds
    36
awinds  
   12 天前
虽然看不懂,但是看起来很🐮🍺
phub2020
    37
phub2020  
   12 天前
不是,哥们,你来真的?我以为大家都是在这里摸鱼的,你怎么?我破防了~
jhdxr
    38
jhdxr  
   12 天前
我也想问和 MPC 相比差异在哪?是在于“叛徒追踪”吗?
wentx
    39
wentx  
   12 天前
这叫摸鱼?
2exhjx
    40
2exhjx  
   12 天前
罗辑?是你吗罗教授
jadehare
    41
jadehare  
   12 天前
别人摸鱼摸出一篇论文。我摸鱼...那真的是在摸鱼
geelaw
    42
geelaw  
OP
   12 天前
@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
    43
Fred0410  
   12 天前 via iPhone
每个人的摸鱼并不一样..
wy315700
    44
wy315700  
   12 天前   ❤️ 6


是不是就是这个意思。

谁泄露了钥匙一清二楚。
Tumblr
    45
Tumblr  
   12 天前
恭喜大佬!两位大佬可以说是强强联手了!

另外,在大佬的很多回复中学到了不少东西,在此感谢!
barlogscc
    46
barlogscc  
   12 天前
大佬你这论文是连着投了两年才被接收吗,太强了
nealHuang
    47
nealHuang  
   12 天前
@geelaw 感觉有点像数字签名
cheneydog
    48
cheneydog  
   12 天前
没意思,还是现有的对称加非对称的应用。
而不是新的密码学应用,协同解密、环签名、隐私计算什么的。
cccb
    49
cccb  
   12 天前
清华大佬摸鱼都是看技术贴的吗,祝贺!
kaedea
    50
kaedea  
   12 天前 via Android
好奇,上世纪欧美那批大佬是不是也是在这样的氛围中取得学术突破的。
Webpoplayer
    51
Webpoplayer  
   12 天前
不是,怎么你的`摸鱼` 跟我认知的摸鱼不一样啊??[/狗头]
cat9life
    52
cat9life  
   12 天前
牛 x 啊,中排祝贺
chf007
    53
chf007  
   12 天前
最近正好有个业务场景要用到这种加密算法,大佬们看看还有其它方案不

有没有一种算法可以对一份文件加入 n 个用户(可以控制在可控范围内,不是无限多)标识进行加密或签名,然后对加密的文件进行分发,每个用户可下载这同一份加密后的文件,但是只能用自已的标识或密钥之类的来解密,不解密则不能正常查看。解密后的文件能够查看原文且能够判断出就是该用户解密的,该用户解密后的文件再次分发也能判断出是该用户解密的。
iamyourking
    54
iamyourking  
   12 天前 via Android
作为一个菜鸡有一个问题,解密后的文件能不能修改?如果能,如何追踪?
goforwardv2
    55
goforwardv2  
   12 天前
虽然看不懂,但是祝贺,牛掰
sniperboy0829
    56
sniperboy0829  
   12 天前
@geelaw 你说的对,MPC 不是 blockchain “里面的”,MPC 最初我是通过 Blockchain MPC wallet 了解到的,MPC 是 Cryptography 领域的
chhtdd
    57
chhtdd  
   12 天前
@nomagick 觉得是民科的话,建议去 Comment
dryadent
    58
dryadent  
   12 天前
楼主厉害,密码专业前来祝贺
insignificance
    59
insignificance  
   12 天前
追踪方法有用到 零知识证明?
Stoney
    60
Stoney  
   12 天前 via iPhone
清华大佬重新定义摸鱼
mustcool
    61
mustcool  
   12 天前
太强了
p1gd0g
    62
p1gd0g  
   12 天前   ❤️ 1
听着很像群签名、环签名啊。梦回研究生时代。
能中就好,祝贺。
qingshengwen
    63
qingshengwen  
   12 天前
群晖的 Sync Cloud 有个加密功能,解密的时候可以选择用密码(字符串),也可以选择用私钥文件
这两种都可以支持,我之前也很好奇这个是怎么实现的,看到 op 这个我觉得有异曲同工之妙
jocover
    64
jocover  
   12 天前 via iPhone
可以用在 drm 系统上,追查谁泄漏的解密 key ,但是如果很多 key 都能解密,会有人暴力破解
haiyun81192
    65
haiyun81192  
   12 天前
祝贺楼主,太强了!
yuruizhe
    66
yuruizhe  
   12 天前
卧槽摸出 paper 来了
chengandc
    67
chengandc  
   12 天前
楼主可以把 LaTex 写的论文托管到 https://scienhub.com 免费 LaTex 论文编译以及托管
rekulas
    68
rekulas  
   12 天前
很 cool 我也喜欢加密学
zsmj1024
    69
zsmj1024  
   11 天前 via iPhone
恭喜楼主,祝楼主明年大满贯
justNoBody
    70
justNoBody  
   11 天前
小弟能力有限,看不懂 op 写的论文。
但是我很好奇是如何追踪是谁破解的?这个破解的解密的过程不是离线的么?离线的情况还可以追踪到是谁解密的么?
不知道 op 可否再简单描述一下,感谢感谢
swordspoet
    71
swordspoet  
   11 天前
@nomagick 不懂的时候,少说,多听,没坏处。
YsHaNg
    72
YsHaNg  
   11 天前
有没有兴趣做 MPC FHE
tryrain
    73
tryrain  
   11 天前 via Android
Congratulations!!
另外,说民科的先麻烦考上姚班再说吧。
fxyr123456
    74
fxyr123456  
   11 天前   ❤️ 1
@justNoBody 我以为我大致看懂了皮毛,故而斗胆解释一下。
- 追踪的前提是假定一个解密谕言机来扮演“破解器”的角色,当秘密(比如一篇小说)被盗版网站盗取发布之后,盗版网站就成为了这个谕言机。
- 追踪的原理大致是,我向这个谕言机 query n 段不同公钥加密的密文 ,当且仅当谕言机概率回复正确解密的明文,我们认为谕言机(也即破解器)拥有当前公钥所对应的密钥。

浅薄的理解,不确定对不对,还请指正。
CRVV
    75
CRVV  
   11 天前   ❤️ 1
@nomagick
@sniperboy0829
@jhdxr

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

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

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



另外,关于环保,为什么不讨论消息变长带来的额外能耗?数据的存储传输都要消耗能量,凭啥这部分就当零来算了?
geelaw
    76
geelaw  
OP
   11 天前
@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
    77
geelaw  
OP
   11 天前
@CRVV #75 环保的考虑里面是计算了存储和传输数据需要的能量的,请注意“总能耗”的“总”字。

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

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

您所谓“科研的玩法”,不可否认科研用作赖以生存的职业会有那种考量,但我的建议是晚一会儿想这个问题是一会儿。
CRVV
    78
CRVV  
   11 天前
@geelaw #77

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

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

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

我给出一个我能想到的最简单的模型,x y 都未知的情况下,Nx+y 和 x+Ny 哪个大?或者说你凭什么认为 x>y 或者 x<y ?
还是说这个“渐近意义”是指把数据加载到内存里面然后把解密跑 N 遍?
geelaw
    79
geelaw  
OP
   11 天前
@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
    80
tcdh  
   11 天前 via Android
恭喜
sankooc
    81
sankooc  
   11 天前
不明绝历
nomagick
    82
nomagick  
   11 天前   ❤️ 1
一个违和的地方,就是一种基于不对称加密的通信机制,在一个攻击者持有了密钥之后,不是单纯对外披露解密后的密文,而是使用私钥本体制作一种解密程序并对外披露
而进行检测的时候,参与方却都能够 100% 7x24 及时有效地参与检测,毫不考虑信道故障

根本的问题是将密码和通信混合起来, 以通信为背景但却不考虑通信的问题
ZiLong
    83
ZiLong  
   11 天前
同 V 鱼汝何秀
DannyVim
    84
DannyVim  
   11 天前
同样是摸鱼,却摸出了不一样的境界。🧐
ContentProvider
    85
ContentProvider  
   11 天前
虽然看不懂,但是看起来很牛逼
814084764
    86
814084764  
   10 天前
我有个实际的需求:如果将密钥安全的存在本地 并且 能离线解密使用? 有什么现成的方案吗?
814084764
    87
814084764  
   10 天前
如果 --> 如何
RedSA
    88
RedSA  
   10 天前
GeeLaw...基佬。。。
good1uck
    89
good1uck  
   2 天前
这哥们清华的,之前有幸被他回答过一些 Leetcode 问题..
good1uck
    90
good1uck  
   2 天前
@good1uck 我指楼主
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2432 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 29ms · UTC 10:21 · PVG 18:21 · LAX 03:21 · JFK 06:21
Developed with CodeLauncher
♥ Do have faith in what you're doing.