Description
TitleOrder-revealing encryption: new constructions and barriers
Date Created2020
Other Date2020-10 (degree)
Extent1 online resource (viii, 133 pages) : illistrations
DescriptionOrder-revealing encryption (ORE) is a symmetric encryption scheme that gives a public procedure by which two ciphertexts can be compared to reveal the order of their underlying plaintexts. ORE is a very popular primitive for outsourcing databases and has seen deployments in products and usage in applied research, as it allows for efficiently performing range queries over encrypted data. However, a series of works, starting with Naveed emph{et al.} (CCS 2015), have shown that when the adversary has a good estimate of the distribution of the data, ORE provides little protection.
In this dissertation, we present our works on order-revealing encryption, which include novel security notions, new constructions, and barriers. First, we consider the best-possible security notion for ORE (ideal ORE), which means that, given the ciphertexts, emph{only} the order is revealed --- anything else, such as the distance between plaintexts, is hidden. Despite the fact that this notion provides the best security for ORE, the only known constructions of ideal ORE are based on cryptographic multilinear maps and are currently too impractical for real-world applications. In this work, we give evidence that building ideal ORE from weaker tools is hard. Essentially, we show black-box separations between ideal ORE and most symmetric-key primitives, as well as public-key encryption and anything else implied by generic group model in a black-box way. This result tells us that any construction of ORE must either (1) achieve weaker notions of security, (2) be based on more complicated cryptographic tools, or (3) require non-black-box techniques thus it suggests that any ORE achieving ideal security will likely be at least somewhat inefficient.
Then we propose a new meaningful security notion--- extit{parameter-hiding}. In our definition, we consider the case that the database entries are drawn identically and independently from the distribution of known shape, but for which the mean and variance are not (and thus the attacks of Naveed et al. do not apply). We say an ORE is parameter-hiding, if for any probabilistic and polynomial-time adversary, given any sequence (polynomial-size) of ciphertexts, the mean and variance of the message distribution are hidden. Based on this notion, we build the corresponding construction of ORE that satisfying it from a bi-linear map.
Next, we study a particular case of ORE, which is called order-preserving encryption. OPE schemes are the subset of ORE schemes for which the ciphertexts themselves are numerical values that can be compared naturally. For OPE, we study its ciphertext length under the security notion proposed by Chenette et al. for OPE (FSE 2016); their notion says that the comparison of two ciphertexts should only leak the index of the most significant bit on which they differ (MSDB-secure). In their work, they propose two constructions, both ORE and OPE; the ORE scheme has very short ciphertexts that only expand the plaintext by a factor approx 1.58, while the ciphertext-size of the OPE scheme expands the plaintext by a security-parameter factor. We give evidence that this gap between ORE and OPE is inherent, by proving that emph{any} OPE meeting the information-theoretic version of their security definition (for instance, in the random oracle model) must have the ciphertext length close to that of their constructions.
NotePh.D.
NoteIncludes bibliographical references
Genretheses, ETD doctoral
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Statistical Profile