Welcome to the resource topic for 2019/1010
Title:
On Perfect Correctness in (Lockable) Obfuscation
Authors: Rishab Goyal, Venkata Koppula, Satyanarayana Vusirikala, Brent Waters
Abstract: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 .