Ability to narrow searches tends to be in direct opposition with the confidentiality that you seek through encryption. For instance, if you store your "16-bit hash" in an extra column then that hash reveals 16 bits of the data -- 16 indirect bits, but 16 bits nonetheless. An attacker who sees the database may try to guess (brute force) the record contents, and the 16 bits will allow him to detect 65535/65536th of bad guesses: this is a substantial advantage.

Ability to do substring searches is even worse, since it necessarily reveals information that allows the brute force attack to proceed in gradual steps (this is in fact the same problem as partial password authentication).

At best, what you could do is to implement deterministic encryption, such that encryption of a given record value always yields the same encrypted result. This leaks a modicus of information (if two records have the same contents then this will show, despite the encryption layer); on the other hand, it allows for exact searches: you encrypt the value to search, and use the index on the encrypted values. Substring searches, however, should be avoided at all costs.

I think a better method would be to revisit your assumptions:

However this will probably change in the future so I am anticipating efficency problems.

Usually, performance issues don't exist until having been actually encountered (at least in a test platform, if not in production) and duly measured. As Donald Knuth once wrote: premature optimization is the root of all evil.

Even if the envisioned performance issue is real and you know how much it will cost, some alternate methods might be applicable. For instance, you could read all the records in the RAM of the application, decrypt them all, and keep them in RAM. This would allow very fast searches without even going to the SQL level. Modern servers have a lot of RAM. As an example, the servers that maintain the StackExchange sites (all of them) are reputed to have been sufficiently boosted in RAM (a few hundred gigabytes) so that all the data can be cached, and the servers can perform all read accesses at RAM speed.

If your records are, say, no longer than 100 bytes (e.g. they are the names of some people), then you can store 10 millions of value in a mere gigabyte of RAM. What is a gigabyte ? Even your phone has more RAM than that.

Ability to narrow searches tends to be in direct opposition with the confidentiality that you seek through encryption. For instance, if you store your "16-bit hash" in an extra column then that hash reveals 16 bits of the data -- 16 indirect bits, but 16 bits nonetheless. An attacker who sees the database may try to guess (brute force) the record contents, and the 16 bits will allow him to detect 65535/65536th of bad guesses: this is a substantial advantage.

Ability to do substring searches is even worse, since it necessarily reveals information that allows the brute force attack to proceed in gradual steps (this is in fact the same problem as partial password authentication).

At best, what you could do is to implement deterministic encryption, such that encryption of a given record value always yields the same encrypted result. This leaks a modicus of information (if two records have the same contents then this will show, despite the encryption layer); on the other hand, it allows for exact searches: you encrypt the value to search, and use the index on the encrypted values. Substring searches, however, should be avoided at all costs.

I think a better method would be to revisit your assumptions:

However this will probably change in the future so I am anticipating efficency problems.

Usually, performance issues don't exist until having been actually encountered (at least in a test platform, if not in production) and duly measured. As Donald Knuth once wrote: premature optimization is the root of all evil.

Even if the envisioned performance issue is real and you know how much it will cost, some alternate methods might be applicable. For instance, you could read all the records in the RAM of the application, decrypt them all, and keep them in RAM. This would allow very fast searches without even going to the SQL level. Modern servers have a lot of RAM. As an example, the servers that maintain the StackExchange sites (all of them) are reputed to have been sufficiently boosted in RAM (a few hundred gigabytes) so that all the data can be cached, and the servers can perform all read accesses at RAM speed.

If your records are, say, no longer than 100 bytes (e.g. they are the names of some people), then you can store 10 millions of value in a mere gigabyte of RAM. What is a gigabyte ? Even your phone has more RAM than that.