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.
Category / Keywords: applications / encrypted databases, private query processing, homomorphic encryption. Date: received 8 Oct 2014 Contact author: alfks500 at snu ac kr Available format(s): PDF | BibTeX Citation Version: 20141011:235048 (All versions of this report) Short URL: ia.cr/2014/812 Discussion forum: Show discussion | Start new discussion