Please consider the following scenario: The user A and B use their keys, K1 and K2 respectively. Each client have a vector of elements. Each client separately permutes his vector using his key and outsources it to the untrusted server. This permutation prevents the server from learning the correct index of each element in this vector.

Now the clinet A and B wants to add exactly two values at the same index (i.e. the index in their original vector before permutation). Trivially, if they share a key, permute their vector using this key and then send each vector to the server, they can achieve what they want. However, they have used different keys to permute their vector, but want to do the same computation as before. Ideally they can interacts (after outsourcing the vectors) and exchange some information. Then the vector(s) at the server can be re-permuted similar to the situation the same key used for both.

Thus I am wondering such re-permutation exists, please. No matter if one client learns the key of the other, but the server should learn as little information as possible.


  • 4
    $\begingroup$ it is not clear what you want to achieve. what is the actual problem ? $\endgroup$ – sashank Sep 22 '14 at 16:03
  • $\begingroup$ To transform one of the vector to have the same permutation as the other one. $\endgroup$ – user153465 Sep 22 '14 at 16:05
  • 4
    $\begingroup$ The question is unclear. What vectors? Where did those come from? What does it mean to have the same permutation at the server, in both vectors? I can't follow you. Try editing your question. Specify what is known to each party, what the inputs from each party are, and what the desired output to each party is. Also specify the trust model. $\endgroup$ – D.W. Sep 22 '14 at 16:23
  • $\begingroup$ Also, why doesn't the trivial solution where A give B their key and B recalculates their vector work? $\endgroup$ – otus Sep 23 '14 at 6:08
  • $\begingroup$ I found the answer. The answer is homomorphic key PRFs. Thanks for your useful answers! $\endgroup$ – user153465 Sep 23 '14 at 19:19