With the many benefits of cloud computing, an entity may want to outsource its data and their related analytics tasks to a cloud. When data are sensitive, it is in the interest of the entity to outsource encrypted data to the cloud; however, this limits the types of operations that can be performed on the cloud side. Especially, evaluating queries over the encrypted data stored on the cloud without the entity performing any computation and without ever decrypting the data become a very challenging problem. In this paper, we propose solutions to conduct range queries over outsourced encrypted data. The existing methods leak valuable information to the cloud which can violate the security guarantee of the underlying encryption schemes. In general, the main security primitive used to evaluate range queries is secure comparison (SC) of encrypted integers. However, we observe that the existing SC protocols are not very efficient. To this end, we first propose a novel SC scheme that takes encrypted integers and outputs encrypted comparison result. We empirically show its practical advantage over the current state-of-the-art. We then utilize the proposed SC scheme to construct two new secure range query protocols. Our protocols protect data confidentiality, privacy of user's query, and also preserve the semantic security of the encrypted data; therefore, they are more secure than the existing protocols. Furthermore, our second protocol is lightweight at the user end, and it can allow an authorized user to use any device with limited storage and computing capability to perform the range queries over outsourced encrypted data.
In this paper, we do not consider the existing secure comparison protocols that are secure under the information theoretic setting. This is because, the existing secure comparison protocols under the information theoretic setting are commonly based on linear secret sharing schemes, such as Shamir's @cite_10 , which require at least three parties. We emphasize that our problem setting is entirely different than those methods since the data in our case are encrypted and our protocols require only two parties. Our protocols, which are based on additive homomorphic encryption schemes, are orthogonal to the secret sharing based SC schemes. Nevertheless, developing a PPRQ protocol by using the secret sharing based SC methods that protect the data access patterns is still an open problem; therefore, it can be treated as an interesting future work.
@cite_10
2141420453
In this paper we show how to divide data D into n pieces in such a way that D is easily reconstructable from any k pieces, but even complete knowledge of k - 1 pieces reveals absolutely no information about D . This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces.