The growing number of data privacy breaches and associated financial losses have driven the demand for private database queries. Clients typically submit queries that involve both search and computation operations, su...
详细信息
The growing number of data privacy breaches and associated financial losses have driven the demand for private database queries. Clients typically submit queries that involve both search and computation operations, such as counting students under a certain age or calculating the BMI of employees above a specific age. Existing protocols often face limitations due to reliance on specific-purpose encryption schemes or multiple communication rounds between clients and servers. In this work, we present a unified framework utilizing fully homomorphic encryption techniques to efficiently and privately process queries with search and computation operations. Our contributions include a homomorphic encryption-based private comparison algorithm, called the layered comparison algorithm, which achieves a 2.6-6.6X performance improvement compared to algorithms from prior work;a fast Fourier transform-based preprocessing method enabling accurate large integer arithmetic operations in the encrypted domain;and a scalable database encoding method. Evaluation results demonstrate the practicality of our system, as it processes an aggregated query for a 1k-row encrypted database in approximately 4.53 seconds.
privateprocessing of database queries protects the confidentiality of sensitive data when queries are answered. It is important to design collusion-resistant protocols ensuring that privacy remains protected even whe...
详细信息
privateprocessing of database queries protects the confidentiality of sensitive data when queries are answered. It is important to design collusion-resistant protocols ensuring that privacy remains protected even when a certain number of honest-but-curious participants collude to share their knowledge in order to gain unauthorised access to sensitive information. A novel setting arises when aggregated queries need to be answered for a large distributed database, but legal requirements or commercial interests forbid making access to records in each subdatabase available to other counterparts. For example, a very large number of medical records may be stored in a distributed database, which is a union of several separate databases from different hospitals, or even from different countries. The present article introduces and investigates two protocols for collusion-resistant privateprocessing of aggregated queries in this novel setting: Accelerated Multi-round Iterative Protocol (AMIP) and Restricted Multi-round Iterative Protocol (RMIP). We define a large collection of query functions and show that AMIP and RMIP protocols can answer all queries in this collection. Our experiments demonstrate that the AMIP protocol outperforms all other applicable algorithms, and this achievement is especially significant in terms of the communication complexity.
private query processing on encrypted databases allows users to obtain data from encrypted databases in such a way that the users' sensitive data will be protected from exposure. Given an encrypted database, users...
详细信息
private query processing on encrypted databases allows users to obtain data from encrypted databases in such a way that the users' sensitive data will be protected from exposure. Given an encrypted database, users typically submit queries similar to the following examples: 1) How many employees in an organization make over U.S. $100000? 2) What is the average age of factory workers suffering from leukemia? Answering the questions requires one to search and then compute over the relevant encrypted data sets in sequence. In this paper, we are interested in efficiently processing queries that require both operations to be performed on fully encrypted databases. One immediate solution is to use several special-purpose encryption schemes simultaneously;however, this approach is associated with a high computational cost for maintaining multiple encryption contexts. Another solution is to use a privacy homomorphic scheme. However, no secure solutions have been developed that satisfy the efficiency requirements. In this paper, we construct a unified framework to efficiently and privately process queries with search and compute operations. For this purpose, the first part of our work involves devising several underlying circuits as primitives for queries on encrypted data. Second, we apply two optimization techniques to improve the efficiency of these circuit primitives. One technique involves exploiting single-instruction-multiple-data (SIMD) techniques to accelerate the basic circuit operations. Unlike general SIMD approaches, our SIMD implementation can be applied even to a single basic operation. The other technique is to use a large integer ring (e.g., Z(2)t) as a message space rather than a binary field. Even for an integer of k bits with k > t, addition can be performed using degree 1 circuits with lazy carry operations. Finally, we present various experiments performed by varying the considered parameters, such as the query type and the number of tuples.
private query processing on encrypted databases allows users to obtain data from encrypted databases in such a way that the user's sensitive data will be protected from exposure. Given an encrypted database, the u...
详细信息
ISBN:
(数字)9783662480519
ISBN:
(纸本)9783662480519;9783662480502
private query processing on encrypted databases allows users to obtain data from encrypted databases in such a way that the user's sensitive data will be protected from exposure. Given an encrypted database, the users typically submit queries similar to the following examples: - How many employees in an organization make over $100,000? - What is the average age of factory workers suffering from leukemia? Answering the above questions requires one to search and then compute over the encrypted databases in sequence. In the case of privately processing queries with only one of these operations, many efficient solutions have been developed using a special-purpose encryption scheme (e.g., searchable encryption). In this paper, we are interested in efficiently processing queries that need to perform both operations on fully encrypted databases. One immediate solution is to use several special-purpose encryption schemes at the same time, but this approach is associated with a high computational cost for maintaining multiple encryption contexts. The other solution is to use a privacy homomorphic scheme. However, no secure solutions have been developed that meet the efficiency requirements. In this work, we construct a unified framework so as to efficiently and privately process queries with "search" and "compute" operations. To this end, the first part of our work involves devising some underlying circuits as primitives for queries on encrypted data. Second, we apply two optimization techniques to improve the efficiency of the circuit primitives. One technique is to exploit SIMD techniques to accelerate their basic operations. In contrast to general SIMD approaches, our SIMD implementation can be applied even when one basic operation is executed. The other technique is to take a large integer ring(e.g., Z(2)t) as a message space instead of a binary field. Even for an integer of k bits with k > t, addition can be performed with degree 1 circuits with lazy carry operations. F
queryprocessing that preserves both the data privacy of the owner and the query privacy of the client is a new research problem. It shows increasing importance as cloud computing drives more businesses to outsource t...
详细信息
ISBN:
(纸本)9781424489589
queryprocessing that preserves both the data privacy of the owner and the query privacy of the client is a new research problem. It shows increasing importance as cloud computing drives more businesses to outsource their data and querying services. However, most existing studies, including those on data outsourcing, address the data privacy and query privacy separately and cannot be applied to this problem. In this paper, we propose a holistic and efficient solution that comprises a secure traversal framework and an encryption scheme based on privacy homomorphism. The framework is scalable to large datasets by leveraging an index-based approach. Based on this framework, we devise secure protocols for processing typical queries such as k-nearest-neighbor queries (kNN) on R-tree index. Moreover, several optimization techniques are presented to improve the efficiency of the queryprocessing protocols. Our solution is verified by both theoretical analysis and performance study.
暂无评论