11.2 定义 Definitions
我们首先定义公钥加密的语法。该定义与定义3.7非常相似，只是不再使用一个密钥，而是使用不同的加密和解密密钥。
定义11.1公钥加密方案
定义11.1公钥加密方案是概率多项式时间算法（Gen、Enc、Dec）的三倍，因此：
- 密钥生成算法Gen将安全参数1^n作为输入，并输出一对密钥（pk，sk）。我们将其中的第一个称为公钥，第二个称为私钥。为了方便起见，我们假设pk和sk的长度至少为n，并且n可以由pk，sk确定。
- 加密算法Enc将公钥pk和来自某个消息空间（可能取决于pk）的消息m作为输入。它输出一个密文c，我们把它写成
。（展望未来，为了实现有意义的安全性，Enc需要具有概率性。）
- 确定性解密算法Dec以私钥sk和密文c作为输入，并输出消息m或特殊符号⊥ 表示失败。我们把它写成
。
需要的是，除了
与私钥设置的重要区别在于，密钥生成算法Gen现在输出两个密钥，而不是一个。公钥pk用于加密，私钥sk用于解密。重申我们之前的讨论，假定pk分布广泛，因此任何人都可以为生成此密钥的一方加密消息，但接收方必须将sk保密，以确保安全性。
我们允许解密错误的概率可以忽略不计，事实上，我们提出的一些方案的错误概率可以忽略不计（例如，如果需要选择一个素数，但以忽略不计的概率获得一个组合）。尽管如此，从现在起，我们通常会忽略这个问题。
对于公钥加密的实际使用，我们希望消息空间为
11.2.1 针对选定明文攻击的安全性 Security against Chosen-Plaintext Attacks
通过在公钥设置中引入定义3.8的“自然”对应项，我们开始处理安全性。由于该定义（以及我们将看到的其他定义）的广泛动机已经在第3章中给出，因此这里的讨论将相对简短，主要集中在私钥和公钥设置之间的差异。
给定公钥加密方案＝（Gen，EnC，DEC）和攻击者A，考虑下面的实验：
窃听不可分辨性实验 The eavesdropping indistinguishability experiment
窃听不可分辨性实验
- 运行
- 对手A被给予pk，并在消息空间中输出一对等长消息m0、m1。
- 均匀位b∈ 选择{0，1}，然后选择密文
是计算出来的，并给出给A。我们称c为质询密文。
- A输出位b'。如果b'=b，实验输出为1，否则为0。如果b'=b，我们说A成功了。
定义11.2
公开密钥加密方案∏=（Gen，Enc，Dec）在窃听者在场的情况下具有不可区分的加密，前提是对于所有概率多项式时间对手A，存在一个可忽略的函数negl，使得
。
上述定义与定义3.8之间的主要区别在于，此处A被赋予公钥pk。此外，我们允许A基于该公钥选择其消息m0和m1。这在定义公钥加密的安全性时非常重要，因为如前所述，我们假设对手知道接收方的公钥。
给对手一个用于加密消息的公钥pk的看似“微小”的修改产生了巨大的影响：它有效地提供了免费访问加密oracle的权限。（加密预言机的概念在第3.4.2节中进行了解释。）这是正确的，因为给定pk的对手可以通过简单计算
命题11.3
如果公钥加密方案在存在窃听者的情况下具有不可区分的加密，则该方案是CPA安全的。
这与私钥设置相反，私钥设置中存在的方案在窃听者在场时具有无法区分的加密，但在选择的明文攻击下不安全（见命题3.20）。接下来将讨论与私钥设置的进一步差异，这些差异几乎会立即产生上述结果。
不可能实现完全保密的公钥加密 Impossibility of perfectly secret public-key encryption
不可能实现完全保密的公钥加密。完全保密的公钥加密可以通过对窃听者的整个视图（即，包括公钥）进行调节，类似于定义2.3来定义。同样地，它可以通过扩展定义11.2来定义，要求所有对手A（不仅仅是高效对手），我们有：
然而，与私钥设置相反，无论密钥有多长或消息空间有多小，都不可能实现完全保密的公钥加密。事实上，一个无限的对手给出了pk和一个通过c计算的密文
确定性公钥加密的不安全性 Insecurity of deterministic public-key encryption
正如在私钥加密的上下文中所指出的，任何确定性加密方案都不能是CPA安全的。这里也是如此：
定理 11.4
没有确定性公钥加密方案是CPA安全的。
因为定理11.4是如此重要，它值得更多的讨论。该定理不是我们的安全定义的“产物”，也不是我们的定义太强的迹象。确定性公钥加密方案在现实场景中容易受到实际攻击，因此不应使用。
原因是确定性方案不仅允许对手确定何时发送同一消息两次（如在私钥设置中），
但如果加密的可能消息集很小，则允许对手以概率1恢复消息。例如，考虑一位教授对学生成绩的加密。这里，窃听者知道每个学生的分数必须是{A，B，C，D，F}中的一个。如果教授使用确定性公钥加密方案，窃听者可以通过加密所有可能的分数并将结果与给定密文进行比较，快速确定任何学生的实际分数。
尽管上述定理看似简单，但在很长一段时间内，许多真实世界的系统都是使用确定性公钥加密设计的。
在引入公钥加密时，可以公平地说，概率加密的重要性还没有完全实现。Goldwasser和Micali的开创性工作，其中（相当于）定义11.2的提出和定理11.4的陈述，标志着密码学领域的一个转折点。把一个人的直觉固定在一个正式的定义中，并第一次以正确的方式看待事物的重要性，即使回顾起来看起来很简单，也不应被低估。
11.2.2 多重加密 Multiple Encryptions
与第3章一样，了解使用同一密钥（在本例中为同一公钥）加密多条消息的效果非常重要。我们可以通过让对手输出两个明文列表，在这样的环境中制定安全性，如定义3.19所示。然而，出于第3.4.2节中讨论的原因，我们选择使用一个定义，在该定义中，攻击者可以访问“左或右”oracle LRpk，b，在输入一对等长消息m0，m1时，计算密文c← Encpk（mb）和eturns c。攻击者可以根据自己的喜好多次查询此oracle，因此，当使用同一公钥加密多条（未知）消息时，该定义将为安全性建模。
形式上，考虑为公钥加密方案=（Gen，EnC，DEC）和攻击者A定义的以下实验：
LR预言机实验 The LR-oracle experiment
LR预言机实验
- 运行Gen（1n）以获取密钥（pk、sk）。
- 均匀位b∈ 已选择{0，1}。
- 对手A被赋予输入pk和oracle访问
的权限。
- 对手A输出位b'。
- 如果b'=b，则实验输出定义为1，否则为0。如果
，则表示A成功。
定义
11.5
公开密钥加密方案∏=（Gen，Enc，Dec）具有不可区分的多重加密，前提是对于所有概率多项式时间对手A，存在可忽略的函数negl，从而：
。
我们将证明任何CPA安全方案自动具有不可区分的多重加密；也就是说，在公钥设置中，单个消息加密的安全性意味着多个消息加密的安全性。这意味着我们可以根据定义11.2证明某些方案的安全性，该定义更简单、更易于使用，并得出结论，该方案满足定义11.5，这是一个似乎更强的定义，可以更准确地模拟公钥加密的实际使用。下面给出了下列定理的证明。
定理 11.6
如果公钥加密方案∏是CPA安全的，那么它也有不可区分的多重加密。
如定理3.24所述，私钥设置中的类似结果已陈述，但未得到证明。
加密任意长度的消息 Encrypting arbitrary-length messages
定理11.6的直接结果是，固定长度消息的CPA安全公钥加密方案意味着满足相同安全概念的任意长度消息的公钥加密方案。我们在原始方案仅加密1位消息的极端情况下说明了这一点。假设∏=（Gen，Enc，Dec）是一种用于单比特消息的加密方案。我们可以构造一个新的方案∏'=（Gen，Enc'，Dec'），它具有消息空间
CLAIM 11.7
设∏和∏'如上所述。如果∏是CPA安全的，那么∏'也是安全的。
声明如下，因为我们可以将使用∏'对消息m的加密视为使用方案∏对t消息（m1，…，mt）的加密。
关于术语的说明 A note on terminology
我们介绍了公钥加密方案的三种安全性定义—不可区分加密—其中存在窃听者、CPA安全性和不可区分多重加密—它们都是等价的。按照密码学文献中的惯例，我们将简单地使用术语“CPA安全性”来指代满足这些安全概念的方案。
Proof of Theorem 11.6
11.2.3 针对选定密文攻击的安全性 Security against Chosen-Ciphertext Attacks
选择密文攻击，其中对手能够获得其选择的任意密文的解密（具有下文所述的一个技术限制），与私钥设置中的攻击一样，是公钥设置中的关注点。事实上，它们在公钥设置中更值得关注，因为接收者期望从多个可能事先未知的发送者接收密文，而私钥设置中的接收者打算仅使用任何特定密钥与单个已知发送者通信。
假设窃听者A观察到发送者S发送给接收者R的密文c。广义而言，在公钥设置中有两类选定的密文攻击：
- 在这种情况下，A可能会代表S向R发送修改后的密文c'（例如，在加密电子邮件的上下文中，A可能会构造加密电子邮件c'并伪造“发件人”字段，使其看起来似乎是源于S的电子邮件），尽管A不太可能获得c'的整个加密m'，A可能会根据R的后续行为推断出关于m'的一些信息。基于此信息，A可能能够了解关于原始消息m的一些信息。
- A可能会以自己的名义向R发送修改后的密文c'。在这种情况下，如果R直接响应A，则A可能获得c'的全部解密m'。即使A不知道关于m'的任何信息，该修改后的消息可能与原始消息m具有可被A利用的已知关系；有关示例，请参见下面的第三个场景。
第二类攻击特定于公钥加密的上下文，在私钥设置中没有类似的攻击。
不难确定一些说明上述攻击类型的现实场景：
情景1
假设一个用户登录到她的银行账户，向她的银行发送一个密码密码的加密密码，密码密码与时间戳连在一起。进一步假设银行发送两种类型的错误消息：如果加密密码与存储的S密码不匹配，则返回“密码不正确”；如果密码正确但时间戳不正确，则返回“时间戳不正确”。
如果对手获得由S发送给银行的密文c，则该对手现在可以通过代表S向银行发送密文c'并观察由此产生的错误消息来发起选定的密文攻击。（这类似于我们在第3.7.2节中看到的填充oracle攻击。）在某些情况下，此信息可能足以让对手确定用户的整个密码。
情景2
假设S向R发送一封加密电子邮件c，A观察到该电子邮件。如果A以自己的名义向R发送一封加密电子邮件c'，则R可能会回复该电子邮件并引用对应于c'的解密文本m'。在本例中，R实际上充当a的解密oracle，可能会解密a发送给它的任何密文。
情景3
与选定密文安全性密切相关的一个问题是密文的潜在可塑性。由于涉及到一个正式的定义，我们这里不提供一个定义，而是给出直观的想法。
如果一个方案具有以下属性，则该方案是可延展的：给定某个未知消息m的加密c，则可能产生密文c'，该密文c'是以某种已知方式与m相关的消息m0的加密。
例如，可能给定m的加密，可以构造2m的加密。（稍后我们将看到具有此属性和类似属性的CPA安全方案的自然示例；请参见第13.2.3节。）
现在假设R正在进行拍卖，其中双方S和A通过使用R的公钥对其进行加密来提交投标。如果使用可延展的加密方案，对手A可能总是出价最高（无需出价最高）通过执行以下攻击：等待S发送与其出价m（a未知）对应的密文c；然后发送与投标m'=2m对应的密文c'。请注意，在R宣布结果之前，m（以及m'）对A仍然是未知的，因此这种攻击的可能性与加密方案是CPA安全的事实并不矛盾。另一方面，CCA安全方案可以被证明是不可延展的，这意味着它们不易受到此类攻击。
定义
通过适当修改私钥设置（定义3.33）中的类似定义，定义了针对选定密文攻击的安全性。考虑到公钥加密方案和对手A，考虑下面的实验：
CCA不可分辨性实验 The CCA indistinguishability experiment
The CCA indistinguishability experiment 
- 运行
以获取密钥（pk、sk）。
- 对手A被授予pk并访问解密oracle
。它输出一对长度相同的消息m0、m1。（这些消息必须位于与pk关联的消息空间中。）
- 均匀位选择b∈{0，1}，然后选择密文
计算并将其提供给A。
- 不请求解密的继续与解密oracle交互，但可能是c本身。最后，A输出位b0。
- 如果b'=b，则实验输出定义为1，否则为0。
定义11.8
公开密钥加密方案∏=（Gen，Enc，Dec）在选定密文攻击下具有不可区分的加密（或是CCA安全的），如果对于所有概率多项式时间对手A存在可忽略的函数negl，则
。
定理11.6的自然类比也适用于CCA安全。也就是说，如果一个方案在选择密文攻击下具有不可区分的加密，那么它在选择密文攻击下具有不可区分的多重加密，这是适当定义的。然而，有趣的是，权利要求11.7的类似物并不适用于CCA担保。
正如定义3.33中所述，我们必须防止攻击者将质询密文c提交给解密oracle，以实现定义。但这一限制并不会使定义变得毫无意义，尤其是对于前面给出的三种激励场景中的每一种，可以认为设置c'=c对攻击者没有好处：
- 在第一个涉及基于密码登录的场景中，攻击者通过向银行重播c，对S的密码一无所知，因为在这种情况下，攻击者已经知道不会生成错误消息。
- 在涉及加密电子邮件的第二种情况下，向接收者发送c'=c可能会使接收者产生怀疑，因此会拒绝回复。
- 在涉及拍卖的最终场景中，如果对手的加密出价与另一方的加密出价相同，R可以很容易地检测到欺诈行为。无论如何，在这种情况下，攻击者通过重放c实现的所有目标就是它提交与诚实方相同的出价。
京公网安备 11010502036488号