Functional Encryption for Bounded Collusions, Revisited

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 in contrast to all prior work which support Boolean circuits. The ciphertext of our scheme is sublinear in the circuit size for the circuit class NC1; this implies the first construction of arithmetic reusable garbled circuits for NC1. Additionally, our construction achieves several desirable features: - Our construction for reusable garbled circuits for NC1 achieves the optimal "full" simulation based security. - When generalised to handle Q queries for any fixed polynomial Q, our ciphertext size grows additively with Q2. In contrast, previous works that achieve full security [5,39] suffered a multiplicative growth of Q4. - 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 reusable garbled circuits construction for NC1 is based on the Ring Learning With Errors assumption (RLWE), while the bounded collusion construction (with non-succinct ciphertext) may also be based on the standard Learning with Errors (LWE) assumption. To achieve our result, we provide new public key and ciphertext evaluation algorithms. These algorithms are general, and may find application elsewhere.