Our main result is that, assuming LWE, {\em black-box constructions} of {\em sufficiently succinct} FE schemes from constant-degree graded encodings can be transformed to rely on a much better-understood object --- {\em bilinear groups}. In particular, under an {\em \"{u}ber assumption} on bilinear groups, such constructions imply IO in the plain model. The result demonstrates that the exact level of ciphertext succinctness of FE schemes is of major importance. In particular, we draw a fine line between known FE constructions from constant-degree graded encodings, which just fall short of the required succinctness, and the holy grail of basing IO on better-understood assumptions.
In the heart of our result, are new techniques for removing ideal graded encoding oracles from FE constructions. Complementing the result, for weaker ideal models, namely the generic-group model and the random-oracle model, we show a transformation from {\em collusion-resistant} FE in either of the two models directly to FE (and IO) in the plain model, without assuming bilinear groups.
Category / Keywords: foundations / functional-encryption, obfuscation, graded-encodings, bilinear-groups Original Publication (with minor differences): IACR-EUROCRYPT-2017 Date: received 4 Oct 2016, last revised 7 Apr 2017 Contact author: nirbitan at csail mit edu Available format(s): PDF | BibTeX Citation Version: 20170407:203814 (All versions of this report) Short URL: ia.cr/2016/962