We construct the first implementable encryption system supporting greater-than comparisons on encrypted data that provides the "best-possible" semantic security. In our scheme there is a public algorithm that given two ciphertexts as input, reveals the order of the corresponding plaintexts and nothing else. Our constructions are inspired by obfuscation techniques, but do not use obfuscation. For example, to compare two 16-bit encrypted values (e.g., salaries or age) we only need a 9-way multilinear map. More generally, comparing $k$-bit values requires only a $(k/2+1)$-way multilinear map. The required degree of multilinearity can be further reduced, but at the cost of increasing ciphertext size.
Beyond comparisons, our results give an implementable secret-key multi-input functional encryption scheme for functionalities that can be expressed as (generalized) branching programs of polynomial length and width. Comparisons are a special case of this class, where for $k$-bit inputs the branching program is of length $k+1$ and width $4$.
Category / Keywords: functional encryption, multilinear maps Original Publication (with minor differences): IACR-EUROCRYPT-2015 Date: received 13 Oct 2014, last revised 25 May 2015 Contact author: jzim at cs stanford edu Available format(s): PDF | BibTeX Citation Version: 20150526:025351 (All versions of this report) Short URL: ia.cr/2014/834 Discussion forum: Show discussion | Start new discussion