You are looking at a specific version 20161126:113228 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Functional EncryptionLearning with ErrorsOnline-OfflineFully Homomorphic Encryption
Contact author(s)
shweta a @ gmail com
History
2017-09-14: last of 14 revisions
2016-04-11: received
See all versions
Short URL
https://ia.cr/2016/361
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.