Paper 2015/1113 Original: eprint.iacr.org/2015/1113 ↗

Multi-Input Functional Encryption with Unbounded-Message Security

Abstract

Multi-input functional encryption (MIFE) was introduced by Goldwasser \emph{et al.} (EUROCRYPT 2014) as a compelling extension of functional encryption. In MIFE, a receiver is able to compute a joint function of multiple, independently encrypted plaintexts. Goldwasser \emph{et al.} (EUROCRYPT 2014) show various applications of MIFE to running SQL queries over encrypted databases, computing over encrypted data streams, etc. The previous constructions of MIFE due to Goldwasser \emph{et al.} (EUROCRYPT 2014) based on indistinguishability obfuscation had a major shortcoming: it could only support encrypting an \emph{a priori bounded} number of message. Once that bound is exceeded, security is no longer guaranteed to hold. In addition, it could only support \emph{selective-security}, meaning that the challenge messages and the set of ``corrupted'' encryption keys had to be declared by the adversary up-front. In this work, we show how to remove these restrictions by relying instead on \emph{sub-exponentially secure} indistinguishability obfuscation. This is done by carefully adapting an alternative MIFE scheme of Goldwasser \emph{et al.} that previously overcame these shortcomings (except for selective security wrt.~the set of ``corrupted'' encryption keys) by relying instead on differing-inputs obfuscation, which is now seen as an implausible assumption. Our techniques are rather generic, and we hope they are useful in converting other constructions using differing-inputs obfuscation to ones using sub-exponentially secure indistinguishability obfuscation instead.