Methods, systems, and computer program products for a secure database-as-a-service are provided herein. A computer-implemented method includes obtaining, by a database service, data associated with one or more client devices to be stored in at least one encrypted database; encrypting, without mutation and in accordance with one or more security requirements, at least a portion of the data using an order preserving encryption scheme, wherein the encrypting comprises (i) computing a set of encryption parameters for the portion of the data and (ii) applying a process that converts a fixed-length cipher text corresponding to the portion of the data to a variable-length cipher text; and storing the encrypted data in the at least one encrypted database, wherein the database service enables one or more indexes to be built over the encrypted data to improve performance of query processing.