The two approaches can be combined! You can use AES to generate and store the ExternalId column. As you pointed out, this saves you from having to encrypt/decr

The two approaches can be combined! You can use AES to generate and store the ExternalId column. As you pointed out, this saves you from having to encrypt/decrypt it on the fly every time, at the cost of an extra lookup and some storage (you're going to want an index on that column as well). If it ever comes up that you prefer to do it on the fly, you can just drop the column. All your external references will still be valid since the ExternalId was generated deterministically.