Cryptology ePrint Archive: Report 2021/1226

Succinct LWE Sampling, Random Polynomials, and Obfuscation

Lalita Devadas and Willy Quach and Vinod Vaikuntanathan and Hoeteck Wee and Daniel Wichs

Abstract: We present a construction of indistinguishability obfuscation (iO) that relies on the learning with errors (LWE) assumption together with a new notion of succinctly sampling pseudo-random LWE samples. We then present a candidate LWE sampler whose security is related to the hardness of solving systems of polynomial equations. Our construction improves on the recent iO candidate of Wee and Wichs (Eurocrypt 2021) in two ways: first, we show that a much weaker and simpler notion of LWE sampling suffices for iO; and secondly, our candidate LWE sampler is secure based on a compactly specified and falsifiable assumption about random polynomials, with a simple error distribution that facilitates cryptanalysis.

Category / Keywords: Indistinguishability Obfuscation, Learning with Errors, LWE sampling

Original Publication (with major differences): IACR-TCC-2021

Date: received 17 Sep 2021, last revised 18 Oct 2021

Contact author: lali at mit edu, quach w at northeastern edu, vinodv at mit edu, hoeteck at alum mit edu, wichs at ccs neu edu

Available format(s): PDF | BibTeX Citation

Version: 20211018:172200 (All versions of this report)

Short URL: ia.cr/2021/1226


[ Cryptology ePrint archive ]