I think the decryption function (or its possibility) is a security hole. Why not keep a copy of the encrypted value locally? When the external partner has a query and sends the encrypted value back, just look it up in the copy you have. On uniqueness: just make an MD5 hash or similar and encrypt it - it is almost guaranteed to be unique.