什么是复杂性利用？

Question

复杂性利用是一种通常用于证明选择性安全方案的自适应安全性的技术。例:我们可以利用复杂性来证明姚的杂乱策略的适应性安全性。许多论文提到了复杂性的杠杆作用，但没有详细介绍。如果有人能用一个详细的例子来解释复杂性，我将不胜感激。

Answer 1

复杂性利用是一种简化，其中“约简算法”运行在一个比对手更复杂的类中。例如，虽然对手只是多项式时间，但我们可以构造一个运行在时间n^{\log n}中的模拟器。在考虑仿真范式时，这是不太令人满意的。例如，在零知识中，论点是对手什么也学不到，因为它可以通过运行模拟器本身来生成它所看到的任何东西。然而，当使用复杂性利用时，对手实际上无法运行模拟器(因为它在一个较低的复杂性类中)。然而，在某些情况下，它可能是有意义的。例如，让我们考虑一个基于“基于游戏”或基于不可区分的安全概念。然后，我们证明了，如果一个在多项式时间运行的对手可以破坏我们的方案，那么就会有一个在时间上运行的对手，比如n^{\log n}，他可以破坏一个散列函数(或其他任何东西；这只是一个例子)。现在，如果哈希函数对于任何在时间上运行的n^{\log n}的对手都是安全的，那么这就足以保证我们的方案的安全性。

就我个人而言，我并不热衷于利用复杂性。在某些情况下，除了定义上的缺点(例如，模拟)，还存在一个很大的缺点，因为它需要一个更强的假设(不是一个原语不能被多时间对手打破，而是由具有某种特定功能的超多时间对手破坏)。然而，它已经被成功地用于实现其他未知的事情。此外，在许多情况下，第一次构造使用了复杂性杠杆，之后的构造成功地消除了假设。

========

后面添加:需要更强的假设的原因如下。假设您有一个从ZK到OWFs的缩减，这样任何区分模拟和不可忽略概率的实际执行的算法都可以用不可忽略的概率反演OWF。现在，假设您使用拟多项式模拟。为了证明对手什么也学不到，你需要假设单向函数对准多项式逆变器是安全的。这是因为，为了用模拟的执行来代替真实的证明执行，你需要在拟多项式的时间内运行。所以，现在你有一个准多项式的时间对手，他实际上正在运行。那么，只有当对手不能破坏OWF时，才能减少到OWF。(当然，这都是挥手，但这是在证据中发生的事情。)