Don't do this!
- TDE is irrelevant for this question.
- Don't do this (index encrypted substrings of encrypted strings).
- Don't index encrypted values generally.
- If you are going to do this anyways, use an HMAC or other MAC algorithm to generate the encrypted values to be used in the index(es).
- If you're feeling really lucky, consider using a format-preserving encryption algorithm or a "Searchable Symmetric Encryption (SSE)" algorithm instead of a MAC algorithm.
I'm assuming "TDE" is Microsoft SQL Server Transparent Data Encryption. TDE is irrelevant (for your question). TDE encrypts an entire database and is 'transparent' to database users or other clients connecting to the database. What TDE protects from is an adversary accessing the data in the database offline, i.e. via copies of the database files or copies of the encrypted data, but without also having access to the encryption key with which the secured data was encrypted. Think of an attacker stealing a backup of the database, e.g. stealing a backup tape cartridge containing the database data or log files. If an attacker can access a live database for which TDE is configured, and the database system doesn't otherwise deny them access to the secured data, they can access any data in it (that's not otherwise encrypted apart from TDE).
Indexing Encrypted Data
The most secure method of searching encrypted field values is going to be to decrypt all of the field values to be searched first. Ideally, you'd do this directly in the database, e.g. in a stored procedure or function. It seems unlikely that an attacker could read the memory of your database process(es) but not also access the encryption key(s) used to encrypt the data in the database.
Your idea of storing encrypted "stubs" or substrings will weaken the security, perhaps substantially. This is a great answer on another question on this site that seems to generalize your question somewhat:
That answer points out an important reason why this approach weakens the security:
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.
You can't create an index of encrypted values without exposing (to people that can see those encrypted values) that equal values are equal. Typically, values would be encrypted with a salt that's unique to each specific instance or occurrence of a value but one consequence of that is that any number of instances of the same cleartext will be encrypted using different salts and thus will result in different encrypted values. This is one reason why decrypting the values to be searched – before searching – is probably the best choice if you really need to store these values encrypted by default, even for authorized database users.
Note that this same weakness applies even for searches for exact matches, i.e. even if you're just indexing the encrypted values whole for performing searches for exact matches. In fact, for the two sentences I quoted above, the sentence immediately following is:
Substring searches, however, should be avoided at all costs.
(That's referring to indexing encrypted substrings.)
Algorithms for Indexes of Encrypted Data
But – if you decide that weakening security as described above is something you're willing to accept, then – cryptographically – the top two answers on this related Stack Overflow question suggest using a MAC algorithm to generate the indexed version of the field to be searched:
This answer on the same question above suggests carefully considering using a format-preserving encryption algorithm, the care being in knowingly using a class of algorithms that are relatively new and thus possibly vulnerable to attacks not yet publicly known.
In this comment on this very question, @AlphaD suggests considering using a "Searchable Symmetric Encryption (SSE)" algorithm. This should only be considered with even more care than for considering a format-preserving encryption algorithm. SSE algorithms are so new that there wasn't even a Wikipedia page for them when I checked.