Two-phase anonymization

Question

EDIT:

[N.B: I fully replaced the original question which was not a very good statement of the problem (see comments) with a more apt one.]

I have records that contain - among other things - the location of users and their ID (it is a big stream of data). I need to provide a 3rd party the location of users. (The stream is also filtered based on other criteria in the stream and perhaps even merged with some other data sources that all contain user IDs - if it is of any interest here and now.)

I must not pass the user IDs to the 3rd party.

The records a output have to enable the 3rd party to build up "routes" and/or time-variant location maps of users over a period of time (say a day but much longer than one hour). To this end they must be able to identify records that belong to the same user. Thus some key has to be passed.

An important restriction that constitutes the core of the problem:

For the discussion let me define "anonymized user ID" an attribute that is is derived from the attributes of the input records such that it is (nearly) uniquely derivable from the user ID (e.g. a hashed salted user ID or a fixed random mapping), and placed in the records of the output stream so that records that belong to the same user can be identified.

Legal regulations and internal rules are such that I must make sure that the "anonymized user ID" can be reproduced for no more than one hour. (Just as an illustrative example: if I would happen to use a salted hash of the user ID as "anonymized user ID" I would have to use a new salt hourly.)

(Note: As mentioned above the 3rd party has to map locations to users for longer. They still don't care about the identity of the user but they have to know that it is the same user all along.)

And the questions are: Is there a way to do this at all? If yes, how?

Answer 1

To restate: your system has users with assigned IDs. You receive periodic location data associated with these user IDs in real time.

You also have one (or more) clients who want to analyze your user locations. Each client needs to receive randomized tokens that each map to a user ID, and the tokens can refer to a specific ID for a period of no more than some maximum duration, say 24 hours. The client needs the location data. The client never needs the real user ID.

And you have a policy prohibiting you from internally retaining the location associated with your real user IDs.

Here's a possible solution:

First, obtain a public key from each of your clients. At the start of each day, for each client generate a random salt and store it internally in RAM, keeping it secret. Upon receipt of a new User ID and location pair, add the client's salt to the ID then compute the hash. After hashing, immediately encrypt the hash with the client's public key, applying randomized padding, then immediately discard the hash. The encrypted salted hash is now a client-specific encrypted token. Preserve only the client ID, the public key ID, the encrypted token, and the location data; place the data in the appropriate message queue. Repeat the tokenization process for each client who will receive the data; after tokenizing the user ID for each of your clients, discard the real user ID. You can then send the encrypted tokens with the location data to each receiving client. Once per day, destroy each client's secured salt and generate a new one.

By destroying the intermediate hash and the user ID, you remove the only links you have tying the location record to a real user ID. You control the client's ability to correlate records by destroying their salt.