Abstract
Order-preserving encryption can help perform many kinds of queries such as range queries on encrypted databases. Popa et al. presented the first order-preserving encryption scheme that achieved ideal security, but their insertion cost is very high. Kerschbaum et al. presented another ideal-secure order-preserving encryption scheme, which can effectively reduce the communication cost when inserting ciphertexts into the server. However, their scheme is not applicable to many kinds of data sets. In this thesis, we proposed a novel order-preserving encryption scheme. Not only can our proposed scheme maintain the communication cost at O(n), but it can also reduce the encryption cost from O(n^3/logn) to O(n^2 ) in the worst case. Simulation shows that the performance of inserting ordered data can be significantly improved at least by 90%, and the performance of inserting random data can be improved by about 11% on average.