如何阅读（密码学）研究论文

简介

我学到的最有价值的技能之一并非密码学特有，而仅仅是如何阅读研究论文。 一旦你掌握了这项技能，你自学的能力将大大提高，并且你可以跟上任何子领域的最新进展。 （我将 IACR 的 ePrint Archive 列在我的 入门 页面上是有原因的。） 在工作中，有很多次团队来找我说“这是什么意思？”，然后递给我一篇密集的论文让我研究。 能够理解它们是一种天赐之物。

不幸的是，阅读研究论文可能非常困难，并且与阅读大多数其他内容所需的技能不同。 （例如，你不是从头开始读到结尾。） 这意味着很多人（像我一样）会尝试阅读一些，然后在发现根本不明白时迅速放弃。 本页旨在帮助人们避免我不得不面对的挫折感。

本指南_并非_针对那些真正在学术界的人。 虽然它可能对你有用，但请与你的导师或同事交谈，而不是听从那些学术背景有限的人的随意漫谈。 你的需求和目标会有所不同，因此你阅读论文的方式也会有所不同。

此处的指导分为两部分。 第一部分应适用于（几乎）所有研究论文，无论领域如何。 第二部分专门针对密码学。

阅读研究论文

在阅读研究论文之前，你需要知道你阅读它的_目标_是什么。

• 你是想更多地了解这个通用领域吗？
• 你是在试图弄清楚这篇论文对你是否重要吗？
• 你是在试图学习这篇论文的具体结果吗？
• 你是在试图理解和评估导致该结果的工作吗？
• ...

每个目标都需要不同的重点和方法。 下面列出的策略对每个目标都相当有效，但你需要根据你的具体需求自定义它们。 你要记下什么笔记？你要跳过什么？

通用策略

研究论文通常按顺序包含以下部分：

1. 标题
2. 摘要
3. 简介
4. （可选）背景
5. 论文的正文
6. 结论
7. 参考文献/引文

对于我们这些习惯于阅读“正常”事物的人来说，我们本能地想要按顺序尝试这样做。 但这效果不好。 相反，最好按以下顺序阅读它们。

阅读时，请务必做笔记，保存你以后想阅读的参考文献（或者可能是首先阅读，如果它们有重要的前提条件的话），等等。

另一个需要考虑的事情是，许多论文都曾在会议上发表过。 查看会议的网站或 YouTube，看看你是否能找到作者解释它的录音。 有时这更容易。

1. 标题

这里真的没什么好说的。 你需要知道你在读什么。

2. 摘要

这将让你了解论文的结构，并让你知道它是否值得你花时间。 如果论文不相关，太超出你的能力范围，或者只是写得很糟糕，有时在这里放弃是值得的。

3. 简介

这就像摘要，但内容更丰富。 你的目标是Roughly了解论文在说什么以及它是如何实现的。 应该明确地提出一个问题陈述，并且希望你能相信论文可能实际上解决了这个问题。

需要注意的一些具体事项：

• 不切实际的说法（你可能不是专家，但你应该已经能够发现一些胡说八道）
• 解决方案与问题不符（这是经典的“当你的工具只有锤子时，一切看起来都像钉子”，只不过这里的锤子是作者喜欢的任何密码学工具。而且，人们通常会为了更简单的技术论文而忽略现实世界的复杂性。根据论文的不同，这可能还可以。）
• 声明中是否有含糊其辞的词语？（也许结果真的很有趣，但只在你不在意的非常特定的情况下，或者作者想要把事情说得比实际更令人印象深刻。）

这是你的第一个真正的好停止点。 到现在你应该知道这篇论文是否值得你花时间了。 你甚至可能有一些其他（更有趣或更有用）的参考文献需要去追寻。

4. 背景

本节是可选的。 如果你已经很了解主题，直接跳过它。

但是，如果你不了解，这可能是论文中最有价值的部分。 在这里你将学习这篇论文在谈论什么，并开始了解上下文。 如果论文写得好，你将真正能够建立你的知识，并收集一个好的参考文献列表以供进一步阅读。 （也许你会意识到这篇论文现在超出了你的能力范围，但你可以阅读其他一些论文。）

