Cryptology ePrint Archive: Report 2014/834

Semantically Secure Order-Revealing Encryption: Multi-Input Functional Encryption Without Obfuscation

Dan Boneh and Kevin Lewi and Mariana Raykova and Amit Sahai and Mark Zhandry and Joe Zimmerman

Abstract: Deciding "greater-than" relations among data items just given their encryptions is at the heart of search algorithms on encrypted data, most notably, non-interactive binary search on encrypted data. Order-preserving encryption provides one solution, but provably provides only limited security guarantees. Two-input functional encryption is another approach, but requires the full power of obfuscation machinery and is currently not implementable.

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


[ Cryptology ePrint archive ]