Paper 2016/622

Function-Revealing Encryption

Marc Joye and Alain Passelègue

Abstract

Multi-input functional encryption is a paradigm that allows an authorized user to compute a certain function ---and nothing more--- over multiple plaintexts given only their encryption. The particular case of two-input functional encryption has very exciting applications like comparing the relative order of two plaintexts from their encrypted form, making range queries over an encrypted database, testing if two encrypted databases share common entries, and more. While being extensively studied, multi-input functional encryption is not ready for a practical deployment, mainly for two reasons. First, known constructions rely on heavy cryptographic tools such as multilinear maps. Second, their security is still very uncertain, as revealed by recent devastating attacks. This paper investigates a simpler approach. Rather than addressing multi-input functional encryption in its full generality, we target specific functions and relax the security notions. As a result, we obtain several practical realizations of multi-input encryption for specialized applications, including an efficient construction of order-revealing encryption with limited leakage, under the standard DLin assumption.