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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2021/1226}},
      url = {https://eprint.iacr.org/2021/1226}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.