Format Preserving Encryption and its applications

As we all know, when we encrypt a 16 digit credit card number using AES, it gives a random block of bytes (depending on the block size utilized). Wouldn't it be cool if we can get another random 16 digit number when you encrypt a credit card number and still be safe? That's where format preserving encryption (FPE) [1,2,3] comes in. Apart from the "coolness" there are many practical advantages of such encryption:

1. It can provide a simpler migration when encryption is applied to legacy systems/databases:
- Since it's the same format, you don't need to change the database schema (type, size, etc.)
- If these data are transported, no change required to the transport layer

2. It may not even be possible to encrypt if it does not preserve the format and deterministic.
- Take for example, a primary or foreign key field


I am not sure how secure these FPE constructs are compared to classical symmetric key encryption. However, I think there will be more interest on this subject with the increase utilization of cloud computing.


[1] H. E. Smith and M. Brightwell. Using Datatype-Preserving Encryption to Enhance Data Warehouse Security. NIST 20th National Information Systems Security Conference, pp.141, 1997.
[2] J. Black and P. Rogaway. Ciphers with Arbitrary Finite Domains. RSA Data Security Conference, Cryptographer's Track (RSA CT '02), Lecture Notes in Computer Science, vol. 2271, pp. 114-130, Springer, 2002.
[3] T. Spies. Feistel finite set encryption mode. Manuscript, posted on NIST’s website on February 6, 2008. Available
at http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-spec.pdf