Format-preserving encryption (FPE) encrypts a plaintext of some
specified format into a ciphertext of identical format—for example,
encrypting a valid credit-card number into a valid creditcard number.
The problem has been known for some time, but it has lacked a fully
general and rigorous treatment.We provide one, starting off by formally
defining FPE and security goals for it.We investigate the natural
approach for achieving FPE on complex domains, the "rank-then-encipher"
approach, and explore what it can and cannot do. We describe two flavors
of unbalanced Feistel networks that can be used for achieving FPE, and
we prove new security results for each. We revisit the cycle-walking
approach for enciphering on a non-sparse subset of an encipherable
domain, showing that the timing information that may be divulged by
cycle walking is not a damaging thing to leak.
Proceedings of Selected Areas in Cryptography 2009
Full version is available as a pdf
List of Updates: