Paper Info
Title
Order-preserving encryption revisited: improved security analysis and alternative solutions
Abstract
We further the study of order-preserving symmetric encryption (OPE), a primitive for allowing efficient range queries on encrypted data, recently initiated (from a cryptographic perspective) by Boldyreva et al. (Eurocrypt'09). First, we address the open problem of characterizing what encryption via a random order-preserving function (ROPF) leaks about underlying data (ROPF being the "ideal object" in the security definition, POPF, satisfied by their scheme.) In particular, we show that, for a database of randomly distributed plaintexts and appropriate choice of parameters, ROPF encryption leaks neither the precise value of any plaintext nor the precise distance between any two of them. The analysis here is quite technically non-trivial and introduces useful new techniques. On the other hand, we also show that ROPF encryption does leak both the value of any plaintext as well as the distance between any two plaintexts to within a range of possibilities roughly the square root of the domain size. We then study schemes that are not order-preserving, but which nevertheless allow efficient range queries and achieve security notions stronger than POPF. In a setting where the entire database is known in advance of key-generation (considered in several prior works), we show that recent constructions of "monotone minimal perfect hash functions" allow to efficiently achieve (an adaptation of) the notion of IND-O(rdered) CPA also considered by Boldyreva et al., which asks that only the order relations among the plaintexts is leaked. Finally, we introduce modular order-preserving encryption (MOPE), in which the scheme of Boldyreva et al. is prepended with a shift cipher. MOPE improves the security of OPE in a sense, as it does not leak any information about plaintext location. We clarify that our work should not be interpreted as saying the original scheme of Boldyreva et al., or the variants that we introduce, are "secure" or "insecure." Rather, the goal of this line of research is to help practitioners decide whether the options provide a suitable security-functionality tradeoff for a given application.
Year
DOI
Venue
2011
10.1007/978-3-642-22792-9_33
IACR Cryptology ePrint Archive
Keywords
DocType
Volume
improved security analysis,security notion,plaintext location,security definition,original scheme,alternative solution,efficient range query,modular order-preserving encryption,ropf encryption,random order-preserving function,symmetric encryption,ropf encryption leak,range queries,hypergeometric distribution
Conference
2012
ISSN
Citations 
PageRank 
0302-9743
179
4.90
References 
Authors
35
3
Search Limit
100179
Name
Order
Citations
PageRank
Alexandra Boldyreva12297114.80
Nathan Chenette253117.37
Adam O'Neill377630.96