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 . Our construction supports arithmetic circuits as against Boolean circuits, which have been the focus of all prior work. The ciphertext of our scheme is sublinear in the circuit size for the circuit class NC_1 when based on Ring LWE and any constant depth when based on standard LWE. This gives the first constructions of arithmetic reusable garbled circuits. Additionally, our construction achieves several desirable features: • Our construction for reusable garbled circuits for NC 1 achieves the optimal “full” simulation based security. • When generalised to handle Q queries for any fixed polynomial Q, our ciphertext size grows additively with Q^2 . Such query dependence on ciphertext size has only been achieved in a weaker security game otherwise [Agr17]. • 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. Security of our scheme may be based on the Learning With Errors assumption (LWE) or its ring variant (Ring-LWE). To achieve our result, we provide new public key and ciphertext evaluation algorithms in the context of functional encryption. These algorithms are general, and may find application elsewhere.