Client side encryption / hashing of "person ID's" with password?

Question

What we're looking for

A solution where data is stored and retrieved (!) from a server using a person ID that can only be known at the client (form of anonymization). Furthermore, the client should be able to calculate the original person ID back from a data record.

Storing certificates on the client is not an option, asking the user for a password is.

My original idea

PBKDF2 + AES (CCM) on the client. However, because we need to be able to retrieve records later, I had to keep the IV (and salt) constant. For what I've read, this could be a problem (but I'm not sure, especially if the person ID is always smaller than the key?).

My alternative idea

PBKDF2 + AES (CCM) on the client, now with random IV. This can now only be used for calculating the person ID from a data record. For data retrieval we would add a separate column, containing a client-calculated hash of the person ID. To prevent against an attack that hashes all valid person ID's and works back from there, I was thinking to salt with the same user supplied password as we used for encryption (since this can be expected to never leave the client).

I could really use some thoughts on this challenge (and the two ideas described above).

Answer 1

Because of the requirement that the secret be decryptable, it has to be encrypted, rather than simply hashed. Because of the requirement that a record be retrievable by the secret, it should be encrypted deterministically, so it can be reproduced. Finally, no keys or salts can be stored by the client, complicating the matter.

This suggests that the client should encrypt the secret person ID using e.g. AES-SIV, which requires no IV. The encryption key can be derived from a password and a constant salt (per client, rather than per record) which does not need to be secret or random (but can be for some extra protection against the server).

Possible key derivation functions include e.g. PBKDF2, bcrypt, scrypt or argon2. I would prefer the later ones, but any of them are acceptable if the password is good.

(Note that AES SIV used without a nonce, like any deterministic encryption, leaks the equality of person IDs (by design), so they should all be unique for this to work.)