Cryptology ePrint Archive: Report 2016/361

Functional Encryption for Bounded Collusions, Revisited

Shweta Agrawal and Alon Rosen

Abstract: We provide a new construction of functional encryption (FE) for circuits in the bounded collusion model. In this model, security of the scheme is guaranteed as long as the number of colluding adversaries can be a-priori bounded by some polynomial q. Compared to the previous best construction in this model, by Gorbunov, Vaikuntanathan and Wee (CRYPTO’12), our scheme has the following advantages:

• The ciphertext of our scheme can be divided into a succinct data dependent component and a non-succinct data independent component. This makes it well suited for optimization in an online-offline model that allows a majority of the computation to be performed in an offline phase, before the data becomes available. This is followed by an efficient online phase, which is performed when the data becomes known. The online component of our scheme significantly outperforms the online component of [GVW12], and depends only on the message size, whereas that of [GVW12] additionally depends on the circuit size and the number of queries.

• The ciphertext of our scheme is decomposable – namely, the data dependent component of the ciphertext CTx may be decomposed as CT_1, . . . , CT_|x|, where CT_i depends only on the bit x_i. Since our ciphertext enjoys both decomposability as well as succinctness of the online component, our scheme is very suitable for distributed data applications where the data to be encrypted is held by multiple, separated parties that share only a PRF seed.

• The ciphertext of our scheme grows as O(q^2), whereas that in [GVW12] grows as O(q^4). Security of our scheme is based on the Learning With Errors assumption (LWE) or its ring variant (Ring-LWE). We believe our techniques are of at least as much interest as our final result: our scheme makes progress towards building compact FE and hence indistinguishability obfuscation [LV16] from LWE. In more detail, it allows shifting the burden of computation from arbitrarily distributed data to well distributed noise via a new proof technique, which we call noisy functional encryption.

Category / Keywords: Functional Encryption, Learning with Errors, Online-Offline, Fully Homomorphic Encryption

Date: received 8 Apr 2016, last revised 26 Nov 2016

Contact author: shweta a at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20161126:113228 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]