Consider two business associates, Adam and Karl, who want to arrange an exchange of information.
Adam has knowledge of two secret numbers k and j. He must never disclose their values to anyone.
Karl wants to calculate a function of these two numbers:
f(k, j) = k + j
Adam decides that it is OK for Karl to know the value produced by this function, but not the inputs.
This poses a tricky problem.
Karl is not interested in the input values, and though he trusts Adam to be honest about them, he wants some proof that his calculation is being performed correctly.
Puzzled by these seemingly irreconcilable constraints, they decide to call upon some mutual contacts for help.
Taking into account the size and importance of the problem, they agree that 3 helpers should be enough: H_1, H_2 and H_3.
Karl starts by choosing 2 random numbers r_1 and r_2 which he also keeps a secret.
If there were 4 helpers, he would have chosen 3 numbers, and so on.
For n random numbers, there are n+1 helpers.
For each helper H_i, he can apply a function g with k and j to obscure their true values:
g(n, i, x) = x + r_1*i^1 + r_2*i^2 + ... + r_(n-1)*i^(n-1) + r_n*i^n
Since there are only 2 random numbers (n=2), we can write this example more simply as:
g(2, i, x) = x + r_1*i + r_2*i^2
We can even go a step further and simply write down the formula we will use for each helper as a new function h(i, a) = g(2, i, a):
h(1, x) = x + r_1 + r_2
h(2, x) = x + 2r_1 + 4r_2
h(3, x) = x + 3r_1 + 9r_2
If Adam's secret numbers were k = 6, j = 8, r_1 = 5, r_2 = 7, applying each h above yields:
h(1, k) = 18 h(1, j) = 20
h(2, k) = 44 h(2, j) = 46
h(3, k) = 84 h(3, j) = 86
Adam distributes these obscured values to each of the respective helpers, and instructs them to calculate f.
We can call the results v_i:
v_i = f(h(i, k), h(i, j))
v_1 = f(h(1, k), h(1, j)) = f(18, 20) = 18 + 20 = 38
v_2 = f(h(2, k), h(2, j)) = f(44, 46) = 44 + 46 = 90
v_3 = f(h(3, k), h(3, j)) = f(84, 86) = 84 + 86 = 170
Karl receives the results from each helper. He now has the solution to three formulae:
f(h(1, k), h(1, j)) = (k + r_1 + r_2) + (j + r_1 + r_2) = k + j + 2r_1 + 2r_2 = v_1
f(h(2, k), h(2, j)) = (k + 2r_1 + 4r_2) + (j + 2r_1 + 4r_2) = k + j + 4r_1 + 8r_2 = v_2
f(h(3, k), h(3, j)) = (k + 3r_1 + 9r_2) + (j + 3r_1 + 9r_2) = k + j + 6r_1 + 18r_2 = v_3
With three equations, the two random variables r_1 and r_2 are easily eliminated, giving a solver function s:
k + j + 2r_1 + 2r_2 = v_1
k + j + 4r_1 + 8r_2 = v_2
k + j + 6r_1 + 18r_2 = v_3
3(k + j) + 6r_1 + 6r_2 = 3v_1
3(k + j) + 12r_1 + 24r_2 = 3v_2
k + j + 6r_1 + 18r_2 = v_3
6r_1 + 18r_2 = 3(v_1 - v_2)
k + j = v_3 - 3(v_1 - v_2)
s(v_1, v_2, v_3) = k + j = v_3 - 3(v_1 - v_2)
= f(k, j)
He evaluates this expression with the helpers' solutions, giving:
k + j = v_3 - 3(v_1 - v_2)
= 170 - 3(38 - 90)
= 14
This value is the correct result for k = 6, j = 8.
Note that the helpers had enough information as a group to determine the values for k and j, but Karl only has enough information to calculate k + j.
Questions:
- Can the same technique be used for
f(k, j) = k * j? - How about other operations? Division? Exponentiation? Modulo?
- Is there a more general way we can determine
sfor a givenn?