I am creating a database table with an encrypted value, say users:

Say John encrypted is U2FsdGVkX193AOGlBRE1RNScJRGN9vSB4erIljJwaKw=.

UserId | Name
------ | --------------------------------------------
1      | U2FsdGVkX193AOGlBRE1RNScJRGN9vSB4erIljJwaKw=

Johnny would be encrypted as U2FsdGVkX19lYDuvuBg3BzTnZro4J6zKoo9s/TLeiPU=.

UserId | Name
------ | --------------------------------------------
1      | U2FsdGVkX193AOGlBRE1RNScJRGN9vSB4erIljJwaKw=
2      | U2FsdGVkX19lYDuvuBg3BzTnZro4J6zKoo9s/TLeiPU=

How could I search for names beginning with Jo?

I was thinking of storing:

NameStub | UserId
-------- | ------
Jo       | 1
Jo       | 2
Joh      | 1
Joh      | 2
John     | 1
John     | 2
Johnn    | 2
Johnny   | 2

I can now do searches like 'Jo%', 'Joh%' and both will include both users.

I can see the obvious security flaw with the above that anyone can map out stubs like Jo or Joh.

So I have decided to store the stubs encrypted:

NameStub    | UserId
----------- | ------
enc(Jo)     | 1
enc(Jo)     | 2
enc(Joh)    | 1
enc(Joh)    | 2
enc(John)   | 1
enc(John)   | 2
enc(Johnn)  | 2
enc(Johnny) | 2

where enc(x) is just the encrypted value for x.

When searching for Joh, I will encrypt Joh and then query for matching stubs and any associated users with names for that stub.

Note:

• Both of the encrypted columns will use different keys and algorithms to protect the data.
• I will be using Microsoft SQL Server Transparent Data Encryption (TDE).

I need to understand if I am missing something fundamental here.