2
$\begingroup$

Consider we have two vectors $v_1, v_2$ of size $n$, and each vector contains $n$ elements. We permute the vectors as: $\pi (k_1,v_1), \pi (k_2,v_2)$. Where $\pi (k_i,v)$ denotes a permutation of a vector, $v$, using key $k_i$.

I use the above technique (permutation), to hide the original positions of the elements in each vector. I want to give away the two permuted vectors to a malicious server, to do some computation. Therefore, I need to reveal to it the relationship between the two permuted vectors; for instance, position 2 in the permuted $v_1$ is related to position 6 in permuted $v_2$.

Question: Given two permuted vectors, $\pi (k_1,v_1), \pi (k_2,v_2)$, and mapping between them, can an adversary learn the original position of the elements in either vector.

|improve this question
$\endgroup$
  • $\begingroup$ I think you need some function that checks if the permutation is in the original order, such as it's hash. $\endgroup$ – user9070 Apr 27 '15 at 20:01
  • $\begingroup$ @TruthSerum yes, in fact the party generates it has the keys, but the point is to hide the original order from an adversary, say untrusted server. So it should not be able to guess the right order, given the mapping between two permuted vectors. $\endgroup$ – user13676 Apr 27 '15 at 20:07
  • $\begingroup$ What do you mean by "to do some computation"? I mean, what is the adversary able to do exactly? My questions intend to formulate the threat model. $\endgroup$ – mczraf Apr 27 '15 at 21:39
4
$\begingroup$

Assuming that the probability distributions of $\pi_{k_1}$ and $\pi_{k_2}$ are both uniform (that is, each permutation can take on any particular setting with probability $1/n!$), then no, adversary does not have enough information to learn anything about the original positions. This remains true even if we assume the adversary can perform unbounded computations, and we don't need to make any assumptions on any possible correlations between $\pi_{k_1}$ and $\pi_{k_2}$

For any possible permutation of $v_1$, there is a unique permutation $\pi_{k_1}$ and a unique permutation $\pi_{k_2}$ that is consistent with this possibility. Because (by assumption), this selection of $\pi_{k_1}$ and $\pi_{k_2}$ is as probable as any other possible selection, the attacker gains no information of whether this permutation of $v_1$ was any more or less probable than any other permutation.

By symmetry, this also holds true for any possible permutation of $v_2$.

|improve this answer
$\endgroup$
  • $\begingroup$ Thus, even if we tell the adversary the correlation between the elements of the permuted vectors, it cannot learn the original position of the permuted vectors. $\endgroup$ – user13676 Apr 28 '15 at 14:24
  • 2
    $\begingroup$ On a sidenote: It would be equally secure if there was just one permutation applied to both vectors, because you tell the malicious server anyway which positions in the vectors correspond to each other. $\endgroup$ – tylo Apr 28 '15 at 15:34
  • $\begingroup$ @tylo: Quite true; that's what I was eluding to when I said that the two permutations needn't be independent. Perhaps I should have stated that outright... $\endgroup$ – poncho Apr 28 '15 at 16:32

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.