Скачать или смотреть Beyond P versus NP: Using Complexity Theory in Obfuscation and Vice-Versa

Rahul Ilango (MIT)
https://simons.berkeley.edu/talks/rah...
Obfuscation

In this talk, I'll discuss new techniques for constructing cryptographic objects using indistinguishability obfuscation (iO). As a taste, our techniques enable us to construct
public-key encryption with optimal hardness guarantees, and
one-way functions with optimal direct product hardness (i.e., simultaneously solving independent instances scales according to the naive bound).

A key theme in our work is to combine iO with complexity-theoretic assumptions that go beyond P \neq NP. For instance, some of our results assume the co-non-deterministic hardness of SAT.

We also prove results of interest to complexity theory. For example, we use obfuscation to give a reduction from non-deterministically solving UNSAT to a solving a direct product version of Search-SAT.

This is joint work with Alex Lombardi.