Let's say you were given a dump from a security breach. You want to share the email addresses affected by the breach with a separate company who pays you for this service so that they can protect their users. Maybe it's a security company, or maybe it's a large retail store wanting to prevent accounts with shared passwords from being hacked.

The constraints are:

  1. You cannot know anything about the company's users. They can't send you a list of email addresses that they want to subscribe to, because even if they are hashed you could discover the list and compromise the privacy of the company's customers. If you are dealing with a EU-based company, it's also against the law for them to share this if I understand correctly.

  2. You don't want to send each company the entire list, only the list of emails that they subscribed to prior to the breach. You might initially be one of the only people given this dump- it's not publicly available- and you do not want the entire list to spread by an employee at one of these companies.

Is there a cryptographic means by which the company can declare to you ahead of time which addresses they are subscribing to, without you being able to decrypt this subscription and learn anything about their users, but by which you can construct a message to them when a breach happens such that they will learn only the addresses in the breach which were also in their prior subscription?

If they want to check the same breach against a larger set of emails (possibly for nefarious reasons), they would be forced to declare a new subscription. This new subscription should be useless to discover any new addresses based off previous communications based off the previous subscription. Then they request a new notification for the breach based on their new subscription. If their new subscription is not suddenly suspiciously large, you repeat the original process with the new subscription.

Bonus if it's possible for you to obfuscate the actual size of the breach when performing the sharing.

This seems like it's perfect problem for cryptography to solve. What are the possibilities at our disposal?

  • $\begingroup$ I don't know why but this makes me think to oblivious transfer protocol and Tardos Codes. $\endgroup$ – Biv Mar 18 '16 at 13:49
  • $\begingroup$ You seem to be conflating "breach notifications" with [protocol which will reveal the intersection to them]. ​ Is the idea that the protocol should be non-interactive? ​ ​ ​ ​ $\endgroup$ – user991 Mar 18 '16 at 14:40
  • $\begingroup$ @RickyDemer The only interaction is subscribing and later finding the intersection with as few round-trips as possible (obviously) to achieve the proper ignorance. Can you suggest better tags? $\endgroup$ – jnm2 Mar 18 '16 at 14:45
  • $\begingroup$ I can't suggest better tags, but I suggest replacing the initial "breach notifications" with "protocol executions that have already been carried out", replacing "sending out the breach notifications" with "carrying out the protocol", and replacing the other use of "notification" with "protocol execution". ​ ​ $\endgroup$ – user991 Mar 18 '16 at 14:46
  • $\begingroup$ @RickyDemer That language seems less specific, more cloudy. I'll try to clarify. $\endgroup$ – jnm2 Mar 18 '16 at 14:50

Your Answer

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

Browse other questions tagged or ask your own question.