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.
As an independent work, @cite_3 developed a new prototype to execute SQL queries by leveraging server-hosted tamper-proof trusted hardware in critical query processing stages. However, their work still reveals data access patterns to the server. Recently, @cite_11 proposed a new PPRQ protocol by utilizing the secure comparison (SC) protocol in @cite_2 as the building block. Perhaps, their method is the most closely related work to the protocols proposed in this paper. However, the SC protocol in @cite_2 operates on encrypted bits rather than on encrypted integers; therefore, the overall throughput in their protocol is less. In addition, their protocol leaks data access patterns to the cloud service provider.
@cite_2 @cite_3 @cite_11
2104145890 2042012257 1998853617
We consider the problem of securely evaluating the Greater Than (GT) predicate and its extension - transferring one of two secrets, depending on the result of comparison. We generalize our solutions and show how to securely decide membership in the union of a set of intervals. We then consider the related problem of comparing two encrypted numbers. We show how to efficiently apply our solutions to practical settings, such as auctions with the semi-honest auctioneer, proxy selling, etc. All of our protocols are one round. We propose new primitives, Strong Conditional Oblivious Transfer (SCOT) and Conditional En- crypted Mapping (CEM), which capture common security properties of one round protocols in a variety of settings, which may be of independent interest. TrustedDB is an outsourced database prototype that allows clients to execute SQL queries with privacy and under regulatory compliance constraints without having to trust the service provider. TrustedDB achieves this by leveraging server-hosted tamper-proof trusted hardware in critical query processing stages. TrustedDB does not limit the query expressiveness of supported queries. And, despite the cost overhead and performance limitations of trusted hardware, the costs per query are orders of magnitude lower than any (existing or) potential future software-only mechanisms. TrustedDB is built and runs on actual hardware, and its performance and costs are evaluated here. With the growing popularity of data and service outsourcing, where the data resides on remote servers in encrypted form, there remain open questions about what kind of query operations can be performed on the encrypted data. In this paper, we focus on one such important query operation, namely range query. One of the basic security primitive that can be used to evaluate range queries is secure comparison of encrypted integers. However, the existing secure comparison protocols strongly rely on the encrypted bit-wise representations rather than on pure encrypted integers. Therefore, in this paper, we first propose an efficient method for converting an encrypted integer z into encryptions of the individual bits of z. We then utilize the proposed security primitive to construct a new protocol for secure evaluation of range queries in the cloud computing environment. Furthermore, we empirically show the efficiency gains of using our security primitive over existing method under the range query application.