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 c
- PDF / 777,341 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 19 Downloads / 213 Views
2
IIT Madras, Chennai, India [email protected] Efi Arazi School of Computer Science, IDC Herzliya, Herzliya, Israel [email protected]
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 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.
1
Introduction
Functional encryption (FE) [52,53] generalizes public key encryption to allow fine grained access control on encrypted data. In functional encryption, a secret key SKf corresponds to a function f , and a ciphertext CTx corresponds to some input x from the domain of f . Given SKf and CTx , functionality posits that the c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 173–205, 2017. https://doi.org/10.1007/978-3-319-70500-2_7
174
S. Agrawal and A. Rosen
user may run the decryption procedure to learn the value f (x), while security guarantees that nothing about x beyond f (x) can be learned. Recent years have witnessed significant progress towards constructing functional encryption for advanced functionalities [3,4,11,13,15,16,21,25,31,32,35, 40–42,45,46,54]. However, for the most general notion of functional encryption – one that allows the evaluation of arbitrary efficient functions and is secure against general adversaries, the only known constructions rely on indistinguishability obfuscation (iO) [31] or on the existence of multilinear maps [33]. For full-fledged functional encryption, reliance on such strong primitives is not a co-incidenc
Data Loading...
