# Permuted vectors

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.

• I think you need some function that checks if the permutation is in the original order, such as it's hash. – user9070 Apr 27 '15 at 20:01
• @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. – user13676 Apr 27 '15 at 20:07
• 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. – mczraf Apr 27 '15 at 21:39

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$.