安全与密码学2014pages.cs.wisc.edu
如何向孩子解释零知识协议（1998）
How to explain zero-knowledge protocols to your children (1998)
入门 · 约 30 分钟读完前置知识：基础概率、密码学基本概念
导读
这篇 1998 年的经典科普论文用“阿里巴巴洞穴”的童话故事向儿童解释零知识协议：证明者可以说服验证者自己确实知道某个秘密（如洞穴魔法门的口令），却不泄露秘密本身的任何信息。论文借助洞穴、概率等直观元素，演示了零知识证明中模拟、可靠性等核心概念。
HN 关注点：零知识证明是密码学经典概念，HN 读者围绕这篇老牌科普文讨论其实用价值与现代应用，也有人质疑这种讲法是否真的适合儿童。
后来怎么样
零知识证明后来成为现代密码学核心工具，广泛用于区块链（zk-SNARK/zk-Rollup）与可验证计算等领域；这篇阿里巴巴洞穴故事也成为讲解零知识证明的标准入门范例。
HN 评论精选
这几条评论里：质疑 1 补充 2 亲历 1
补充零知识证明极具实用价值（如防键盘记录器的密码验证），可惜尚无能在脑内完成的实用方案。
零知识证明是个极其实用的课题。如果你能让算法相信你知道密码，而不必真的输入它，你就能对键盘记录器等密码泄露手段免疫，也永远不必更换密码。遗憾的是，目前没有任何人能在脑子里完成的实用零知识证明，所以我们至少得把密码输入到本地设备，或者使用第二验证因素。这很可惜，因为理论上并不存在障碍——理论上可以存在简单实用、能在脑内完成的零知识证明，但显然现实中没有。
logicallee查看英文原文
Zero-knowledge proofs are an extremely practical problem. If you could convince an algorithm that you know a password, without having to type it, you would be impervious to keyloggers or any loss of your password - you would never have to change your password, either. Unfortunately, there are no practical zero-knowledge proofs anyone can use in their heads. For this reason we are left typing them at least into the local device we're using - or having to use a second factor. Passwords can't stay in our head. That's a shame, because there's no theoretical reason for this to be so. Theoretically, easy, practical zero-knowledge proofs we can implement in our heads could exist. But apparently they don't.
亲历用 5 张红黑牌就能在现实中演示零知识证明（秘密投票方案）。
我大学的密码学老师 Jacques Patarin 用一个简单的现实版零知识方案向我们介绍零知识证明：只需 5 张牌，3 张相同的红牌和 2 张相同的黑牌。给 Alice 和 Bob 每人一红一黑，自己留下最后一张红牌。Alice 把她的两张牌放在剩下的红牌上面：同意则黑牌在上，反对则红牌在上；Bob 把他的两张牌放在红牌下面：同意则黑牌在最下面，反对则相反。然后充分洗牌混淆谁做了什么，如果两张黑牌相邻（或在牌堆两端），就知道两人都同意了；只要有人反对，黑牌就会被红牌隔开。
littlestymaar查看英文原文
Jacques Patarin[1], my cryptography teacher at university introduced us with zero-knowledge proofs with a simple real-life zero knowledge scheme. All you need is 5 cards, 3 identical red and 2 identical blacks. You give one black and one red to each person (Alice and Bob), and keep the last red. The scheme is the following: Alice will puts her two cards ON TOP of the remaining red card: to say yes, she puts her black card on top of her red card, to say no she does the opposite (red on top of black). Bob will put his pair of cards BELOW the remaining red card, and to say yes he puts his black card at the bottom, with his red card in between, and to say no he does the opposite. Then you cut the deck enough times to obfuscate who've done what, and you know that they've both day yes if you have the two blacks cards next to each other (or both at each ends of the deck). If anyone (or both of them) said no, you'd have black cards separated by one red card. [1] https://fr.wikipedia.org/wiki/Jacques_Patarin
补充零知识证明的现代应用：用简短证明验证虚拟机数十亿步计算的正确性，验证者无需重跑。
我现在在做“执行证明”和“数据可用性证明”，这是零知识证明在超长数值序列上的有趣应用：步骤本身不公开，但步骤必须遵循的规则是公开的。神奇的是，可以证明一台按规范精确运行的虚拟计算机（含 CPU 和内存）在给定输入文件（或其哈希）和程序（或其哈希）的情况下，执行数十亿步后产生了特定的输出文件——而这一切被总结成一段验证者可以快速检查的简短证明，验证者无需重跑计算就能信任输出。
jlokier查看英文原文
These days I'm working on "proof of execution" and "proof of data availability", which are an interesting application of zero-knowledge proofs to very large sequences of values. The steps aren't revealed, but the rule which the steps must follow is revealed. It's almost magical how it's possible to prove that N billion steps of a simulated virtual computer, run exactly according to specification, complete with CPU and memory, given a particular set of input files (or even a hash of an input) and program (or hash of a program), produces a particular set of output files. All summarised in a short proof that a verifier can easily and quickly check, so it doesn't have to redo the computation itself - it can trust the outputs it receives, due to the proof.
质疑质疑这篇“讲给孩子听”的文章后半部分行文清晰度崩塌，术语堆砌并不适合儿童。
如果考虑到目标读者是儿童，我觉得在“嫉妒的记者”一节之前，文章的清晰度就开始崩塌了：引入概率却不解释其意义，“真实性”的概念，一堆莫名其妙的法庭术语，模拟和平行的概念，还有把洞穴塞进高楼大厦里拍摄这种未必最优的设定……甚至中途还丢掉了认证。说实话，我很惊讶 Alice 和 Bob 居然没被塞进这个故事里——还是说那是 Paul 和 Carole？
metaphor查看英文原文
If I try to keep in mind that the target audience is children, then the paragraph just before The Jealous Reporter is where I feel the clarity in prose really starts to fall apart. Introducing the concept of probability without really explaining its significance...or the notion of something being genuine...all this random court mumbo jumbo...simulation and parallel stuff...filming high-rise apartments with caves stuffed in them to achieve something that may not be optimal...even dropped authentication somewhere in there. Really? I'm honestly surprised Alice and Bob didn't somehow find their way into this plot...or was that Paul and Carole.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2014Hacker News 讨论帖56 分 · 13 评
- 2015Hacker News 讨论帖29 分 · 6 评
- 2017Hacker News 讨论帖281 分 · 41 评
- 2022Hacker News 讨论帖163 分 · 59 评
同领域还值得读
如何入侵一台已关机的电脑：在 Intel ME 中运行未签名代码
How to hack a turned-off computer, or running unsigned code in Intel ME
这篇 Black Hat 2017 白皮书讨论 Intel Management Engine（ME）的安全问题：如何在 ME 中运行未签名代码，以及攻破处于关机状态的电脑的相关…
安全与密码学2017 · 543 分 · 107 评专业 · 约 40 分钟编辑精选比特币：一种点对点的电子现金系统（2008）
Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
中本聪 2008 年发表的比特币白皮书，提出了无需可信第三方的点对点电子现金系统。
安全与密码学2017 · 536 分 · 394 评入门 · 约 45 分钟编辑精选GPRS 加密算法 GEA-1 的密码分析表明存在故意弱点
Cryptanalysis of GPRS Encryption Algorithms GEA-1 suggest intentional weakness
首次公开了对 GPRS 加密算法 GEA-1 和 GEA-2 的密码分析攻击。
安全与密码学2021 · 487 分 · 107 评专业 · 约 90 分钟编辑精选Signal 消息协议的形式化安全分析
A Formal Security Analysis of the Signal Messaging Protocol
用形式化方法分析 Signal 消息协议（TextSecure）的安全性：作者在多阶段密钥交换模型下，借助自动化证明工具对协议的密钥协商与 Double Ratchet 密钥更新…
安全与密码学2016 · 353 分 · 230 评专业 · 约 120 分钟编辑精选A2：模拟恶意硬件
A2: Analog Malicious Hardware
论文研究如何在芯片设计阶段植入模拟电路形式的恶意硬件后门，使其难以被常规检测发现。
安全与密码学2016 · 315 分 · 94 评专业 · 约 75 分钟编辑精选