【概述】

密码学（Cryptography）一直与设计和分析加密方案的问题相关，即通过不安全通信媒介提供秘密通信的方案。自 20 世纪 70 年代以来，诸如构建不可伪造的数字签名、设计容错协议等问题也被视为密码学范畴。事实上，密码学可被视为一门研究如何设计任何需要抵御恶意滥用企图的系统的学科

单向函数（One-way Function）是在密码学中具重要意义的函数，其是一个单射函数，对于每一个输入 $x$，可以在多项式时间内计算出函数值 $f(x)$，但是给定一个函数值 $y$，要找到一个输入 $x$ 使得 $f(x)=y$ 在计算上是困难的

单向函数的定义刻画了整个密码学方法中内在的计算困难性（Computational Difficultly），因此密码学的许多内容均建立在“单向函数是存在的”这一假设之上。这种方法试图利用攻击者的计算能力有限这一事实，从而构造能够抵御恶意攻击的密码系统

因此，如果不仅存在困难问题，而且这些困难问题的实例还可以被高效生成，那么这些困难问题就可以被有效利用

【加密方案】

基本模型

在不安全媒介上实现秘密通信，是密码学中最传统、最基本的问题。这个问题的基本场景包括两个通信方，他们通过一个可能被窃听的信道进行通信，通信双方希望彼此交换信息，同时尽可能使窃听者无法了解这些信息的内容。窃听信道的窃听者常被称为敌手（Adversary）

简单来说，加密方案是一种允许通信双方秘密通信的协议。通常，一个加密方案由一对算法组成，其中一个算法是由发送方使用的加密算法（Encryption Algorithm），另一个算法是由接收方使用的解密算法（Decryption Algorithm）

因此，为了发送一条消息，发送方首先将加密算法应用于该消息，并将结果通过信道发送出去；接收方在收到密文后，将解密算法应用于该密文，从而恢复出原始消息。消息加密得到的结果称为密文（Ciphertext），密文解密后得到的原始消息称为明文（Plaintext）

为使该方案提供秘密通信，通信双方或接收方必须知道窃听者某些不知道的消息，否则窃听者就可以像接收方一样解密密文。这些额外知识被称为解密秘钥（Decryption Key），可能表现为解密算法本身，或者是解密算法所使用的某些参数、辅助输入

为不失一般性，通常假设窃听者知道解密算法，且解密算法需要一个密文和一个解密秘钥作为输入，但窃听者不知道解密秘钥的具体内容

安全观念

安全观念主要有两种：基于信息论的传统观念、基于计算复杂性的现代观念

基于信息论的传统观念：关注的是密文中是否包含关于明文的信息。如果密文中包含关于明文的信息，那么该加密方案就是不安全的
基于计算复杂度的现代观念：不关心密文中是否包含关于明文的信息，而是关注这些信息能否被高效提取出来。即不再询问窃听者是否有可能提取出某些特定信息，而是询问窃听者提取这些信息在计算上是否可行

传统观念认为，只有当秘钥长度至少等于通过加密方案发送的消息总长度一样长时，才可能实现较高的安全性。但这种秘钥比使用它交互的信息还要长的方案，极大的限制了这类加密方案的适用性；而对于现代观念，即使秘钥远短于加密方案发送的消息总长度时，也能够提供安全性

加密方案

基于计算复杂性的现代安全观念，不仅改变了对加密方案安全性的定义，也允许引入一些在信息论方法下无法存在的概念和密码学原语，一个典型的例子就是公钥加密

在前面的讨论中，主要关注的是解密算法及其使用的解密秘钥，但实际上，加密算法除了消息本身作为输入外，还需要一个依赖于解密秘钥的辅助输入，即加密秘钥（Encryption Key）

根据加密秘钥与解密秘钥之间的关系，可以区分两类加密方案：

私钥加密（Private-key Encryption）：加密秘钥等于解密秘钥，即同一个秘钥既用于加密，也用于解密。窃听者必须不知道加密秘钥，否则方案的安全性会受到破坏
公钥加密（Public-key Encryption）：解密秘钥不同于加密秘钥，且从加密秘钥计算出解密秘钥在计算上是不可行的。加密秘钥可以被窃听者知道，但不会破坏加密方案的安全性

传统加密方案会带来秘钥密钥分发问题（Key-distribution Problem），即两个希望通过不安全信道通信的参与方，如何协商出一个秘密的加密/解密密钥。而公钥加密方案可以公开发布加密秘钥，因此密钥分发问题可以被直接解决

【伪随机生成器】

伪随机生成器（Pseudorandom Generators）在加密方案以及相关密码学方案的构造中具有核心作用，特别是其能给出私钥加密方案的简单构造

虽然伪随机生成器这一术语被广泛使用，但其很少被赋予精确的含义。简单来说，伪随机生成器是一种确定性算法，其将较短的随机种子（Random Seeds）扩展为更长的比特序列，这些比特序列看起来是随机的，但实际上并非真正随机

