Semantically secure order-revealing encryption: Multi-input functional encryption without obfuscation

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

89 Scopus citations

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 “bestpossible” 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings
EditorsMarc Fischlin, Elisabeth Oswald
PublisherSpringer Verlag
Pages563-594
Number of pages32
ISBN (Print)9783662468029
DOIs
StatePublished - Jan 1 2015
Externally publishedYes
Event34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015 - Sofia, Bulgaria
Duration: Apr 26 2015Apr 30 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9057
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015
CountryBulgaria
CitySofia
Period4/26/154/30/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Semantically secure order-revealing encryption: Multi-input functional encryption without obfuscation'. Together they form a unique fingerprint.

  • Cite this

    Boneh, D., Lewi, K., Raykova, M., Sahai, A., Zhandry, M., & Zimmerman, J. (2015). Semantically secure order-revealing encryption: Multi-input functional encryption without obfuscation. In M. Fischlin, & E. Oswald (Eds.), Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings (pp. 563-594). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9057). Springer Verlag. https://doi.org/10.1007/978-3-662-46803-6_19