2
$\begingroup$

Lets say A has a binary vector of length n, B has a permutation matrix of size n. Is there a way for B to permute A's vector so that A only learns about the result of permutation and B does not learn about the original vector?

$\endgroup$
  • $\begingroup$ Correct me if I'm wrong but surely if B knows the permutation p and the output he can invert p and use it to get the original vector again. $\endgroup$ – Jackoson Feb 21 '18 at 13:03
  • $\begingroup$ B doesn't know the output of the permutation, at the beginning A knows v, B knows P, and at the end A should know Pv while B still only knows P $\endgroup$ – Adam Feb 21 '18 at 14:30
  • $\begingroup$ If B knows the result, he knows the hamming weight, so some (usually small) information leakage is unavoidable $\endgroup$ – kodlu Feb 21 '18 at 20:36
  • 1
    $\begingroup$ Just as a random observation, if A can make $\log_2 n$ queries with $n$-bit vectors against the same permutation matrix, then they can trivially recover the entire permutation. So if this is possible at all, the number of queries must be strictly limited. $\endgroup$ – Ilmari Karonen Mar 23 '18 at 18:03
1
$\begingroup$

Using an encryption scheme that is rerandomizable (such as ElGamal for example), A can just send n ciphertexts encrypting her values, then B shuffles those ciphertexts and rerandomize them. B never learns anything and the rerandomization destroys information about the original ciphertexts so that A cannot trace back the permutation.

$\endgroup$
  • 1
    $\begingroup$ It's a binary vector, which implies the entries are all 0 and 1. With basic ElGamal you can't encrypt 0s. This question/answer provides a small modification that facilitates encryptions of 0. $\endgroup$ – Ella Rose Apr 24 '18 at 13:57

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.