0
$\begingroup$

Consider a situation in which two companies hold data about individuals: the first company holds individual's names, and their age.

The second company also holds the individual's name, but instead of holding their age they have their salary.

The state is interested in doing analysis of how age and salary are correlated: so would like to build a data base of the pairs (age, salary), however they wish to do so without being able to identify individuals, and without requiring the two companies to share their data.

Is there a data sharing strategy that the state and the two companies can devise so that:

  1. The state has the pairs (age, salary).
  2. None of the parties (state, or companies) can identify any given individual's age and salary.

A few points / thoughts:

I am working with the assumption that names are unique, so that if one party had both the (name, age) and (name, salary) data then they would be able to uniquely determine the (name, age, salary) data; but this strategy itself violates requirement 2.

Using just the name, age and salary variables it seems clear to me that this cannot be solved: if either company gives their names to the other this is of no use, likewise if they provide their age/salary data alone the other company cannot use it. And if both companies provide the age / salary data to the state then they alone cannot join the data.

So this leaves the question of whether additional anonymised identifiers can be created between the three parties to achieve the objective?


Update / Extension I realise that in wording the question I have over simplified the situation I am actually interested in, but the solutions below have been enough for me to adapt to this case.

In my scenario (and as one would expect in the real world!), the names held by the two companies do not match exactly.

This means that the succinct solution of @TwoBitOperation cannot be applied.

Further to the above, I will add the constraint that the two companies are only willing to share their data directly with the state (both names, and attributes).

I have posted my solution to this adaptation below (though refuse to accept my own answer, as it is heavily inspired from others' contributions).

$\endgroup$

closed as off-topic by Chowzen, JonMark Perry, w l, Glorfindel, puzzledPig Jun 6 '18 at 18:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – Chowzen, JonMark Perry, w l, Glorfindel, puzzledPig
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Wow, talk about an edit that moves the goalposts. $\endgroup$ – Phylyp Jun 6 '18 at 16:09
  • $\begingroup$ Yes, apologies: and hence why I mention that I am so grateful for the contributions below. It really was one of those cases where trying to simplify a problem down to the barebones meant I ultimately over simplified! $\endgroup$ – owen88 Jun 6 '18 at 16:10
  • $\begingroup$ Based on the edit, this looks to me to be a question for Security SE instead of Puzzling. The edit implies he is searching for a solution, not offering a puzzle with a solution. $\endgroup$ – Keeta Jun 6 '18 at 18:29
  • $\begingroup$ Its fair to say I came across this in a genuine real world environment, however my interest in a pure solution as above is more for the puzzle aspect (in the real world, pragmatism has taken over and an easier solution found!). Reading the off topic post distinguishing between mathematics problems and puzzles, I would personally determine this as a puzzle, as i believe it satisfies the bullet point: "Clever or elegant solution, often an "aha" moment". On the other hand I do not think a general mathematical audience (eg. math.stackexhange) would find this question to fit their remit. $\endgroup$ – owen88 Jun 6 '18 at 18:40
7
$\begingroup$

This seems solvable, unless I'm not understanding all the stipulations.

1) Company A encrypts the salaries with function f, then sends the tuples (NameN, f(salaryN)) to Company B

2) Company B uses the names to cross-reference their database of ages, then is able to send the pairs (AgeN, f(salaryN)) to the state

3) Company A has the inverse decryption function f-1, and provides it to only the state

4) The state decrypts what Company B sent them using f-1 to get (AgeN, salaryN)

Now, neither company has provided useful information to the other, and the state only has the two values it needs.

$\endgroup$
  • 1
    $\begingroup$ A suggestion - to probably make it easier to understand for non-math/non-tech users (if there are any such on this site!), you could give an example of an obfuscation function like ROT13("pbzcnal N nqqf 1234567890 gb gur fnynel"). I agree that this is not a good function to use in reality, but is good enough to explain the principle. $\endgroup$ – Phylyp Jun 6 '18 at 16:08
2
$\begingroup$

I am working with the assumption that names are unique, so that if one party had both the (name, age) and (name, salary) data then they would be able to uniquely determine the (name, age, salary) data; but this strategy itself violates requirement 2.

So, with this in mind:

