International Association
for Cryptologic Research

Indistinguishability Obfuscation (IO) 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 IO. First, we consider a notion of \emph{witness pseudo-canonicalization (WPC)}---which roughly speaking, requires, given a witness $w$ for some $NP$ statement $x$, efficiently outputting a pseduo-canonical witness $w'$ for the same statement $x$ (i.e., one that is \emph{computationally independent} of $w$). We remark that WPC for the Minimum Circuit Size problem (MCSP) is essentially equivalent to the notion of (exponentially-efficient) IO, which in turn can be bootstrapped into IO (assuming LWE and subexponential security). We next provide a further study of the notion of WPC, noting that this notion captures not only IO 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 $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 $R$ through a problem referred to as the \emph{Decisional Computational Shallowness} ($DCS$) problem. Intuitively, the $DCS$ problem with w.r.t. witness-relation $R$ and an instance $\varphi$, requires deciding, given $x, y, z \in R(\varphi)$, which of $CD^t(z| x)$ and $CD^t(z| y)$ is smaller, where $CD^t(z| x)=K^t(z| x)-K(z| x)$ is the (Kolmogorov) \emph{Computational Depth} and $t(size{z})$ 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), which leads our new complexity-theoretic characterization of (weak) IO.

In 2002, Barak and Goldreich introduced the notion of a {\em universal argument} and constructed an interactive universal argument for non-deterministic computations based on polynomially hard collision-resistant hash functions. Since then, and especially in recent years, there have been tremendous developments in the construction of {\em non-interactive} succinct arguments for deterministic computations under standard hardness assumptions. However, the constructed succinct arguments can be proven universal only under {\em sub-exponential} assumptions. Assuming {\em polynomially hard} fully homomorphic encryption and a widely believed worst-case complexity assumption, we prove a general lifting theorem showing that all existing non-interactive succinct arguments can be made universal. The required complexity assumption is that non-uniformity does not allow arbitrary polynomial speedup. In the setting of uniform adversaries, this extra assumption is not needed.