Practical Solutions For Format-Preserving Encryption
This addresses the need for secure and practical FPE in cloud computing and data storage, offering incremental improvements over existing methods.
The paper tackles the problem of inefficient and insecure format-preserving encryption (FPE) for general formats, proposing a scheme with optimal security and efficient algorithms that support large formats through a user-defined size bound, achieving a flexible security-efficiency tradeoff.
Format Preserving Encryption (FPE) schemes encrypt a plaintext into a ciphertext while preserving its format (e.g., a valid social-security number is encrypted into a valid social-security number), thus allowing encrypted data to be stored and used in the same manner as unencrypted data. Motivated by the always-increasing use of cloud-computing and memory delegation, which require preserving both plaintext format and privacy, several FPE schemes for general formats have been previously suggested. However, current solutions are both insecure and inefficient in practice. We propose an efficient FPE scheme with optimal security. Our scheme includes an efficient method of representing general (complex) formats, and provides efficient encryption and decryption algorithms that do not require an expensive set-up. During encryption, only format-specific properties are preserved, while all message-specific properties remain hidden, thus guaranteeing data privacy. As experimental results show that in many cases large formats domains cannot be encrypted efficiently, we extend our scheme to support large formats, by imposing a user-defined bound on the maximal format size, thus obtaining a flexible security-efficiency tradeoff and the best possible security (under the size limitation).