Queries And Computations On Ciphertexts In The Cloud

With the rapid development of Mobile Internet and Internet of Things,the amount of data we produce is growing explosively.Because of the benefits of on-demand self-service,rapid elasticity and scalability,and the professional data analyzing services,more and more data owners(e.g.companies and organizations)are starting to use public clouds to store and process the data they generated or collected.However,the clouds managed by third-party cloud services providers cannot be fully trusted,and the outsourced data could be leaked due to inside or outside attacks,which can compromise data privacy.The most effective method of protecting data privacy in cloud computing is encryption,i.e.the data owners encrypt their data before outsourcing to the clouds.However,traditional encryption(e.g.AES)does not support queries and computations on ciphertexts,which limits the functionalities of cloud computing,while Fully Homomorphic Encryption is far from being practical.In this dissertation,we address some problems of queries and computations on ciphertexts in the cloud for different applications as follows.(1)Top-k Queries on Ciphertexts.The most efficient solution to top-k queries on ciphertexts is Order-Preserving Encryption(OPE).However,OPE leaks too much information(i.e.the orders of non-top-k values).To address this problem,we propose a Top Order-Preserving Encryption(TOPE)scheme,which enables top-1(min or max)queries on ciphertexts with minimized information leakage.Then we extend this TOPE to support top-k queries.With TOPE,the ciphertexts of top-k values are still the top-k in the ciphertext domain,while the ciphertexts of non-top-k values are in meaningless order.In addition,we formally define and prove the security of TOPE with IND-TOCPA,and conduct experiments to investigate its performance.The experimental results show that the search performance of top-k queries on TOPE ciphertexts is almost as fast as on the plaintexts.(2)Range Queries on Ciphertexts.Searchable Encryption(SE)enables an untrusted server to perform different queries on ciphertexts,such as keyword searches and range queries.To boost search time,most of the SE schemes leak access pattern.However,for the SE enabling range queries,by harnessing access pattern,an attacker can launch range injection attack to efficiently recover the encrypted index value of data.To address this problem,we propose an efficient mechanism,named Randex,to mitigate the range injection attacks against SE enables range queries.Specifically,we apply pre-encryption obfuscation by deploying Randomized Response,which obfuscates access pattern.Randex is compatible with any SE scheme supporting range queries.We formally prove that Randex achieves?-local differential privacy and analyze an attacker's guessing probability in range injection attack.The experimental results show that Randex can effectively mitigate range injection attacks,and render minimal tradeoffs to the correctness of range queries.For instance,with only 3.6% false negatives and no false positives,Randex can suppress an attacker's guessing probability to 0.17,which is significantly lower than the guessing probability of 1.0 without the privacy enhancement offered by Randex.(3)Reachability Computation on Encrypted Location Data.Location reachability,which indicates whether a person is reachable from another person through a sequence of locations obtained within a period of time,is of great importance in many applications,such as social behavior analysis and public health monitoring.We propose two novel schemes to compute reachability on encrypted location data on an untrusted cloud server.We first propose a basic scheme,named Sec Reach,which can compute 2-hop reachability on encrypted location data by applying Bloom filters and Somewhat Homomorphic Encryption(SWHE).Then,we design an advanced scheme,called Fast Reach,which can improve the computation efficiency by using Single Instruction Multiple Data(SIMD)technique and Z-order curve.We formally prove the security of the proposed schemes and implement them using HElib library.Compared to Sec Reach,Fast Reach boosts encryption time over 400 times and the computation time over 30 times.For instance,in the best case,Fast Reach only takes 1.2 seconds to compute a 2-hop reachability between two users in a system including 1,000 users.To the best of our knowledge,our work is the first solution to reachability computation on encrypted location data.