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 \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.
Category / Keywords: public-key cryptography / Date: received 28 Aug 2020, last revised 1 Sep 2020 Contact author: danwichs at gmail com Available format(s): PDF | BibTeX Citation Version: 20200901:153847 (All versions of this report) Short URL: ia.cr/2020/1042