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$
4
  • $\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
    Commented Feb 21, 2018 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
    Commented Feb 21, 2018 at 14:30
  • $\begingroup$ If B knows the result, he knows the hamming weight, so some (usually small) information leakage is unavoidable $\endgroup$
    – kodlu
    Commented Feb 21, 2018 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$ Commented Mar 23, 2018 at 18:03

1 Answer 1

2
$\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
  • 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
    Commented Apr 24, 2018 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.