Paper 2014/812

Search-and-compute on Encrypted Data

Jung Hee Cheon, Miran Kim, and Myungsun Kim

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 \textbf{search} and then \textbf{compute} over the encrypted databases \emph{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 \emph{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 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 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 (\textit{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. As a result, search queries including a conjunctive or disjunctive query on encrypted databases of $N$ tuples with $\mu$-bit attributes require $\bigo(N \log \mu)$ homomorphic operations with depth $\bigo(\log \mu)$ circuits. Search-and-compute queries, such as a conjunctive query with aggregate functions in the same conditions, are processed using $\bigo(\mu N)$ homomorphic operations with at most depth $\bigo(\log \mu \log N)$ circuits. Further, we can process search-and-compute queries using only $\bigo(N \log \mu)$ homomorphic operations with depth $\bigo(\log \mu)$ circuits, even in the large domain. Finally, we present various experiments by varying the parameters, such as the query type and the number of tuples.