CryptoDB
A Meta-Complexity Theoretic Approach to Indistinguishability Obfuscation and Witness Pseudo-Canonicalization
Authors: |
|
---|---|
Download: | |
Conference: | TCC 2025 |
Abstract: | 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. |
BibTeX
@inproceedings{tcc-2025-36251, title={A Meta-Complexity Theoretic Approach to Indistinguishability Obfuscation and Witness Pseudo-Canonicalization}, publisher={Springer-Verlag}, author={Tomer Solomon and Noam Mazor and Rafael Pass}, year=2025 }