安全归约基础（二）

本文主要是介绍安全归约基础（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.敌手概述

我们通常假设敌手能攻破所提方案，敌手对模拟方案可以发出哪种攻击在安全归约中十分重要，本节将具体介绍敌手。

什么是自适应攻击？

令 a 为从集合{ 0 ，1}中选择的一个整数，如果 a 是随机选择的，则有

$P_{r}\left [ a = 0 \right ] =P_{r}\left [ a = 1 \right ]=\frac{1}{2}$

如果 a 是自适应选择的，则 $P_{r}\left [ a = 0 \right ]$ 和 $P_{r}\left [ a = 1 \right ]$ 是未知的。自适应攻击是一种特定攻击，即敌手在给定空间的选择不是均匀分布的，其概率分布未知。

在敌手和模拟器之间的安全归约中，自适应攻击由三部分组成。我们以EU-CMA安全模型下数字签名方案的安全归约为例来解释这三个部分。假设消息空间为{m1，m2，m3，m4，m5}，五个消息互不相同，敌手将先询问其中两个消息的签名，再伪造新消息的有效签名。

敌手向模拟器询问的内容是自适应的。我们不能认为敌手将以2/5的概率询问某个特定的消息（例如m3）的签名。相反，敌手询问消息m对应签名的概率未知。

敌手如何向模拟器询问是自适应的。敌手既可以同时输出两个消息进行签名询问，也可以一次输出一个。对于后者，敌手决定第一个要进行签名询问的消息；在收到消息的签名后，它决定要询问的第二个消息。

对模拟器来说，敌手的输出是自适应的。如果敌手对消息m2和m。进行签名询问，那么我们不能认为伪造签名中的消息将是{m1，m2，m3}中的某个随机消息m*，而是敌手会以一个[0，1]之间的未知概率来伪造{ m1, m2，m3}中某一个消息的签名，且该概率满足

Pr[m*=m1]+Pr[m*=m2]+Pr[m*=m5]=1

