Using bitmaps for executing range queries in encrypted databases

Privacy of data stored at un-trusted servers is an important problem of today. A solution to this problem can be achieved by encrypting the outsourced data, but simple encryption does not allow efficient query processing. In this paper we propose a novel scheme for encrypting relational databases so that range queries can be efficiently executed on the encrypted data. We formally define the syntax and security of the problem and specify a scheme called ESRQ1. ESRQ1 uses a deterministic encryption scheme along with bitmap indices to encrypt a relational database. We provide details of the functionality of ESRQ1 and prove its security in the specified model.