Multi-input Functional Encryption in the Private-Key Setting: Stronger Security from Weaker Assumptions

In terms of assumptions, the recent work of Asharov and Segev [7] shows that indistinguishability obfuscation and public-key functional encryption are significantly stronger primitives than private-key functional encryption. We refer the reader to Sect. 1.1 for a more elaborate discussion.

Bitansky and Vaikuntanathan [18] achieved the same result (an indistinguishability obfuscator) as [5] using a similar construction (at least conceptually) while relying essentially on the same assumptions. However, they construct an indistinguishability obfuscator directly without going through the equivalence to multi-input functional encryption schemes.

We consider a unified notion capturing both message privacy and function privacy not only as a useful feature for various applications. In fact, the function privacy of the resulting two-input scheme plays a crucial role when extending our results to more than two inputs.

A somewhat related functionality was recently considered by Iovino and Zebrowski [27] who introduced the notion of mergeable functional encryption, where one can publicly transform encryptions, \(\mathsf {Enc}(x)\) and \(\mathsf {Enc}(y)\), of two values into an encryption \(\mathsf {Enc}(x\Vert y)\) of their concatenation. They show how to construct such a scheme for two inputs building on the specific construction of [22] and assuming strong notions of obfuscation. In comparison, our approach applies to many inputs (as discussed below) and is based on minimal assumptions.

Notice that this is a randomized functionality. We will derandomize it using a PRF.

“One sided” here refers to the fact that the encapsulated key \(\mathsf {msk}^\mathsf {\star }\) is generated only from the side of the x’s.

Any two-input scheme can be used as a single-input scheme by simply ignoring one of its coordinates, and then one can apply the selective-to-adaptive transformation of Ananth et al. [3] for single-input schemes.

More accurately, the key \(\mathsf {msk}^\mathsf {\star }\) is computed by applying the setup algorithm of \(\mathsf {1FE}\) with randomness \(\mathsf {PRF}(s,t)\).

Indeed, [5] get a construction of a t-input scheme for any \(t\ge 1\) which implies an indistinguishability obfuscator. Our construction falls short from being generalized to such extent (however, it relies on weaker assumptions).