Obfuscating Pseudorandom Functions is Post-quantum Complete
摘要
The last decade has seen remarkable success in designing and uncovering new applications of indistinguishability obfuscation (i \(\mathcal {O}\) ). The main pressing question in this area is whether post-quantum i \(\mathcal {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 \(\mathcal {O}\) be reduced, assuming only learning with errors (LWE), to obfuscating a smaller class of functions? The specific class of functions we consider are pseudorandom functions (PRFs), which constitute a natural functionality of independent interest. We show the following results: 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).