Quasi-Linear Indistinguishability Obfuscation via Mathematical Proofs of Equivalence and Applications

Indistinguishability obfuscation () is a powerful cryptographic primitive and has been quoted as the ``swiss army-knife of modern cryptography''. Most prior works on focused on theoretical feasibility, and paid less attention to the efficiency of the constructions. As a result, all prior constructions stopped at achieving polynomial efficiency without worrying about how large the polynomial is. In fact, it has even been conjectured that a polynomial dependence on the input length is necessary.

In this work, we show that if the two circuits to be obfuscated enjoy a succinct propositional logic proof of equivalence, then we can
create obfuscated versions of these programs that are computationally indistinguishable; and importantly, the obfuscated program's efficiency is quasi-linear in the circuit size and proof size. We show that our quasi-linear construction also leads to new applications. Specifically, we show how to achieve quasi-linear efficiency for 1) for Turing Machines with unbounded inputs, and 2) multi-input functional encryption, also assuming succinct proofs of equivalence.