Search-and-compute on Encrypted Data.
Jung Hee Cheon, Miran Kim, Myungsun Kim · 2014
Abstract. 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 encryp-tion contexts. The other solution is to use a privacy homomorphism (or fully homomorphic encryption) 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