自适应攻击指不仅敌手向模拟器询问的方式是自适应的，而且敌手的所有选择内容也是自适应的（除非选择被安全模型限制）。例如，在数字签名的弱安全模型下，敌手必须伪造由模拟器指定的消息m*的签名。在这种情况下，m*不是敌手自适应选择的。但是，也存在一些安全模型(如IBE的IND-sID-CPA模型）要求敌手需要在看到主公钥之前输出挑战身份，但它仍可以从身份空间中自适应地选择该挑战身份。

黑盒敌手

攻破假设表明，存在一个在多项式时间内以不可忽略的优势攻破所提方案的敌手。除了时间和优势之外，敌手不会受到任何限制。安全归约中的敌手是黑盒敌手，其最为重要的一条性质是：将询问的内容以及将发出的攻击是不受限制的，且模拟器也是无法知道的。

对于这样的黑盒敌手，我们使用自适应攻击来描述黑盒敌手的行为。但是，以黑盒敌手来描述安全归约中的敌手是远远不够的。

恶意敌手

假设安全归约中仅存在两种可以攻破模拟方案的攻击：，另一种是无用攻击。那么我们来考虑以下问题：

敌手返回有用攻击的概率是多少？

据对黑盒敌手的描述，我们知道由于敌手的自适应攻击，这个概率是未知的。但是，正确的安全归约要求我们能够计算出返回有用攻击的概率。了解决此问题，我们将黑盒敌手放大为恶意敌手，并考虑恶意敌手返回用攻击的最大概率。

简单游戏中的敌手

为了帮助读者更好地理解不可区分模拟中恶意敌手的含义，我们给出简单游戏来说明安全归约的难点。在这个简单游戏中：

（1）模拟器利用一个随机值 $b\ \epsilon \left \{ 0,1 \right \}$ 构造模拟方案；

（2）敌手自适应地选择 $a\ \epsilon \left \{ 0,1 \right \}$ 作为攻击;

（3）当且仅当a≠b时，敌手的攻击才是有用攻击。

在安全归约中，a可以看作敌手发起的自适应攻击，其中 a=0 和 a=1 都可以攻破该方案；b 可以看作模拟方案中的秘密信息。在模拟中，提供给敌手的所有参数可能包括有关如何发起无用攻击的秘密信息。恶意敌手的目的是使攻击无用，它将尝试从模拟方案中猜测 b，然后以Pr[ a=b ]=1的概率输出攻击 a 。

安全归约的难点在于必须以敌手不知道如何发起无用攻击的方式来实现模拟过程。在安全归约的正确性分析中，概率 Pr[ a≠b ] 必须是不可忽略的。为此，b 必须随机且独立于提供给敌手的所有参数，以便敌手只能以1/2的概率正确猜测出b。在这种情况下，即使敌手自适应选择 a ，也有Pr[ a≠b ]=1/2。

如何发起一个无用攻击

敌手发起无用攻击的方式在此无法详细描述，其高度依赖于所提方案、归约算法和底层困难问题。我们仅概括数字签名和加密的无用攻击应该具备的条件。

假设签名方案的安全归约使用敌手伪造的签名来解决底层的困难问题。无用攻击是针对模拟方案的特殊伪造签名，该签名有效且模拟器可以自己计算得出，因此它无法用于解决底层的困难问题。

假设加密方案的安全归约使用敌手对加密消息的猜测来解决底层的判定性困难问题。无用攻击是猜测加密消息m。的一种特殊方式，它满足的条件是无论判定性问题实例中的目标乙为True还是False，敌手始终可以正确猜出挑战密文中的消息，即 c' = c 。

由于知道模拟中的秘密信息，因此敌手可以发起一个无用攻击。如何使用完全困难问题向敌手隐藏秘密信息，这是安全归约中很重要的一步。

2.敌手的成功攻击及其概率

令 $p_{\varepsilon }$ 为攻破假设下所提方案返回成功攻击的概率。在安全归约中，敌手将对模拟方案发起一次成功攻击，其概率如下：

如果模拟方案与真实方案是不可区分的，那么根据攻破假设，敌手对模拟方案进行成功攻击的概率为 $p_{\varepsilon }$ 。

若模拟方案与真实方案是可区分的，那么敌手对模拟方案进行成功攻击的概率为P*∈[0，1]。该概率是敌手自己决定的恶意且自适应的概率。因为模拟方案与真实方案不同，因此以这样的恶意概率返回一个成功攻击并不违背攻破假设。

3.敌手的计算能力

所有公钥密码方案都只是计算性安全的。如果存在一个具有无穷计算能力且可以解决所有计算性困难问题的敌手，那么它肯定可以在多项式时间内以不可忽略的优势攻破任何所提方案。例如，敌手可以利用其无穷的计算能力解决离散对数问题，该离散对数可以应用于攻破所有基于群的方案中。因此，所提方案仅对计算能力有限的敌手是安全的。

一个有趣的问题是：在分析所提方案的安全性时，我们应该限制敌手无法解决哪些问题。证明所提方案的可证明安全性（不提其安全模型）通常可以使用以下定理：

如果数学问题P是困难的，则所提方案是安全的，即没有敌手可以在多项式时间内以不可忽略的优势攻破该方案。

上述定理指出，在问题P的困难假设下，所提方案是安全的。在解决困难问题P时，敌手的计算能力似乎是有限的。也就是说，我们只证明所提方案在面对无法解决困难问题P（或比P更困难的问题）的敌手时是安全的，这种证明思路符合逻辑，是可接受的。因为假设了问题P是困难的，所以我们不关心所提方案对一个能够解决问题P的敌手是否安全。

在安全归约中，为了简化正确性分析，敌手的计算能力被认为是无限的。通常来说，所提方案仅对计算能力有限的敌手是安全的，但是相应的安全归约应该对计算能力无限的敌手也是有效的。

归约中的敌手

安全归约始于攻破假设，即存在一个敌手，该敌手可以在多项式时间内以不可忽略的优势攻破所提方案。然后，我们构建一个模拟器，它可以生成模拟方案并利用敌手的攻击解决困难问题。根据前面的解释，安全归约中的敌手概述如下。

敌手具有无限的计算能力。它既可以解决定义在数学原语上的所有计算性困难问题，也可以攻破模拟方案。

敌手将恶意地尽力对模拟方案发起无用攻击，从而使安全归约失败。

虽然我们假设敌手具有无限的计算能力，但是我们不能直接要求敌手为我们解决底层的困难问题。敌手所做的只能是对那些看起来像是真实方案的方案发起一次成功攻击。这就是敌手在安全归约中可以做并且唯一会做的事情。接下来，我们需要了解在安全归约中，敌手知道哪些信息、不知道哪些信息。

归约中敌手的计算能力

在安全归约中，模拟（比如由模拟器计算的应答）可能包含一些秘密信息（以Ⅱ表示）。这些信息会告诉敌手如何对模拟方案发起无用攻击。例如，简单游戏中的b就是敌手无法获知的秘密信息。其他的一些示例可以在本章末找到。模拟器必须隐藏此秘密信息，否则，一旦恶意敌手从模拟给定参数获取信息Ⅱ，它将始终发起无用攻击。这里的给定参数是指敌手可以从模拟方案中获取的所有信息，例如公钥和签名。

隐藏秘密信息Ⅱ最简单的方法是模拟器永远不要向敌手透露秘密信息Ⅱ。然而，我们发现现有文献的安全归约都必须对询问做出应答，而应答中包含信息Ⅱ。为了保证敌手不知道信息Ⅱ，模拟器必须使用一些困难问题来隐藏它。令P为安全归约的底层困难问题，模拟器有三种方法来隐藏安全归约中的秘密信息Ⅱ。

（1）模拟器通过以一组新困难问题 $p_{1},p_{2},....p_{q}$ ，隐藏信息Ⅱ的方式来设计安全归约。安全归约的正确性要求这些新的困难问题不能比问题P简单，否则，敌手可以通过解决这些困难问题来获得信息Ⅱ。为此，我们必须证明信息Ⅱ只能通过解决这些困难问题来获得，而且这些困难问题并不比底层困难问题P简单。此方法是非常困难的，因为我们可能无法将困难问题 $p_{1},p_{2},....p_{q}$ 归约到困难问题P。

（2）模拟器通过用困难问题P隐藏信息的方式来设计安全归约。由于假设了解决问题P是困难的，那么该方法是有效的。然而，如何利用问题P来隐藏信息Ⅱ使其不被敌手发现是很难实现的。例如，P是CDH问题,假设信息Ⅱ被 $g^{ab}$ 隐藏，而敌手知道 $(g,g^{a},g^{b})$ 。模拟器不应该向敌手提供另外的群元素（如群元素 $g^{a^{2}b}$ )，否则，它就不再是CDH问题。

