  Database users have started moving toward the use of cloud computing as a
service because it provides computation and storage needs at affordable prices.
However, for most of the users, the concern of privacy plays a major role as
they cannot control data access once their data are outsourced, especially if
the cloud provider is curious about their data. Data encryption is an effective
way to solve privacy concerns, but executing queries over encrypted data is a
problem that needs attention. In this research, we introduce a bit-based model
to execute different relational algebra operators over encrypted databases at
the cloud without decrypting the data. To encrypt data, we use the randomized
encryption algorithm (Advanced Encryption Standard-CBC) to provide the
maximum-security level. The idea is based on classifying attributes as
sensitive and non-sensitive, where only sensitive attributes are encrypted. For
each sensitive attribute, the table owner predefined the possible partition
domains on which the tuples will be encoded into bit vectors before the
encryption. We store the bit vectors in an additional column(s) in the
encrypted table in the cloud. We use those bits to retrieve only part of
encrypted records that are candidates for a specific query. We implemented and
evaluated our model and found that the proposed model is practical and success
to minimize the range of the retrieved encrypted records to less than 30
percent of the whole set of encrypted records in a table.
