3
$\begingroup$

Consider $n$ parties having their private inputs $s_1,\cdots,s_n$. How can they compute a public function $f(s_1,\cdots,s_n)= \pi$, where $\pi$ is a permutation of numbers between $1,\cdots,n$, using secret sharing scheme?

$\endgroup$
  • $\begingroup$ The permutation is of $1,\dots,n$ or of $s_1,\dots,s_n$? $\endgroup$ – mikeazo Mar 2 '17 at 15:11
  • $\begingroup$ Permutation is of $1,\cdots,n$. I want to define $\pi$ in such a way that it will take random numbers as an input and return me a set which is a permutation of numbers between $1,\cdots,n$ as an output. Constraint is that $\pi$ should be random permutation. $\endgroup$ – Ananya Shrivastava Mar 2 '17 at 17:31
  • $\begingroup$ So let's assume you had a trusted 3rd party that everyone could send their $s_i$ values to and that party would just compute the permutation. How would you do it in that case? Do you have an algorithm in mind? $\endgroup$ – mikeazo Mar 2 '17 at 18:07
  • $\begingroup$ 3rd party can execute pseudo random permutation (PRP), one example of it is block cipher, and return output to each party. But I'm not sure how I'll implement it without third party. $\endgroup$ – Ananya Shrivastava Mar 2 '17 at 18:22
2
$\begingroup$

If you are just lacking a function from some random number to permutations, this is easy:

Consider the set of all permutations of $\{1,\dots,n\}$, put them in lexicographical order and assign natural numbers. There are $n!$ permutations, so let's say $x$ is some random number from $\mathbb{Z}_{n!}$, and here's an algorithm how to get the matching permutation:

  1. Generate list $L = [1,\dots,n]$ and empty list $O = [\;]$
  2. $a = (|L| - 1)!$
  3. $b = \lfloor x / a\rfloor $
  4. Remove $L[b]$ from $L$ and append it to $O$
  5. $x = x \mod a$
  6. if $L$ is not empty: GOTO 2.
  7. output $O$

List indices are starting from $0$ as usual.

It wasn't stated in the question from which set the private inputs were taken, and ideally this would be from $\mathbb{Z}_{n!}$ (or alternatively $\{a, a+1, \dots ,a + n! - 1\}$). Then all you need is to use MPC to calculate the sum $x = s_1 + \dots + s_n \mod n!$, and use above algorithm to calculate the matching permutation. If the entropy of the inputs is not enough, use can use a PRG to expand this input and use $s'_i = PRG(s_i)$ instead (for party $P_i$).

$\endgroup$

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.