Paper 2013/744

Functional Encryption and Property Preserving Encryption: New Definitions and Positive Results

Shashank Agrawal, Shweta Agrawal, Saikrishna Badrinarayanan, Abishek Kumarasubramanian, Manoj Prabhakaran, and Amit Sahai

Abstract

Functional Encryption (FE) is an exciting new paradigm that extends the notion of public key encryption. In this work we explore the security of Inner Product Functional Encryption schemes with the goal of achieving the highest security against practically feasible attacks. In addition, we improve efficiency/ underlying assumptions/ security achieved by existing inner product Functional Encryption and Property Preserving Encryption schemes, in both the private and public key setting. Our results can be summarized as follows: - We study whether known impossibilities for achieving strong SIM based security imply actual real world attacks. For this, we present a new UC-style SIM based definition of security that captures both data and function hiding, both public key and symmetric key settings and represents the "dream" security of FE. While known impossibilities rule out its achievability in the standard model, we show, surprisingly, that it can be achieved in the generic group model for Inner Product FE (Katz et al., Eurocrypt 2008). This provides evidence that FE implementations may enjoy extremely strong security against a large class of real world attacks, namely generic attacks. - We provide several improvements to known constructions of Inner Product FE. In the private key setting, the construction by Shen et al. (TCC 2009) was based on non-standard assumptions, used composite order groups, and only achieved selective security. We give the first construction of a symmetric key inner product FE which is built using prime order groups, and is fully secure under the standard DLIN assumption. Our scheme is more efficient in the size of key and ciphertext than Shen et al.'s, when the latter is converted to prime-order groups. - We give the first construction of a property preserving encryption (PPE) scheme for inner-products. Our scheme is secure under the DLIN assumption and satisfies the strongest definition of security -- Left-or-Right security in the standard model. Note that the only previously known construction for PPE by Pandey et al. (Eurocrypt 2012), which was claimed to be secure in the generic group model, was recently attacked Chatterjee and Das, making our construction the first candidate for PPE.

Note: Substantial revision. The relaxed simulation part of the paper has been removed due to technical issues. Also, the private-key functional encryption and property preserving encryption schemes given in the paper do not appear in the proceedings of PKC 2015.