跳转至

Notions of Reducibility between Cryptographic Primitives

Introduction

大多数的密码协议的安全性是依靠归约到看似更弱或是更简单的原语的安全性上，比如单向函数（OWF）的存在性表明了私钥加密的可能性. 但依然存在未被证明与单向函数等价的密码学原语，如公钥加密、不经意传输等. 此外，也有一些虽然基于单向函数，并且能在多项式时间内实现，但效率极低的密码学原语，比如基于单向函数的伪随机数生成器. 以上的问题催生出这个问题：能否从单向函数构造出额外的密码学原语，以及如何使得已知构造变得更高效.

密码学中的大多数蕴含关系都是通过规约进行证明，初始的原语被视为谕示机或是黑盒，而分析表明如果该原语在黑盒意义下是安全的，那么构造出的原语也是安全的. 但在不同额外约束的黑盒规约模型中，情况会有所不同. Impagliazzo 和 Rudich 证明其中一种模型中的基于单向函数的密钥协商（KA）的黑盒构造将蕴含 \(\mathsf{P} \neq \mathsf{NP}\) 的证明；而在另外一种约束更强的模型中，这样的构造是不可能的. 他们的形式化框架也被用于解决其他的蕴含问题，而这些结果的普遍解读是：使用原语作为黑盒存在固有的局限性，这些不可能性结果只能通过明确使用原语的代码来克服.

但本文将重新审视这些结果，对黑盒规约的形式化方法进行更细致的分类，强化一些先前的结果，并且提出新的解读：在许多情况下，将原语作为黑盒使用并无限制，但将敌手视为黑盒则存在限制. 特别地，这些否定结果可以通过在分析中明确使用敌手的代码来克服.

Impossibility Results for Reductions

从单向函数到原语 Q 的黑盒（BB）规约是一种构造，其将函数 \(f\) 作为谕示机使用，并且保证如果 \(f\) 是单向函数，那么构造出的原语 Q 也是安全的. 具体来说：

  • 该构造不使用 \(f\) 的代码；
  • 即使 \(f\) 不是高效可计算的，但只要其作为谕示机给出，该构造也是良定义且高效的；
  • 存在一个安全性证明表明任何破坏协议的敌手都能产生一个可以逆转 \(f\) 的敌手.

形式化第三个条件的方法有很多，其中一种是指存在一个算法，该算法能将每一个破坏构造的敌手转换成一个能逆转 \(f\) 的过程，其被称为完全黑盒规约. 该算法是高效的，并且被赋予了对敌手和 \(f\) 的谕示机访问权限. 在这种设定下，构造和分析都是黑盒的；另一种看待它的方式是原语和敌手都被视为黑盒. 大部分规约都是完全黑盒的.

Impagliazzo 和 Rudich 证明，不可能存在从 OWF 到 KA 的完全黑盒规约，而因为公钥加密、陷门置换和不经意传输都通过完全黑盒规约到 KA，所以也不存在从 OWF 到这些原语的完全黑盒规约.

所以问题是出在了将原语和敌手都视为黑盒上吗？还是只要原语被视为黑盒就足以诱发？Impagliazzo 和 Rudich 又考虑了一种从 OWF 到 KA 的形式更弱的规约，称为半黑盒规约. 半黑盒规约中有一个基于谕示机 \(f\) 的 KA 的黑盒构造，分析证明，对于每个具有 \(f\) 的谕示机访问权限并且能够破坏该构造的高效敌手，都存在一个在拥有 \(f\) 的谕示机访问权限的情况下逆转 \(f\) 的高效敌手. 如果 \(f\) 是黑盒意义上的单向函数，那么这个构造不仅对高效敌手需要是安全的，而且对所有拥有 \(f\) 的谕示机访问权限的敌手都需要是安全的. 在这种情况下，利用敌手代码的证明技术就不是黑盒的了.

Impagliazzo 和 Rudich 证明，如果 \(\mathsf{P} \neq \mathsf{NP}\)，那么就不存在 OWF 到 KA 的半黑盒规约；他们通过建立一个更强的论断来证明这一结果：如果 \(\mathsf{P} \neq \mathsf{NP}\)，那么随机谕示机模型中不存在安全的 KA.

The Limitations of Semi-BB Reductions

本文中无条件地证明了不存在从 OWF 到 KA 的半黑盒规约. 这通过将 \(\mathsf{PSPACE}\) 谕示机嵌入到 Impagliazzo-Rudich 结果中使用的随机谕示机的一部分，并结合 \(\mathsf{P}^\mathsf{PSPACE} = \mathsf{NP}^\mathsf{PSPACE}\) 来证明.

嵌入技术使本文能够在所有先前有条件地排除半黑盒归约的情况下，证明半黑盒归约是无条件不可能的. 更一般地，本文表明在大多数自然原语满足的温和条件下，半黑盒规约等价于相对化规约（relativizing reductions），即证明该蕴含关系相对于任何谕示机都成立. 而先前的工作无条件地排除了相对化规约，所以也就得到了半黑盒规约地无条件不可能性.

The Power of Mildly-BB Reductions

首先形式化具有任意证明的黑盒构造的概念，称为温和黑盒规约（mildly black-box reductions）. 例如在 OWF 到 KA 的温和黑盒规约中