Paper 2021/1226
Succinct LWE Sampling, Random Polynomials, and Obfuscation
Lalita Devadas, Willy Quach, Vinod Vaikuntanathan, 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.
Metadata
- Available format(s)
-
PDF
- Publication info
- A major revision of an IACR publication in TCC 2021
- Keywords
- Indistinguishability ObfuscationLearning with ErrorsLWE sampling
- Contact author(s)
-
lali @ mit edu
quach w @ northeastern edu
vinodv @ mit edu
hoeteck @ alum mit edu
wichs @ ccs neu edu - History
- 2021-10-18: revised
- 2021-09-20: received
- See all versions
- Short URL
- https://ia.cr/2021/1226
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1226,
author = {Lalita Devadas and Willy Quach and Vinod Vaikuntanathan and Hoeteck Wee and Daniel Wichs},
title = {Succinct {LWE} Sampling, Random Polynomials, and Obfuscation},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/1226},
year = {2021},
url = {https://eprint.iacr.org/2021/1226}
}
