Lattice-Based Post-Quantum iO from Circular Security with Random Opening Assumption

Indistinguishability obfuscation (iO) is a powerful cryptographic primitive with numerous impactful applications. However, constructing post-quantum iO under simple and well-founded assumptions remains a significant challenge. Following the framework initiated by Brakerski et al. (Eurocrypt 2020), recent work has explored building post-quantum (x)iO by combining fully homomorphic encryption (FHE) with carefully designed “decryption hints” for homomorphically evaluated ciphertexts. The security of these constructions typically reduces to "LWE-with-hint" type assumptions, which assert the security of certain LWE samples even when specific auxiliary information is revealed. Unfortunately, subsequent cryptanalysis has identified structural weaknesses in all previously proposed variants of these assumptions, casting doubt on their soundness.

In response, we introduce a new assumption - Circular Security with Random Opening (CRO) - which overcomes key vulnerabilities in prior LWE-with-hint formulations. The CRO assumption features two critical properties: (1) the hint distribution is marginally uniform, and (2) natural uses of the hint do not give any noise leakage. These properties rule out important classes of attack strategies, including those that have broken earlier assumptions. Therefore, our new lattice-based assumption for iO provides a qualitatively different target for cryptanalysis compared to existing assumptions.

In this talk, I will begin by reviewing key ideas from earlier iO constructions and highlighting the problematic leakages that have been exploited in attacks. I will then present our new construction and explain the core insights that eliminate the known vulnerable structures.

Based on joint work with Aayush Jain and Huijia Lin.