Methods, systems, and computer program products for securely processing range predicates on cloud databases are provided herein. A computer-implemented method includes separately encrypting a set of plain text data using two or more encryption functions, thereby producing an encrypted domain comprising at least two distinct groups of encrypted data items; converting a range query over plain text data items into a query over at least one of the distinct groups of encrypted data items; and combining results from the query over the distinct groups of encrypted data items, thereby generating a final encrypted result to the range query.