Article Preview
Top1. Introduction
Recently, privacy of outsourced database has attracted more and more attentions. Encryption is the most effective way for data privacy protection, but it raises at least two challenges: 1. data encryption may change the data type and length, resulting in that it is hard to impose encryption mechanism over existing database. For example, a phone number, encrypted using the AES encryption algorithm, not only does not resemble a phone number but will even not contain any numbers at all. A database field typically defined to hold an eleven-character phone number would not be able to store the AES-encrypted version of data; 2. data encryption may lead to hardly performing structured query language (SQL) operations over encrypted data.
For the first challenge, a novel primitive namely format-preserving encryption (FPE) making sure that ciphertext has the same format as plaintext was proposed. In other words, using this technique, the data encryption will not change the data type and length, so ciphertext can be stored in the original database. Since it was proposed, several solutions to FPE have been investigated. In 2002, Black (2002) formalized the FPE problem and proposed three basic methods to implement such cipher. After 2008, some FPE schemes (Morris, 2009; Bellare, 2010; Liu, 2010; Li, 2012) were proposed to provide format-preserving encryption for different domains like integer, datetime, etc.
For the second challenge, several cryptographic tools were developed to provide solutions for operating directly on encrypted data, such as order-preserving encryption (Agrawal, 2004; Boldyreva, 2009; Popa 2013) for encryption while preserving orders of ciphertext, homomorphic encryption (Van Dijk, 2010) for allowing function computations directly imposed on ciphertexts, searchable encryption for searching keywords over encrypted data (Song, 2000; Curtmola, 2006; Li, 2010) and query processing over encrypted databases (Kwok 2002; Wang, 2005; Yang, 2006; Ashrafi, 2007; Amanatidis, 2007; Evdokimov, 2007; Taniar, 2008). Although these techniques have been developed, fuzzy query over encrypted data is still a challenge.