I've run into this issue a couple of times in my career. I'll see if I can explain with an example (please ignore the fact that this is implausible in the real-world).

Suppose I sell computers, and I have account data on the person that purchased every computer I sell. I also install tracking software on every computer I sell, so that it sends me detailed information about which websites are being visited on that computer.

I would like to set up some sort of system that would allow me to merge account data with usage data in aggregate, but NOT for individual users.

In other words, I don't want to be able to know that John Doe watches cat videos and surfs porn 7 hours a day. I would think that's a violation of his privacy. However, I do want to be able to know that men are 20% more likely than women to visit news sites. This would still require the merging of account data and usage data - I just don't want to be able to see merge results for individual users, only aggregates.

Is there any way to accomplish this? Simply encrypting the key that links the account and usage data is not enough, obviously. The join could still happen. It seems like you need to encrypt usage data in such a way that it can only be decrypted when more than 1 value is aggregated. Is such a thing possible?

  • 2
    $\begingroup$ One approach to solve this problem is functional encryption. Another approach is secure multiparty computation. They each have strengths and weaknesses, which, if I have time, I'll write up in an answer. $\endgroup$ – mikeazo Jun 11 '15 at 15:06
  • $\begingroup$ Both of these sound like promising avenues - secure multiparty computation in particular. Unfortunately, there's one difference between these schemes and what I'm trying to accomplish - in the SMC protocols, all of the parties involved are participating in an ongoing, collaborative process to determine aggregate values. In my example (above), the users' computers send me their web data, and that's the limits of their participation in the process. $\endgroup$ – John Chrysostom Jun 11 '15 at 19:56
  • $\begingroup$ SMC can also be used in an outsourcing model. The users' secret share their data and send a share to 3 or 4 cloud services, the cloud services then run the computation privately and send the result to you. If you are looking for a commercial offering, Sharemind might work. $\endgroup$ – mikeazo Jun 12 '15 at 11:36
  • $\begingroup$ What about differential privacy? $\endgroup$ – pg1989 Jun 13 '15 at 0:19

If you're okay with getting statistics that are not perfectly exact but noisy, a variant of randomized response could solve your problem. Instead of sending you real information about their usage, your users will send you noisy data. For a given user, you can't know for sure whether their answer to a particular question is exact or is just random (and you get a very solid property to quantify that, differential privacy). But when aggregating all responses, you can get statistics that are close to the real ones.

If you need more than binary questions, take a look at RAPPOR and the related paper — if you have enough users, you can get much more complex statistics (numerical, strings…) with a very decent precision and strong privacy guarantees.

Note that implementing such a system in practice is not trivial: you need to make sure that if you ask the same question twice to the same user (in your case, if the statistics are collected periodically) their randomized answer stays the same — otherwise, the noise cancels itself out over time and you end up learning sensitive information about them.


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.