Abstract With the advent of cloud computing, individuals and organizations have become interested in moving their databases from local to remote cloud servers. However, data owners and cloud service providers are not in the same trusted domain in practice. For the protection of data privacy, sensitive data usually have to be encrypted before outsourcing, which makes effective database utilization a very challenging task. To address this challenge, in this paper, we propose L-EncDB, a novel lightweight encryption mechanism for database, which (i) keeps the database structure and (ii) supports efficient SQL-based queries. To achieve this goal, a new format-preserving encryption (FPE) scheme is constructed in this paper, which can be used to encrypt all types of character strings stored in database. Extensive analysis demonstrates that the proposed L-EncDB scheme is highly efficient and provably secure under existing security model.