0

There are three parties involved in a repeated data transfer process: Client C, Broker B and Provider P. There might be multiple clients C.

Broker B manages P's customer database. Each customer has a unique National ID numbers.

Client C can send requests to retrieve information of a customer ID from P's customer database (which B manages).

The requirement is: B must not know customer IDs, even though B manage's P database and information requests from C.

In other words:

  1. P can share data with Broker B without revealing customer IDs (e.g., encrypt the customer ID with a public key).

  2. C can query P's data that B manages, by sending the encrypted customer ID to B.

  3. B can match C's encrypted ID with P's encrypted key to locate a consumer record.

  4. B cannot brute-force attack the encryption to learn about true customer IDs.

We plan to assign P a public key. P uses this key to encrypt customer IDs of the data that B manages. C uses this key to encrypt customer IDs that are need to be queries.

The number of unique customer IDs is ~ 10 billion numbers. Therefore, it's quite fast to brute-force attack this list of 10 billion numbers.

My question is: Is there a deterministic public-key solution that satisfies (1), (2), (3), and (4).

  • Is it required that C can "decrypt" a customer ID or is the customer ID only needed for lookup? – Neil Smithline Jun 7 '15 at 20:04
2

If it isn't required that you can decrypt the customer ID, then I believe that you can use an HMAC. You create a shared secret between C and P. This should be a really nice long shared secret. When you go to store a customer ID you store HMAC(SECRET, CustomerID). When C wants to look up a record it performs the HMAC and passes the result to B who can do the DB lookup.

You are protected from pre-computation attacks because you have used a very long shared secret (let's say 1024 bits but less may be secure - others maybe can help you).

Likewise, the long secret protects you from brute-force attacks.

I believe that this securely satisfies (1), (2), (3), and (4). Of course, if you need to be able to go backwards from the hashed ID to the actual ID, this doesn't work. I know that you don't specify that requirement in your question but maybe you assumed it was obvious.

  • thank you! Is this possible for P to assign different shared secrets to multiple C? – AdamNYC Jun 8 '15 at 3:00
  • You can but it will make the look-up more complicated. You'll need to do hash an ID with each possible secret to find it in the DB. But of you know which secret to use with which ID this won't be a problem. – Neil Smithline Jun 8 '15 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.