Graduate Defense: Ning Shen

Dissertation Information

Title: Improve Security of Order-preserving Encryption and Its Applications in Data Outsourcing

Program: Doctor of Philosophy in Computing

Advisor: Dr. Jyh-haw Yeh, Computer Science

Committee Members: Dr. Gaby Dagher, Computer Science; and Dr. Liljana Babinkostova, Mathematics

Abstract

Encryption is an important tool to protect data confidentiality and privacy. One important practice of computation primitives is encrypting data with Order-Preserving Encryption (OPE). Order-Preserving Encryption is an encryption algorithm that allows the ciphertexts to preserve the same order of plaintext and it is very useful for range queries in databases and other applications. However, OPE has certain security vulnerabilities, such as it may leak sensitive information other than the ordering. Currently, the application of OPE is also limited, which is primary used in the encryption of outsourced databases.
Due to the OPE’s security concern and limited usage, this dissertation focuses on improving the security if OPE algorithm and extending OPE’s user scenarios to more applications. Chapter one gives an introduction to this research scope, as well as the research objectives and the contribution of the work. Chapter two gives the background of this research. It contains a synthesis of literature on the security of OPE algorithms and the backgrounds of the proposed areas where OPE can be applied. From Chapter three to Chapter five, I describe the three themes of my research in detail. To improve the security of the OPE algorithms, Chapter four presents a new practical and secure OPE algorithm. The new algorithm compensates for the security weakness while it remains efficient. To extend OPE to more applications, I propose two schemes which utilize OPE algorithms to solve real word problems in Chapter three and five. One scheme uses OPE to protect the completeness of outsourced databases, while the other one makes use of OPE to implement a privacy-preserving Location-Based Service (LBS) protocol which allows the clients to query the nearby Places of Interests (POIs). The two studies both outperform the existing approaches from different key metrics, which shows the contribution of the work. Chapter six presents a summary of the three studies, along with their practical implications and the areas that require further research.