Candidate Obfuscation via Oblivious LWE Sampling

Hoeteck Wee and Daniel Wichs

Abstract

We present a new, simple candidate construction of indistinguishability obfuscation (iO). Our scheme is inspired by lattices and learning-with-errors (LWE) techniques, but we are unable to prove security under a standard assumption. Instead, we formulate a new falsifiable assumption under which the scheme is secure. Furthermore, the scheme plausibly achieves post-quantum security. Our construction is based on the recent "split FHE" framework of Brakerski, Döttling, Garg, and Malavolta (EUROCRYPT '20), and we provide a new instantiation of this framework. As a first step, we construct an iO scheme that is provably secure assuming that LWE holds \emph{and} that it is possible to obliviously generate LWE samples without knowing the corresponding secrets. We define a precise notion of oblivious LWE sampling that suffices for the construction. It is known how to obliviously sample from any distribution (in a very strong sense) using iO, and our result provides a converse, showing that the ability to obliviously sample from the specific LWE distribution (in a much weaker sense) already also implies iO. As a second step, we give a heuristic contraction of oblivious LWE sampling. On a very high level, we do this by homomorphically generating pseudoradnom LWE samples using an encrypted pseudorandom function.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
Contact author(s)
danwichs @ gmail com
History
2021-03-04: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/1042

CC BY

BibTeX

@misc{cryptoeprint:2020/1042,
author = {Hoeteck Wee and Daniel Wichs},
title = {Candidate  Obfuscation via Oblivious LWE Sampling},
howpublished = {Cryptology ePrint Archive, Paper 2020/1042},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1042}},
url = {https://eprint.iacr.org/2020/1042}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.