  Despite extensive research on cryptography, secure and efficient query
processing over outsourced data remains an open challenge. This paper continues
along with the emerging trend in secure data processing that recognizes that
the entire dataset may not be sensitive, and hence, non-sensitivity of data can
be exploited to overcome limitations of existing encryption-based approaches.
We, first, provide a new security definition, entitled partitioned data
security for guaranteeing that the joint processing of non-sensitive data (in
cleartext) and sensitive data (in encrypted form) does not lead to any leakage.
Then, this paper proposes a new secure approach, entitled query binning (QB)
that allows secure execution of queries over non-sensitive and sensitive parts
of the data. QB maps a query to a set of queries over the sensitive and
non-sensitive data in a way that no leakage will occur due to the joint
processing over sensitive and non-sensitive data. In particular, we propose
secure algorithms for selection, range, and join queries to be executed over
encrypted sensitive and cleartext non-sensitive datasets. Interestingly, in
addition to improving performance, we show that QB actually strengthens the
security of the underlying cryptographic technique by preventing size,
frequency-count, and workload-skew attacks.
