Format-preserving encryption is a deterministic encryption scheme that encrypts plaintext of some specified format into ciphertext of the same format. This has a lot of practical use cases such as storing SSN or credit card information, without having to change the underlying schematics of the database or application that stores the data. The protected data is in-differentiable from unprotected data, and still enables some analytics over it, such as with masking (ie, displaying last four digits of a format). For other analytics, and depending on the use cases, differential privacy or FHE should be considered.
This paper primarily describes construction of a short-space FPE scheme. Starting off with earlier constructions based off of work done by Terence Spies and M. Bellare. The authors have developed an FPE scheme that is tweakable, to enhance security and this value is imperative for ciphertext alphabets of small range. A tweak value is like an initialization vector, chosen by the user. This ensures that with two different tweak values, the same plaintext encrypted twice will encipher to different ciphertexts.
Of particular interest for practical applications is 'cycle-walking' and 'rank-then-encipher'. These are "meta-techniques" for building an FPE scheme that essentially ensures you get a ciphertext in the desired ciphertext space.
misc (pg 9):
cycle-walking:
If you wanted to encipher on some message space $X$, you would make an FPE scheme:
$$E: K \times \chi \rightarrow \chi$$
If you know how to encipher onto a superset of $X'$, with an FPE scheme:
$$E' : K \times \chi' \rightarrow \chi'\\$$
All you would need to do is keep enciphering the message $X \in \chi'$ until you get $X \in \chi$
Rank-then-Encipher:
Encipher a point $X \in \chi$
map it to a corresponding point $X' \in \chi'$, encipher that point in $\chi'$ to get a ciphertext $Y' \in \chi'$, then map $Y'$ to its corresponding point $Y$ in $\chi$.