Paper 2012/474

On the Semantic Security of Functional Encryption Schemes

Manuel Barbosa and Pooya Farshim

Abstract

Functional encryption (FE) is a powerful cryptographic primitive that generalizes many asymmetric encryption systems proposed in recent years. Syntax and security definitions for general FE were recently proposed by Boneh, Sahai, and Waters (BSW) (TCC 2011) and independently by O'Neill (ePrint 2010/556). In this paper we revisit these definitions, identify several shortcomings in them, and propose a new definitional approach that overcomes these limitations. Our definitions display good compositionality properties and allow us to obtain new feasibility and impossibility results for adaptive token-extraction attack scenarios that shed further light on the potential reach of general FE for practical applications. The main contributions of the paper are the following: - We show that the BSW definition of semantic security fails to reject intuitively insecure FE schemes where a ciphertext leaks more about an encrypted message than that which can be recovered from an image under the supported functionality. Our definition (as O'Neill's) does not suffer from this problem. - We introduce an orthogonal notion of \emph{setup security} that rejects all FE schemes where the master secret key may give unwanted power to the TA, allowing the recovery of extra information from images under the supported functionality. We prove FE schemes supporting \emph{all-or-nothing} functionalities are intrinsically setup-secure and further show that many well-known functionalities \emph{are} all-or-nothing. - We extend the equivalence result of O'Neill between indistinguishability and semantic security to restricted \emph{adaptive} token-extraction attacks (the standard notion of security for, e.g., IBE and ABE schemes). We establish that this equivalence holds for the large class of all-or-nothing functionalities. Conversely, we show that the proof technique used to establish this equivalence cannot be applied to schemes supporting a one-way function. - We show that the notable \emph{inner-product} functionality introduced by Katz, Sahai, and Waters (EUROCRYPT 2008) can be used to encode a one-way function under the Small Integer Solution (SIS) problem, and hence natural approaches to prove its (restricted) adaptive security fail. This complements the equivalence result of O'Neill for the non-adaptive case, and leaves open the question of proving the semantic security of existing inner-product encryption schemes.