-We can 'just' create ID numbers's for our names in company 1
-Send a list with names and ID's to company 2
-Both companies send their list of ID's and age/salary to the state who can join tables on their ID's


In the end, none has complete information about all 3 variables: Individuals-Age-Salary
And no weird encryptions are needed.

$\endgroup$
1
$\begingroup$

How about:

Using one-way encryption algorithm, to encrypt the name.

So

1. The first company sends the state, the encrypted_name and age.
2. The second company sends the state, the encrypted_name and salary.
3. The state joins the data, without knowing the actual names.

$\endgroup$
  • $\begingroup$ I think that it is a good answer. It is the only answer with no communication between companies for now! $\endgroup$ – Untitpoi Jun 6 '18 at 14:35
  • 2
    $\begingroup$ @Untitpoi (I'm not that much into encryption, but...) Don't they have to communicate to make sure that their encryption matches with that of the other company? And if it is always the same kind of encryption, so that the data always matches, can't the state just brute force it to still get the names? $\endgroup$ – PL457 Jun 6 '18 at 14:48
  • $\begingroup$ Im not a specialist of encryption either! As for a password database, You don't need communication between users to get that, state has to give the one way encryption that will be used. But I agree in this case, the state could brute Force the encryption. Or making is own database using the encrypted name and the corresponding real name. So it has some issues indeed. $\endgroup$ – Untitpoi Jun 6 '18 at 15:35
  • $\begingroup$ @PL457 They would only need to agree on the algorithm. State would have to spend a bit of effort to brute force. $\endgroup$ – paparazzo Jun 7 '18 at 0:35
0
$\begingroup$

Just a bit more generic than what was suggested by TwoBitOperation

The solution seems trivial, as long as you have not left out any requirements and can be solved in many combinations, requiring all but one of the parties to know a common secret or function.

If you have a one-way function f(name) (it may be an encryption function or anything else), which returns a unique result for each name, so that f(name₁) ≠ f(name₂) if name₁ ≠ name₂, all companies (it may be more than 2) can send f(name) together with their data to the state. The state can use the key f(name) to correlate the different data, but will have no way to know which person the data belongs to.

$\endgroup$
0
$\begingroup$

This is my solution to the updated / extended problem; with much inspiration from the solutions provided to the original problem I posed.


Let $(N_1, A)$ denote the (name, age) data held by the first company, and $(N_2, S)$ denote the (name, salary) data held by the second company.

1. The companies send the state $N_1$, and $N_2$. From this the state creates a mapping $N_1 \sim N \sim N_2$.

2. The state sends the first company the pairs $(N_1, N)$ and the second company $(N_2, N)$.

3. The first company defines a new mapping $N^* \sim N$, and sends the second company $(N, N^*)$.

4. The first company sends the state $(N^*, A)$, and the second sends the state $(N^*, S)$.

$\endgroup$
  • 1
    $\begingroup$ After step 2, the names have been normalized between the two companies, at which point the answer that @TwoBitOperation provided also becomes feasible. In fact, at this point, your original question itself becomes valid. $\endgroup$ – Phylyp Jun 6 '18 at 16:13
  • 3
    $\begingroup$ step 3 has a communication between the two companies no? $\endgroup$ – Untitpoi Jun 6 '18 at 17:22
  • $\begingroup$ @Phylyp, exactly, and this is why I say that it has benefited massively from the thoughts of other posters, and most noteably TwoBitOperation $\endgroup$ – owen88 Jun 6 '18 at 18:42
  • $\begingroup$ @Untitpoi, yes but what I said in the (updated) question is that they do not want to share their data. In this solution they would be sharing a function definition, with none of their own data $(N_1,A)$ being shared. $\endgroup$ – owen88 Jun 6 '18 at 18:44
-1
$\begingroup$

You mention "database", so I am tempted to use a database-oriented answer:

Create an interface that can read from both companies' data systems. Run a join query to produce the needed result.

The common field (eg person id), which needs to be missing in order to not violate rule 2, is only stored in temporary memory, which is generally random access and thus I would argue it does not mean that even the computer itself has any access to it.

Now of course, if by "party" we may mean the data system, my answer fails. That doesn't seem a problem to me, because we then could mean the entire humanity and its data as "party", thus the problem would be unsolvable.

$\endgroup$

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