TY - GEN
T1 - Semantically secure order-revealing encryption
T2 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2015
AU - Boneh, Dan
AU - Lewi, Kevin
AU - Raykova, Mariana
AU - Sahai, Amit
AU - Zhandry, Mark
AU - Zimmerman, Joe
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84942636663&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84942636663&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-46803-6_19
DO - 10.1007/978-3-662-46803-6_19
M3 - Conference contribution
AN - SCOPUS:84942636663
SN - 9783662468029
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 563
EP - 594
BT - Advances in Cryptology - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Proceedings
A2 - Fischlin, Marc
A2 - Oswald, Elisabeth
PB - Springer Verlag
Y2 - 26 April 2015 through 30 April 2015
ER -