International Association for Cryptologic Research

International Association
for Cryptologic Research


Candidate Obfuscation via Oblivious LWE Sampling

Hoeteck Wee , NTT Research Inc., USA
Daniel Wichs , Northeastern University and NTT Research Inc. USA
DOI: 10.1007/978-3-030-77883-5_5 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
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\"ottling, 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 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 pseudorandom LWE samples using an encrypted pseudorandom function.
Video from EUROCRYPT 2021
  title={Candidate Obfuscation via Oblivious LWE Sampling},
  author={Hoeteck Wee and Daniel Wichs},