[Resource Topic] 2019/1010: On Perfect Correctness in (Lockable) Obfuscation

Welcome to the resource topic for 2019/1010

On Perfect Correctness in (Lockable) Obfuscation

Authors: Rishab Goyal, Venkata Koppula, Satyanarayana Vusirikala, Brent Waters


In a lockable obfuscation scheme a party takes as input a program P, a lock value \alpha, a message m and produces an obfuscated program \tilde{P}. The obfuscated program can be evaluated on an input x to learn the message m if P(x)= \alpha. The security of such schemes states that if \alpha is randomly chosen (independent of P and m), then one cannot distinguish an obfuscation of P from a ``dummy’’ obfuscation. Existing constructions of lockable obfuscation achieve provable security under the Learning with Errors assumption. One limitation of these constructions is that they achieve only statistical correctness and allow for a possible one sided error where the obfuscated program could output the m on some value x where P(x) \neq \alpha. In this work we motivate the problem of studying perfect correctness in lockable obfuscation for the case where the party performing the obfuscation might wish to inject a backdoor or hole in correctness. We begin by studying the existing constructions and identify two components that are susceptible to imperfect correctness. The first is in the LWE-based pseudo random generators (PRGs) that are non-injective, while the second is in the last level testing procedure of the core constructions. We address each in turn. First, we build upon previous work to design injective PRGs that are provably secure from the LWE assumption. Next, we design an alternative last level testing procedure that has additional structure to prevent correctness errors. We then provide a surgical proof of security (to avoid redundancy) that connects our construction to the construction by Goyal, Koppula, and Waters (GKW). Specifically, we show how for a random value \alpha an obfuscation under our new construction is indistinguishable from an obfuscation under the existing GKW construction.

ePrint: https://eprint.iacr.org/2019/1010

Talk: https://www.youtube.com/watch?v=vB9VRTlsdGI

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .