Dual Encryption for Query Integrity Assurance

In database outsourcing, an enterprise contracts its database management tasks to an outside database service provider to eliminate in-house hardware, software, and expertise needs for running DBMSs. This represents an attractive paradigm, especially for parties with limited abilities in managing their own data. Typically, the client applications want to obtain quality assurance (e.g., data authenticity and query completeness) of the outsourced database service at a low cost. Previous work on database outsourcing has focused on issues such as communication overhead, secure data access, and data privacy. Recent work has introduced the issue of query integrity assurance, but usually, to obtain such assurance incurs a high cost. In this paper, we present a new method called dual encryption to provide low-cost query integrity assurance for outsourced database services. Dual encryption enables “cross examination” of the outsourced data, which consists of the original data stored under a certain encryption scheme, and another small percentage of the original data stored under a different encryption scheme. We generate queries against the additional piece of data and analyze their results to obtain integrity assurance. Our scheme is provable secure, that is, it is impossible to break our scheme unless some security primitives can be broken. Experiments on commercial workloads show the effectiveness of our approach.

By: Haixun Wang; Jian Yin; Chang-Shing Perng; Philip S. Yu

Published in: RC24300 in 2007


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .