Indistinguishability Obfuscation (\(i\mathcal {O}\)) is a central hub of modern cryptography, with far reaching applications. Over the last decade, a handful of constructions ranging from heuristic ones to, more recently following the breakthrough of Jain, Lin and Sahai [STOC’21], provably secure constructions based on well-formed assumptions. The provably secure constructions, however, rely on various different assumptions, some of which can be broken in quantum polynomial time.
In this work we propose meta-complexity-theoretic characterizations of \(i\mathcal {O}\). First, we consider a notion of witness pseudo-canonicalization (WPC)—which roughly speaking, requires, given a witness w for some \(\textrm{NP}\) statement x, efficiently outputting a pseudo-canonical witness \(w'\) for the same statement x (i.e., one that is computationally independent of w). We remark that WPC for the Minimum Circuit Size problem (MCSP) is essentially equivalent to the notion of (exponentially-efficient) \(i\mathcal {O}\), which in turn can be bootstrapped into \(i\mathcal {O}\) (assuming LWE and subexponential security).
We next provide a further study of the notion of WPC, noting that this notion captures not only \(i\mathcal {O}\) but also non-interactive witness indistinguishabilty (NIWI); at the same time, (assuming OWFs) it is impossible to achieve it for any witness relation that is \(\textrm{NP}\)-complete w.r.t. (honest) Levin reductions.
Finally, we provide a purely meta-complexity (worst-case) characterization of WPC w.r.t. some witness relation \(\mathcal{R}\) through a problem referred to as the Decisional Computational Shallowness (\(\textbf{DCS}\)) problem. Intuitively, the \(\textbf{DCS}\) problem with w.r.t. witness-relation \(\mathcal{R}\) and an instance \(\varphi \), requires deciding, given \(x, y, z \in \mathcal{R}(\varphi )\), which of \(\textbf{CD}^t(z| x)\) and \(\textbf{CD}^t(z| y)\) is smaller, where \(\textbf{CD}^t(z| x)=\textrm{K}^t(z| x)-\textrm{K}(z| x)\) is the (Kolmogorov) Computational Depth and \(t(\left| z\right| )\) is some polynomial. We show that DCS w.r.t. R is essentially equivalent to a notion of “weak" WPC (i.e., with weak indistinguishability) w.r.t. R, which leads our new complexity-theoretic characterization of (weak) \(i\mathcal {O}\).