在很多方面，我仍然认为自己是一个初学者，所以“背景”仍然是我最喜欢的一篇写得好的论文的部分。

5. 参考文献

本节是可选的。

如果背景有用，你应该浏览参考文献，看看接下来（或首先）要读什么。 如果你不需要背景，那么你就足够了解这些参考文献是否有帮助了。

6. 结论

是时候跳到结尾了！

论文的结论是什么？它们有意义吗？（它们有趣吗？）

在许多情况下，论文的结论是它存在的全部原因。 这就是论文被撰写和发表的原因。

这是你的下一个真正的好停止点。

也许你只关心结论。

• “算法 FOO 被破坏了！” 好的，我们不要使用它。
• “算法 BAR 可用于执行 BAZ。” 嗯，我不执行 BAZ，所以我不关心。
• 等等。

我的一个常见工作是查看研究论文，并弄清楚我们是否关心它们。 我们需要更改我们的代码或与安全团队争论以防御新的攻击吗？ 通常，一旦我阅读了结论，我就知道足够多来对论文进行分类，并弄清楚它们是否值得我们花时间，我可能永远不需要细节。

7. 正文

最后我们到达了论文的正文。 （或者也许我们没有到达它，因为你在到达这里之前就停止了。这也没关系。）

重要的是要理解，现在你的目标不是阅读正文，而是浏览它。 了解他们在说什么以及他们是如何工作的。 不要担心证明或任何详细的数据集。 现在，你只想了解整体论点，并且只是相信作者可以支持他们的论点。 你不是在试图检查他们的工作。

这是另一个好的停止点。

事实上，这是我最常见的停止点。 我还没有足够的能力（还）来理解，更不用说检查我阅读的论文中的详细安全证明了。 大多数非对称算法的数学都远远超出了我的能力范围。 因此，与这些细节作斗争不值得我花时间。

8. 正文（详细阅读）

现在是你重新阅读正文的时候了，包括所有详细的证明和数据，目的是为了理解他们究竟做了什么，如何做的，并在有错误的情况下抓住它们。 你知道论文的结构和他们的论点，所以你可以看到一切是如何组合在一起的。 当提出一个证明时，你可以看到它是如何支持后面的部分的。

恭喜，你完成了。

阅读密码学论文的技巧

密码学很难，并且像许多科学一样，有它自己的词汇表。 很多概念都有详细和极其精确的定义，但是，如果你正在使用本指南，则它们很少重要。 相反，你需要的是一种直觉。 大多数时候，你所需要的只是一种粗略的心理近似，并且熟悉一些标准的符号和术语，就可以浏览许多论文。

所以，这里有我极其非正式的（并且可能不准确的）密码学事物心理模型。

• 密码学假设：大多数情况下，我们并不声称一种算法仅仅是“安全的”，而是说它相对于某些假设是安全的。
  • 最常见的假设是，它在计算上（或语义上）相对于某个安全参数是安全的。这仅仅意味着你可以在大致与 \(2^\lambda\)（2 的安全参数次方）成正比的时间内暴力破解该算法。另一个假设可能是 离散对数很难。
  • 一些算法在 信息理论上是安全的，这意味着它们确实是“安全的”。无论攻击者的力量如何，都没有办法暴力破解或破解它们。虽然有趣，但这些算法在现实世界中很少有用。（是的，我知道 Shamir 的秘密共享 在现实世界中使用，但大多数人不会也不应该接触它。）
  • 很多（大多数？）论文使用安全归约。如果他们证明了从 Foo 到 Bar 的安全归约，那么这意味着（通常以多项式近似为条件），Foo 与 Bar 一样安全（并且暗示对 Foo 的任何攻击也可以用来攻击 Bar）。当我们对 Bar 的安全性非常有信心时，这很好。（它也将用于理论上完美的构造。因此，证明可能是相对于一个随机函数的，其归约意味着当你代入一个 PRF 时，你的构造将与该 PRF 是一个真实的随机函数的一个好的近似一样安全。）
