Format-Preserving Fuzzy Query Mechanism

Outsourced database has attracted much attention recently due to the emergence of cloud computing. However, a problem need to be further solved is how to encipher data and perform fuzzy query over the encrypted database while keeping the database structure. In this paper we propose a format-preserving fuzzy query mechanism based on format-preserving encryption (FPE), which protects the privacy of the sensitive data and keeps the data structure. The mechanism generates keywords for every possible keyword of the corresponding data, and results in a longer keyword string. It performs fuzzy query at a cost of O(n²) times of AES and practically acceptable redundancies in the query results, while being secure in all aspects.