Encryption of small messages Some time ago, I asked how to encrypt small messages like e.g., four decimal digit numbers (banking PINs). I've got my answer, but also a warning like it makes no sense as it's easy to guess: Even having no information at all and bad luck implies 10000 trials only, which is nothing in crypto.
However, at an ATM you have three trials only, and a PIN encryption scheme not leaking any information makes a lot sense to me. What does the theory say?
Clarification:
I'm looking for something telling apart bad and good system for this encryption.

A bad system could be &quot;add a constant to the PIN modulo $10^4$. The attacker with a single plaintext-ciphertext pair could decrypt any other ciphertext.
A perfect system would be &quot;generate a permutation table with $10^4$ elements using a true RNG and a proper algorithm&quot;. Now the attacker with any number of plaintext-ciphertext pairs given an unseen-yet ciphertext knows nothing except that the corresponding plaintext is not in his collection.
You want to talk about format-preserving encryption. One of the main motivations for FPE is the ability to encrypt messages which lie in a short space, with an output which is in the same space.

The ideal encryption model on a space of size $S$ (e.g. $S = 10000$ for four-digit PIN codes) is that the encryption systems implements a permutation chosen randomly and uniformly among the set of $S!$ possible permutations. Or at least that the cipher is indistinguishable from such a randomly chosen permutation.

An extreme security model is then the following: assume that the attacker is given a black box which implements the encryption (and decryption) algorithms. He can ask for the encryption or decryption of the almost complete code book, i.e. $S-2$ requests. The attacker gets to choose the contents of each request, adaptatively. So at that point, the attacker can simulate the complete encryption function, except for two input values: he knows the two inputs (let's call them $p_0$ and $p_1$) and the two corresponding outputs ($s_0$ and $s_1$), but he does not know whether $p_0$ encrypts to $s_0$ or to $s_1$. His goal is to predict the encryption of $p_0$ with probability substantially better than pure luck (i.e. $1/2$).

A commonly quoted solution for FPE is the Thorp shuffle. It is an unbalanced Feistel cipher, with enough rounds to make it secure. The good part of it is that it is possible to prove security while keeping the number of rounds low enough to be practical (say 100 rounds or so). The bad part is that it does not realize the extreme model explained above. You have to relax a bit the model, because a Feistel scheme always implements an even permutation; so if you know all the code book except the encryptions of $p_0$ and $p_1$, then you can decide whether $p_0$ goes to $s_0$ or $s_1$ with 100% success rate, because only one of the two choices leads to an even permutation. However, the relaxation is not a big deal: if you give to the attacker only $S-3$ requests, then you can have the best possible under these conditions (attacker cannot predict the mapping of the three remaining inputs, except that they will have to comply to the "even permutation" rule).

To reach the "ideal" model with $S-2$ requests, you have to do heavier thing, like generating the complete permutation in a big array (this is certainly doable with only 10000 entries; for bigger spaces, memory-conscious solutions exist, but the CPU price is quite high). For a practical solution, use the Thorp shuffle.



For verifying PIN codes, encryption is probably not the right tool anyway. Indeed, as you notice, the space of PIN codes is so small that there must be a locking mechanism somewhere, which blocks the attempt after three wrong tries. You cannot have that from cryptography alone. In fact, you will get locking by using dedicated hardware: either a smart card (the smart card is tamper-resistant and locks itself after three wrong PIN codes) or a remote server (that enforces the locking policy).

FPE is used to realize other features, e.g. serial numbers with verifiable validity: you define an 8-digit number which embeds a 5-digit counter value, and you want to have a tool which can verify whether a given sequence of 8 digits is one of the 100000 sequences that you have issued; but you don't want anybody else to be able to generate random "valid" sequences with success probability higher than 1/1000. Solution is to encode the 5-digit counter as 8 digits by appending three zeros, then encrypting the whole lot with FPE. To verify, decrypt, and see if the three zeros are there.