Multiparty Protocol that Usually Shuffles
This work addresses secure distributed computation for parties needing to agree on random permutations without trusted third parties, offering incremental improvements in efficiency for specific shuffling scenarios.
The paper tackles the problem of secure multiparty shuffling by proposing two data-oblivious protocols based on permutation networks, achieving unconditional security against malicious adversaries with corruption limits, and providing concrete bounds on adversarial learning probabilities such as ((n-t)!)^{-1} for the n-permute protocol.
Multiparty computation is raising importance because it's primary objective is to replace any trusted third party in the distributed computation. This work presents two multiparty shuffling protocols where each party, possesses a private input, agrees on a random permutation while keeping the permutation secret. The proposed shuffling protocols are based on permutation network, thereby data-oblivious. The first proposal is $n\text{-}permute$ that permutes $n$ inputs in all $n!$ possible ways. $n$-permute network consists of $2\log{n}-1$ layers, and in each layer there are $n/2$ gates. Our second protocol is $n_π$-permute shuffling that defines a permutation set $Π=\{π_1,\dots,π_N\}$ where $|Π| < n!$, and the resultant shuffling is a random permutation $π_i \in Π$. The $n_π$-permute network contains leases number of layers compare to $n$-permute network. Let $n=n_1n_2$, the $n_π$-permute network would define $2\log{n_1}-1+\log{n_2}$ layers. \par The proposed shuffling protocols are unconditionally secure against malicious adversary who can corrupt at most $t<n/3$ parties. The probability that adversary can learn the outcome of $n$-permute is upper bound by $((n-t)!)^{-1}$. Whereas, the probability that adversary can learn the outcome of $n_π$-permute is upper bounded by $\big(f_Π(n_1-θ_1)^{n_2}2^{θ_2}\big)^{-1}$, for some positive integer $θ_1, θ_2$, and a recursive definition of $f_Π$. The protocols allow the parties to build quorums, and distribute the load among the quorums.