How to protect against brute force attacks in the case of a small dictionary?
I think you're looking for column level encryption.

It allows you to encrypt specific columns in your database, in your case the cloumn "country".

Another way would be to use database encryption, which can encrypt an entire database. The main disadvantage there would be the speed, because the size of the data to encrypt / decrypt is larger than just the data in a single column.

Just be sure to store the encryption key securely. You can find more information about this topic in this post: SecuritySE - Where to store a server side encryption key.

Edit:


  My question is not tied to the specific case of the column of a table. Rather, I am asking what are the algorithms to use when the dictionary size is small.


You could simply use a symmetric-key algorithm, i.e. AES in CTR mode to protect your data. It works for both small and large data.