CryptoDB
Obfuscating Pseudorandom Functions is Post-Quantum Complete
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | The last decade has seen remarkable success in designing and uncovering new applications of indistinguishability obfuscation (i$\O$). The main pressing question in this area is whether {\em post-quantum} i$\O$ exists. All current lattice-based candidates rely on new, non-standard assumptions, many of which are known to be broken. To make systematic progress on this front, we investigate the following question: can general-purpose i$\O$ be reduced, assuming {\em only} learning with errors (LWE), to obfuscating a smaller class of functions? The specific class of functions we consider are {\em pseudorandom functions} (PRFs), which constitute a natural functionality of independent interest. We show the following results: \begin{itemize} \item We construct exponentially-efficient i$\O$ (xi$\O$) for general circuits based on LWE in the pseudorandom oracle model -- a variant of the Random Oracle model (Jain et al., CRYPTO'23). Our construction requires the pseudorandom oracle model heuristic to hold for a \emph{specific} pseudorandom function and we prove its security against classical adversaries. \item We construct (post-quantum) i$\O$ for general circuits in the standard model based on (post-quantum) sub-exponentially secure LWE and (post-quantum) sub-exponentially secure {\em average-case} i$\O$ -- a natural notion of i$\O$ for pseudorandom functions that we define. \end{itemize} To obtain these results, we generalize the ``encrypt-evaluate-decrypt'' paradigm used in prior works by replacing the use of fully homomorphic encryption with succinct secure two-party computation where parties obtain additive output shares (Boyle et al., EUROCRYPT'25 and Abram et al., STOC'25). |
BibTeX
@inproceedings{tcc-2025-36281,
title={Obfuscating Pseudorandom Functions is Post-Quantum Complete},
publisher={Springer-Verlag},
author={Pedro Branco and Abhishek Jain and Akshayaram Srinivasan},
year=2025
}