Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

Indistinguishability obfuscation, introduced by [Barak et. al. Crypto 2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new ...

Cook and Krajíček have recently obtained the following Karp-Lipton collapse result in bounded arithmetic: if the theory PV proves NP⊆ P/poly, then the polynomial hierarchy collapses to the Boolean hierarchy, and this collapse is provable in PV. Here we ...

Since the seminal work of Garg etï źal. FOCS'13 in which they proposed the first candidate construction for indistinguishability obfuscation iO for short, iO has become a central cryptographic primitive with numerous applications. The security of the ...