0
$\begingroup$

First of all apologies if this is not the right place. I am not very knowledgeable in cryptography but I thought you can at least point me in the right direction of research.

The following is a toy problem I tried to to analyse for fun and see if it's possible to find and answer.

It might be the case that the way I have tried to define the problem is still not valid enough, for that reason I am also happy to try and reformulate it to make it more interesting or useful.

Before I go into my version of the problem, I want to explain the philosophy behind it,i.e. what is the sort of intuition I am after: in our everyday world, we often have users who interact with a external service/company. The company would like to do some data analysis on the data provided by their users to make use of their service.

The general question is: can we devise a system that allows the service provider to run aggregate computations over the data but in a way that service provider is unable to reconstruct exactly the list of data of its users?

///////////

Ok here is how I tried to capture this problem mathematically. I am open to modification to this:

Let's pretend Company A has a mathematical function f that takes as input an unordered list of 5 numbers (i.e. swapping the order of the arguments the result stays the same) and returns a single number.

Moreover this company has 5 clients each of which is defined by a number code, which is an integer number from 1 to 10.

Is it possible to find a general algorithm/system of communication in such a way that Company A is able to compute the value of the function f applied to its set of clients' number codes but without being able to reconstruct the actual list? If this is not possible in general, can you prove it?

//// For example, let's assume the five clients have numbers: 1;4;10;4;3

The function to compute is "the number of number codes bigger than three" in this case this function evaluates to 3, since there are 3 numbers (two 4, one 10) bigger than three.

A very naive approach would be via an API where each client gives is number. Then company A can surely compute the value of f. The problem is that with this it also knows for sure that it's client list is made of 1,4,10,4,3 so this is not a valid solution.

A valid solution could be instead in this case the following system: each client send 1 or 0 whether their number is bigger than three. Then company A sums up this values. In this case is not able to recontestruct the original list(i.e. all lists such that there are three number bigger than three are equiprobabile) but can compute the aggregate value.

I suspect this is not achievable in general, for example for the simple case of a function like the product of all the number codes I can't think of a way one could do this.

Again I do fear I haven't managed to mathematicize this problem quite correctly yet, but I am very curious to know from you the expert if this sort of problem reminds of some specific area of cryptography (it will probably be something really basic I suspect).

Just to reinstate: I am interested in the trade-off between maintaining ownership/privacy of each single data points (the number code) while allowing the big company to query for AGGREGATE information.

Stated another way: can we devise a system to ask questions about the whole "sea" in a way that doesn't allow to also know each single "drop" that makes that sea?

$\endgroup$
2
  • $\begingroup$ Secure multi-party computation. $\endgroup$
    – Mikero
    Feb 20 at 14:39
  • $\begingroup$ This is spot on what I was after, thanks! $\endgroup$ Feb 21 at 0:47

1 Answer 1

1
$\begingroup$

One common approach to deal with these kinds of questions is differential privacy, google it. A search here on crypto stackexchange yields quite a lot of questions and answers.

Very briefly and in its simplest instantiation, it's about querying a database to obtain information about the database without leaking specific information about individuals or certain groups. There are algorithms devised for this purpose. At a very high level, they "add noise" to the computations but the noise impacts the quantity that is being computed minimally.

In terms of what you are asking, threshold queries are more problematic, since they leak more information than averages, as you also surmised.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much, I will definitely start digging deeper. Meanwhile I also stumbled upon the concept of "homomorphic encryption" which seems also very relevant to the sort of general problem I was thinking about. I am guessing though that these systems have various security drawbacks. Thanks a lot for the nudge! $\endgroup$ Feb 18 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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