（3）模拟器通过以完全困难问题隐藏信息Ⅱ的方式来设计安全归约，即使计算能力无限的敌手也无法解决完全困难问题。这种方法非常有效，因为这些完全困难问题是通用的，并且独立于底层困难问题P。在这种情况下，我们只需要证明信息隐藏在完全困难问题中。

仅介绍通过第三种方法隐藏秘密信息的安全归约。因此，敌手可以具有无限的计算能力。此方法虽然是充分不必要的，但是它为分析安全归约的正确性提供了最有效的方法。现有文献所提的大多数安全归约也都采用了第三种方法。

4.敌手知道的信息

敌手知道三类信息。

方案算法 敌手知道所提方案的方案算法。也就是说，敌手知道如何根据输入准确地计算输出。例如，为了攻破签名方案，敌手知道系统参数生成算法、密钥生成算法、签名算法和验证算法。

归约算法 敌手知道用来证明所提方案的安全性的归约算法。否则，我们必须证明敌手自身无法从方案算法中知晓归约算法（也就是说，我们要么证明敌手不知道归约算法，要么直接允许敌手知道归约算法）。例如，敌手知道模拟器如何模拟公钥、如何选择随机数、如何应答询问,以及如何通过有用攻击来解决底层困难问题。

如何解决所有计算性困难问题 敌手具有无限的计算能力，可以解决所有计算性困难问题。例如，在基于群的密码学中，给定 $(g,g^{a})$ ,我们假设敌手可以在发起攻击之前计算出a。但是，敌手不能攻破方案构造所用的其他密码原语（如哈希函数），否则它可能通过攻破组件来攻破模拟方案，从而导致安全归约永远无法成功。

我们假设敌手知道归约算法。尽管模拟方案是由归约算法生成的，然而这不意味着敌手知道模拟方案中模拟器选择的所有秘密参数。有些秘密信息是敌手永远不会知道的。否则，我们将不可能实现成功的安全归约。

5.敌手不知道的信息

有三种秘密信息是敌手永远不会知道的。

随机数 在模拟器生成模拟方案时，除非敌手能够计算出这些随机数，否则敌手不知道模拟器选择的随机数（包括群元素）。例如，模拟器随机选择两个秘密数 x,y∈Z，，我们假设敌手不知道这两个随机数。但是，一旦将 $(g,g^{x+y})$ 给了敌手，根据前面的描述，敌手会知道x+y。

问题实例 敌手不知道提供给模拟器的底层困难问题的随机实例。这种假设是为了简化不可区分性的证明。例如，假设Bob提出了一个方案和一个安全归约，并表明如果存在一个可以攻破该方案的敌手，则该归约可以找到离散对数问题实例 $(g,g^{a})$ 的解。在安全归约中，敌手收到一个密钥对 $(g,g^{a})$ ，它等于 $(g,g^{a})$ 。由于敌手知道 $(g,g^{a})$ 是一个问题实例（而不是一个真正的密钥对），因此它将立刻发现给定方案是模拟方案，并停止攻击。

如何解决完全困难问题 敌手不知道如何解决完全困难问题，例如，如何根据 $(g,g^{x+y})$ 计算（x，y)。另一个例子是给定（m1，m2，f(m1）,f(m2))，计算（ m* , f(m*) )，其中 f(x)∈Zp[x] 是一个随机的2次多项式，m* ∉ {m1，m2}。

通常，敌手将利用所知道的信息对模拟方案发起无用攻击，而模拟器应利用敌手所不知道的一切来迫使敌手以不可忽略的优势发起有用攻击。