Paper 2015/103

Mergeable Functional Encryption

Vincenzo Iovino and Karol Zebrowski

Abstract

In recent years, there has been great interest in Functional Encryption (FE), a generalization of traditional encryption where a token enables a user to learn a specific function of the encrypted data and nothing else. In this paper we put forward a new generalization of FE that we call Mergeable FE (mFE). In a mFE system, given a ciphertext $c_1$ encrypting $m_1$ and a ciphertext $c_2$ encrypting $m_2$, it is possible to produce in an oblivious way (i.e., given only the public-key and without knowledge of the messages, master secret-key or any other auxiliary information) a ciphertext encrypting the string $m_1||m_2$ under the security constraint that this new ciphertext does not leak more information about the original messages than what may be leaked from the new ciphertext using the tokens. For instance, suppose that the adversary is given the token for the function $f(\cdot)$ defined so that for strings $x\in\zu^n$, $f(x)=g(x)$ for some function $g:\zu^n\rightarrow\zu$ and for strings $y=(x_1||x_2)\in\zu^{2n}$, $f(x_1||x_2)=g(x_1) \vee g(x_2)$. Furthermore, suppose that the adversary gets a ciphertext $c$ encrypting $(x_1||x_2)$ that is the result of ``merging`` some ciphertexts $c_1$ and $c_2$ encrypting respectively $x_1$ and $x_2$, and suppose that the token for $f$ evaluates to $1$ on $c$. Then, the security of mFE guarantees that the adversary only learns the output $f(x_1,x_2) = g(x_1) OR g(x_2)=1$ and nothing else (e.g., the adversary should not learn whether $g(x_1)=1 or g(x_2)=1$). This primitive is in some sense FE with the ``best possible`` homomorphic properties and, besides being interesting in itself, it offers wide applications. For instance, it has as special case multi-inputs FE and thus indistinguishability obfuscation (iO) and extends the latter to support more efficiently homomorphic and re-randomizable properties. We construct mFE schemes supporting a single merging operation, one from indistinguishability obfuscation for Turing machines and one for messages of unbounded length from public-coin differing-inputs obfuscation. Finally, we discuss a construction supporting unbounded merging operations from new assumptions.