Cryptology ePrint Archive: Report 2019/1025

On Perfect Correctness without Derandomization

Gilad Asharov and Naomi Ephraim and Ilan Komargodski and Rafael Pass

Abstract: We give a method to transform any indistinguishability obfuscator that suffers from correctness errors into an indistinguishability obfuscator that is $\textit{perfectly}$ correct, assuming hardness of Learning With Errors (LWE). The transformation requires sub-exponential hardness of the obfuscator and of LWE. Our technique also applies to eliminating correctness errors in general-purpose functional encryption schemes, but here it is sufficient to rely on the polynomial hardness of the given scheme and of LWE. Both of our results can be based $\textit{generically}$ on any perfectly correct, single-key, succinct functional encryption scheme (that is, a scheme supporting Boolean circuits where encryption time is a fixed polynomial in the security parameter and the message size), in place of LWE.

Previously, Bitansky and Vaikuntanathan (EUROCRYPT 17) showed how to achieve the same task using a derandomization-type assumption (concretely, the existence of a function with deterministic time complexity $2^{O(n)}$ and non-deterministic circuit complexity $2^{\Omega(n)}$) which is non-game-based and non-falsifiable.

Category / Keywords: foundations / Indistinguishability Obfuscation, Correctness, Functional Encryption

Date: received 10 Sep 2019

Contact author: asharov at cornell edu, nephraim at cs cornell edu, komargodski at cornell edu, rafael at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20190911:072447 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]