Lattice-Based Post-quantum iO from Circular Security with Random Opening Assumption
摘要
Indistinguishability obfuscation ( \(\textsf{iO}\) ) stands out as a powerful cryptographic primitive but remains notoriously difficult to realize under simple-to-state, post-quantum assumptions. Recent works have proposed lattice-inspired \(\textsf{iO}\) constructions backed by new “LWE-with-hints” assumptions, which posit that certain distributions of LWE samples retain security despite auxiliary information. However, subsequent cryptanalysis has revealed structural vulnerabilities in these assumptions, leaving us without any post-quantum \(\textsf{iO}\) candidates supported by simple, unbroken assumptions. Motivated by these proposals, we introduce the Circular Security with Random Opening ( \({\textsf{CRO}}\) ) assumption—a new LWE-with-hint assumption that addresses structural weaknesses from prior assumptions, and based on our systematic examination, does not appear vulnerable to known cryptanalytic techniques. In \({\textsf{CRO}}\) , the hints are random “openings” of zero-encryptions under the Gentry–Sahai–Waters (GSW) homomorphic encryption scheme. Crucially, these zero-encryptions are efficiently derived from the original LWE samples via a special, carefully designed procedure, ensuring that the openings are marginally random. Moreover, the openings do not induce any natural leakage on the LWE noises. These two features—marginally random hints and the absence of (natural) noise leakage—rule out important classes of attacks that had undermined all previous LWE-with-hint assumptions for \(\textsf{iO}\) . Therefore, our new lattice-based assumption for \(\textsf{iO}\) provides a qualitatively different target for cryptanalysis compared to existing assumptions. To build \(\textsf{iO}\) under this less-structured \({\textsf{CRO}}\) assumption, we develop several new technical ideas. In particular, we devise an oblivious LWE sampling procedure, which succinctly encodes random LWE secrets and smudging noises, and uses a tailored-made homomorphic evaluation procedure to generate secure LWE samples. Crucially, all non-LWE components in this sampler, including the secrets and noises of the generated samples, are independently and randomly distributed, avoiding attacks on non-LWE components.