Can you help me understand Format Preserving Encryption? I came across the definition of format-preserving encryption (FPE) as first defined in a seminal paper by Black and Rogaway. Based on their paper, FPE (or prefix cipher) is defined as follows (quoted from Wikipedia):


  One simple way to create an FPE algorithm on ${0,...,N-1}$ is to assign a pseudorandom weight to each integer, then sort by weight. The weights are defined by applying an existing block cipher to each integer. 


Can you help me understand the difference between this and monoalphabetic substitution, and what security is offered by FPE?
I cannot understand what is the difference with monoalphabetic substitution and what is the security offered.


A monoalphabetic cipher applies to individual symbols of the plaintext.  But an FPE scheme works on the whole message as a unit.  In the set {0,...,N-1} that you mention, N is the size of the message space—the number of distinct messages, not the number of distinct symbols; each number represents a distinct message, not a symbol of a message.  So for example:


For US Social Security numbers, which are 9 digits, N is one billion, and each number in the set {0,...,N-1} stands for a distinct SSN.
Credit card numbers have 16 digits, but generally the first 6 and last 4 digits must be left in the clear, so the middle 6 are encrypted and N = one million.


But the 10 digits left in the clear are used as a "tweak" to the encryption, so that 123456 in the middle six encrypts to different values for different credit card numbers.



The way FPE works is (ignoring the "tweak" concept that I mentioned above):


You define a bijective function between your message space and the set {0,...,N-1}.  For SSNs, N = 1,000,000,000, and the bijective function just treats the 9-digit sequence as a decimal numeral with its most significant digits padded with zeroes.
The FPE scheme gives you a bijective encryption function that takes a secret key and a number between {0,...,N-1} and outputs another number between {0,...,N-1}.  (It also takes a tweak, but I'm ignoring that for simplicity.)


So to encrypt an SSN you convert the SSN into a number using the function from (1), encrypt that number using the FPE scheme, and convert the encrypted number to an encrypted SSN using the inverse of the function in (1).  To decrypt you use the inverses of the functions.



One of the reasons why FPE scheme is defined in terms of sets {0,...,N-1} for user-chosen values of N is for flexibility; as long as you can define a bijection between your message space and such a set, you can use FPE to encrypt those values.  For example, if you want to apply FPE to a database date field, you can't just read the date's sequence of digits as a number, because some such sequences of digits aren't valid dates (e.g., 2014-54-35), but the encryption could well output the number 20,145,435.  But you can use date arithmetic to represent a date as a count of days since a reference "beginning of time," and then apply FPE using this bijection.



The security offered gets a bit more complex, but at the most basic level it is that the FPE is a pseudorandom permutation on the set {0,...,N-1}.  Imagine a solution where instead of using a cipher, you had a big database where, for each plaintext Social Security number, you stored a unique, randomly chosen sequence of nine digits.  The encryption operation would go somewhat like this.  Given a plaintext P:


Search the database for an entry that has P as its plaintext.
If P is already associated with a ciphertext C, then return C;
Otherwise, set C to some message chosen at random (using a true random number generator).
Search the database for an entry that has C as its ciphertext.
If C is already in the database, go to 3.
Otherwise, store the entry (P, C) in the database, and return C.


FPE's basic security goal, put in simplified terms, is to be no worse than that in practice, from the point of view of an attacker who has doesn't have the encryption key but might have seen a subset of the plaintext/ciphertext pairs.

Note as well that there exist token vault solutions that work like the six-step sketch that I described—a database that associates plaintext with unique random values.  So in another sense, the security goal of FPE is offer comparable practical security but at lower cost and better reliability and performance.