[Resource Topic] 2021/1226: Succinct LWE Sampling, Random Polynomials, and Obfuscation

Welcome to the resource topic for 2021/1226

Succinct LWE Sampling, Random Polynomials, and Obfuscation

Authors: Lalita Devadas, Willy Quach, Vinod Vaikuntanathan, Hoeteck Wee, Daniel Wichs


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.

ePrint: https://eprint.iacr.org/2021/1226

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

Slides: https://iacr.org/submit/files/slides/2021/tcc/tcc2021/187/slides.pptx

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 .