换言之，伪随机生成器的输出并不是真正的随机序列，但很难在计算上区分它与真正随机序列之间的差别。因此，伪随机性的关键不在于输出本身是否真正随机，而在于是否能够高效地区分其输出与真正随机输出

伪随机生成器可基于多种不可处理假设来构造，因此其与计算困难性之间有更根本的联系

此外，伪随机生成器与单向函数间存在十分紧密的关系，即：伪随机生成器存在，当且仅当单向函数存在

【数字签名】

基本概念

在过去几个世纪中，人们曾讨论过不可伪造签名（Unforgeable Signatures），但当时讨论的对象是手写签名，因此并没有将其视为与密码学相关。但随着计算机通信在商业环境中的引入，参与方往往需要对其提出的建议或作出的声明进行承诺，数字签名（Digital Signature）的需求便产生了

随着加密方法与签名方法都被数字化，并且基于计算复杂性的安全方法被引入，加密方法与签名方法之间的联系成为可能。简单来说，一个不可伪造签名方案需要满足以下三个要求：

每个用户都能高效地在自己选择的文档上生成自己的签名
每个用户都能高效地验证某个给定的字符串，是否是另一个特定用户在某个特定文档上的签名
没有人能够高效地为其他用户没有签名过的文档，生成这些用户的签名

不可伪造签名方案的要求，也清楚说明了手写签名的基本要素，这些要素包括：

每个人都能为自己签名
存在一个被普遍认可的验证过程
人们相信能够通过验证过程的方式伪造签名是不可行的（至少是困难的）

很难说明手写签名在多大程度上满足这些基本要求，但数字签名可以提供精确表述，以说明数字签名在多大程度上满足上述要求

此外，不可伪造数字签名方案可以使用与构造私钥加密方案相同的计算假设来构造

消息认证

消息认证（Message Authentication）是一个与加密方案所考虑的场景相关的任务，即在不安全信道中进行通信，但消息认证考虑的是一种更主动的敌手情形。

假设信道上存在一个主动敌手（Active Adversary），这个敌手不仅会监听信道，还可能修改信道上传输的消息。因此，通过不安全信道通信的双方希望对他们发送的消息进行认证，使得预期接收方能够区分一条消息到底是发送方发送的原始消息，还是被敌手篡改过的消息

简单来说，一个消息认证方案需满足以下要求：

每个通信方都能高效地为自己选择的任意消息生成一个认证标签（Authentication Tag）
每个通信方都能高效地验证某个给定字符串是否是某条给定消息的认证标签
对于通信双方外的任意第三方，都不能高效地为通信双方没有发送过的消息生成认证标签

因此，消息认证的核心目标不是隐藏消息内容，而是保证接收方能够判断消息是否是发送方原本的消息，即消息认证关注的是消息在传输过程中是否被敌手篡改

从某种意义上来说，消息认证类似于数字签名，二者都涉及对某个消息或文档生成某种可验证的字符串，并通过验证过程判断其有效性，二者的区别在于验证者的范围不同：

消息认证：不要求第三方能够验证指定用户生成的认证标签是否有效
数字签名：要求第三方能够验证其他用户生成的签名是否有效

由于数字签名允许验证某个消息是否由特定用户签署，因此，数字签名可以为消息认证提供一种解决方案，从而帮助判断消息是否被伪造或篡改

但是，消息认证不要求第三方具备验证认证标签有效性的能力，因此消息认证方案不一定构成数字签名方案

密码学范围的扩展

将数字签名问题看作密码学的一部分，会扩展密码学的研究范围。此时，密码学不再只关注传统的秘密通信问题，而是进一步关注一类更广泛的问题：如何限制系统中不诚实行为所能带来的收益

这里的不诚实放既可能是系统外部的参与方，也可能是系统内部的参与方。因此，从更广泛的意义上来看，密码学不仅研究如何隐藏通信内容，也研究如何限制不诚实用户对系统造成的影响

具体来说，可以从以下三个问题理解密码学范围的扩展：

秘密通信问题：通过使用加密方案来解决，其目标是尽可能减少潜在窃听者能够从两个指定用户之间通信中提取到的消息
消息认证问题：阻止任何外部窃听者修改两个指定用户之间的通信，即不关注的不是信息隐藏，而是防止通信内容在传输过程中被外部敌手篡改
数字签名问题：为系统中的所有用户提供一种方式，使他们能够作出对自己具约束力的声明，同时确保一个用户不会作出约束另一个用户的声明

因此，从广义上来说，密码学关注的是任何希望限制不诚实用户影响的问题，即只要某个问题的核心目标是限制不诚实行为所能造成的收益，就可以被纳入广义密码学的讨论范围

【容错协议】

容错协议与协议问题

