We have a trusted application that observes sensitive identifiers, e.g. credit card numbers. We want to send data associated with these identifiers to an untrusted analytics service that will occasionally generate and send alerts back to the trusted application.
We've considered storing a table mapping sensitive identifiers to an opaque ID (e.g. UUID) to pass to the untrusted analytics service. But since there are billions of sensitive identifiers, the application can't store all the mappings due to storage constraints. We need the opaque ID to be stable over time, since the analytics service will be keying off of that to correlate data we send it. We also need the opaque ID to be reversible, so that the trusted application can determine what sensitive identifier was involved in an alert.
What we're planning on instead is to use a deterministic encryption scheme, though we're concerned about how well it fits our use case: often deterministic encryption is discussed in the context of key wrapping schemes, but the identifiers we see are far less random and have structure. On the other hand, we also see that chosen plaintext attack (CPA) is typically a concern, but in this case we aren't going to allow the attacker (i.e. the analytics service) to ask the telemetry service to encrypt arbitrary plaintexts.
We also don't want the untrusted analytics service to be able to figure out plaintexts or the key(s) used in a deterministic encryption scheme, even if it sees a large number of ciphertexts.
Given these constraints, what scheme best satisfies our use case? In particular, is AES-SIV applicable in this case?