• 模型：模型是密码学家假设一些可能不真实但通常足够接近真实（并且对证明有用）的事情的一种方式。它们可以是我们的 球形奶牛 版本。
  • 随机预言机模型：我们可以假设我们可以访问 随机预言机（RO）。对于密码学证明来说，这非常奇怪和关键，但你可以把它想象成一个“完美”的密码学哈希函数（可能具有可变长度的输出）。由于这无论如何都是一个想象中的构造，因此有无数个不同的 RO，它们以不同的方式将其输入映射到输出。通常，你不在乎你拥有哪一个，只要你有一个。（这也意味着论文可能会在同一论文中出于不同的目的使用多个 RO。）在安全证明中，挑战者和对手都可以查询它，并且对手有能力预先编程它的响应。
  • 通用参考字符串模型：每个人都可以知道一些通用的字符串。这解决了确保每个人都可以访问一些公共（受信任）值的问题。
  • 代数群模型：对手输出的群元素只能通过乘以和反转对手的输入群元素来派生。
• 随机函数：它就像一个随机预言机（但不要问我有什么区别）。想象一下，你有一组从一组输入到一组输出的所有可能的函数。然后，你完全随机地（均匀分布）选择其中一个。
• 随机置换：与随机函数相同，但输入和输出集相同，并且它们之间存在一对一的映射。
• PRF：一个 伪随机函数。基本上是一个假的随机预言机。在第一次心理近似中，不要担心差异。（它们通常采用一个密钥，这使得它们可以模拟不同的 RO。）
• PRP：一个 伪随机置换。就像 PRF 一样，除了输入和输出空间相同，并且它定义了一个置换。把它想象成一个“完美”的块密码。（就像 PRF 一样，它们通常采用密钥。）
• \(\xleftarrow{\$}\)（一个左指向的箭头，上面有一个美元符号）表示从一个集合中随机选择一个元素。除非另有说明，否则所有元素被选中的可能性相等。这通常用于选择 nonce 或密钥。
• 游戏：游戏是挑战者和对手之间允许的一系列动作。大多数安全定义都是通过描述一个游戏并说，如果没有 PPT 对手能够以超过可以忽略不计的概率赢得游戏，那么某事物就是安全的。
  • “对手”是一些有限的（通常是正常的概率多项式时间）算法，它们试图破坏一个算法。（概率多项式时间仅仅意味着它可以相对快速地运行并且可以访问随机位。）
  • “挑战者”通常使用一个算法（被证明具有某些属性）和随机位来在游戏的上下文中对对手提出某种挑战。例如，“这个字符串是通过使用随机密钥加密你给我的数据的结果，还是它只是完全随机的数据？”
• 证明的安全参数通常表示为 \(\lambda\)，并且是许多 1。 （因此，AES-128 的安全参数可能表示为 \(1^{128}\) 或 128 个 1 的字符串。）为什么？因为说“输入大小的多项式”（这对于 大 O 表示法 是正常的）比说“安全参数的多项式时间”（这将是不同的并且对我们来说是特殊的）更容易。
• 可忽略的概率：基本上，随着值（通常是安全参数）变得足够大，某些事情发生的概率变得很小，你可以（几乎）忽略它。如果对于任何多项式 \(p(n)\)，对于所有足够大的 \(n\)，\(|f(n)| \< 1/p(n)\)，则函数 \(f(n)\) 是可以忽略的。你可以将可忽略的函数视为以反指数的速度变得非常小。
• 同行评审：在会议或期刊上发表的论文已经过同行评审。你应该将此视为对论文提出的声明及其沟通质量的高级别检查。重要的是，这并不意味着结果是正确的，只是它们很有趣并且没有明显的错误。（任何人都可以将论文发布在 ePrint 上，因此你不能假设它们已经过任何类型的审查。）
• 证明：许多论文将包括特定定理的证明或证明草图。包含的详细程度因作者和地点而异。符号中的错误或遗漏很常见，因此如果一个步骤似乎缺少并且需要由读者填写，请不要太惊讶。
• （是的，我知道我遗漏了很多东西，请告诉我什么）

最后，我还听说 Boneh 和 Shoup 的 应用密码学研究生课程 是一本优秀的（免费）参考书，并且是参与研究论文的一个很好的垫脚石。我还没有读过它，但它现在在我个人清单上排名很高。

• 原文链接： github.com/SalusaSecondu...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～