一旦考虑数字签名，自然就会产生一个问题：在什么情况下，一方应该向另一方提供自己的签名？

这类问题通常通过容错协议（Fault-tolerant Protocols），也可称为密码协议（Cryptographic Protocols）来处理。此时，主要会引出两类协议问题：

同时性问题（Simultaneity Problems）：如何保证多个参与方在协议执行中获得某种同步的结果？
函数的安全实现（Secure Implementation of Functionalities）：如何在不完全信任参与方的情况下，安全地计算由多个用户共同输入决定的函数？

同时性问题

同时性问题一个典型例子是秘密的同时交换，而合同签署可以视为其中的一个特殊情形

秘密的同时交换涉及到两个参与方，每一方都持有一个秘密。目标是执行一个协议，使得双方如果均正确遵守协议，那么协议结束时，每一方都能得到对方的秘密。并且在任何情况下，即使一方作弊，也应当满足：第一方得到第二方的秘密，当且仅当第二方也得到第一方的秘密

完全同时的秘密交换，只有在假设存在某种程度上可信的第三方时才能实现。事实上，如果有一个可信的第三方主动参与，那么秘密的同时交换就很容易实现：每一方通过安全信道把自己的秘密发送给可信第三方，第三方在收到两个秘密后，把第一方的秘密发送给第二方，把第二方的秘密发送给第一方

但是这种解决方法存在两个问题：

在所有情况下都需要一个外部参与方的主动参与，即使双方都是诚实的，也仍需要第三方参与
要求存在一个完全可信的第三方实体，但这样的实体不一定存在

函数的安全实现

另一类协议问题关注的是函数的安全实现，即讨论如何计算一个函数，这个函数的输入分别由不同用户持有

这类问题的一个典型的例子是投票。在投票问题中，需要计算的函数是多数函数，而用户 A 持有的输入是一个表示其投票选择的二元值，例如支持或反对

简单来说，一个用于安全计算某个特定函数的协议，需要满足以下条件：

隐私性（Privacy）：除可以从函数值本身推导出的信息外，任何参与方都不能获得其他参与方的输入
鲁棒性（Robustness）：除通过选择自己的输入所产生的影响外，任何参与方都不能影响函数值

有时，上述条件还于要求对于小的参与方联盟成立，而不仅仅是针对单个参与方

显然，如果已知某个用户是完全可信的，那么任何函数的安全计算都存在一个简单的解决方案：每个用户只需要通过安全信道把自己的输入发送给可信方，可信方在收到所有输入后计算函数，将结果发送给所有用户，并从自己的存储中删除收到的所有输入以及中间计算结果

但是，一个参与方被信任到这种程度是不现实的。例如，很难相信它会主动删除自己已经“学到”的内容。尽管如此，函数的安全实现可归约为可信第三方的实现问题，即如果能够实现一个可信第三方，就可以进一步实现函数的安全计算

零知识证明

零知识证明（Zero-knowledge Proofs）是构造容错协议的重要工具之一，其核心依据是：如果单向函数存在，那么所有 NP 语言均存在计算零知识证明系统

简单来说，零知识证明可以在不泄露任何额外信息（除断言本身成立这一事实）的情况下，向验证者证明某个断言为真，即：验证者能够确信断言为真，但无法从证明过程中获取到除“断言为真”这一事实外的任何额外信息，尤其不能获得用于证明该断言的证据

这一工具在容错协议设计中尤为重要，其迫使参与方诚实遵守协议，同时不泄露其私有输入，从而实现隐私保护下的正确性验证

为说明零知识的作用，考虑以下场景：Alice 从 Bob 那里收到一条加密消息后，需要向 Carol 发送这条消息的最低有效位

在这个场景中，需要证明的断言是：Alice 发送给 Carol 的这个比特，确实是原消息的最低有效位

能够证明该断言为真的证明材料是：完整的原始消息以及对应的解密秘钥

显然，如果 Alice 只发送这条消息的最低有效位，那么 Carol 无法判断 Alice 是否作弊，即 Carol 并不知道 Alice 发送的这一位是否真的是原消息的最低有效位

Alice 可以通过向 Carol 公开整条加密消息以及对应的解密秘钥来证明自己没有作弊，但这样会泄漏远超原本要求的信息

更好的方法是：Alice 在向 Carol 发送这一位时，附加一个零知识证明，来证明这一位确实是原消息的最低有效位。这样一来，Carol 可以确认 Alice 没有作弊，但不会获得除该断言有效性外的任何其他信息

因此，如果所有 NP 断言都存在零知识证明，那么 Alice 就可以在不泄露任何额外信息的情况下，证明自己发送的这一位确实是原消息的最低有效位

也就是说，零知识证明在这里的作用是：既保证协议参与方的行为可以被验证，又避免验证过程泄露不必要的信息

Alex_McAvoy

密码学概述