Russell W. F. Lai, Researcher, Aalto University
Indistinguishability obfuscation turns a program unintelligible without altering its functionality. Because it captures the power of most known cryptographic primitives and enables new ones, obfuscation is often referred to as being crypto-complete. In this work we investigate constructions of indistinguishability obfuscation, whose security can be reduced from potentially hard problems over lattices. Compared to other candidates, a purely lattice-based obfuscator has the advantage of being based on a single source of hardness and being plausibly post-quantum, enabling many applications in quantum cryptography. We propose a new construction of lattice-based obfuscation whose security relies on an instance-independent assumption over lattices called the Equivocal Learning with Errors (LWE) assumption. Roughly, the assumption asserts that two related LWE distributions are computationally indistinguishable, even when given random LWE secrets which ``explain’’ the samples. Our main technical ingredient is a new statistical trapdoor algorithm for equivocating LWE secrets over lattices with exceptionally short vectors, which may be of independent interest.