Paper 2014/812
Searchandcompute 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 specialpurpose 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 specialpurpose 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. Searchandcompute 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 searchandcompute 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.
Metadata
 Available format(s)
 Category
 Applications
 Publication info
 Preprint. MINOR revision.
 Keywords
 encrypted databasesprivate query processinghomomorphic encryption.
 Contact author(s)
 alfks500 @ snu ac kr
 History
 20141011: received
 Short URL
 https://ia.cr/2014/812
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/812, author = {Jung Hee Cheon and Miran Kim and Myungsun Kim}, title = {Searchandcompute on Encrypted Data}, howpublished = {Cryptology {ePrint} Archive, Paper 2014/812}, year = {2014}, url = {https://eprint.iacr.org/2014/812} }