Oblivious random permutation

The procedure

This is the main building block of the oblivious sort. We briefly describe here the recent construction of Peeter Laud; it specifically requires SPDZ, so it might need to be replaced in case one wants to use different sharing scheme.

For each pair of parties $i, j$, we need to precompute the following data $X_i, X_j$ for each party:

1. The party $i$ picks a permutation $\pi$. Honest parties are assumed to pick it uniformly at random.
2. Pick a pair of random vectors $\bar x, \bar y \in_R \mathbb{F}^m$. Set $\bar z = \pi(\bar x) - \bar y$.
3. Set $X_i = (\pi, \bar z)$, $X_j = (\bar x, \bar y)$.

In practice, this can be done in the offline phase in a few different ways.

Then, this precomputed data can be used to construct from a vector $\bar a_j = (a_1, ..., a_m)_j$ belonging to the $j$-th party a permuted vector $[\pi(\bar a)]_{ij} = ([a_{\pi(1)}], ..., [a_{\pi(m)}])_{ij}$ shared between $i$ and $j$ in a following way:

1. $j$ sends to $i$ the vector $\bar a' = \bar a + \bar x$
2. $j$ sets $\pi (\bar a)_j = -\bar y$
3. $i$ sets $\pi(\bar a)_i = \pi(\bar a') - \bar z$

Now, the oblivious random permutation protocol of a shared value $[\bar a]$ is the following:

Repeat for each party $i$: Permute with $\pi_i$ each of the shares $\bar a_j$, setting the new shares value $\bar a_j := -\bar y_{ij}$; set $i$-th share to be the sum of discrepancies: $\bar a_i :=\overset{n}{\underset{j = 1; j \neq i}\sum}[\bar a'_{ij}]$.

This requires $n$ rounds and total $O(n^2 m)$ communication.

Active security

The protocol above is passively secure. The active check can be made post-factum: to check that a pair of vectors $\bar a, \bar b$ are permutations of each other, we sample a random value $t$ and check $\sum \frac{1}{a_i - t} = \sum \frac{1}{b_i - t}$.

Offline phase

Offline phase can be done in various ways. We are currently planning to use butterfly network to apply a permutation $\pi$ to a shared value $[x]$ in the offline phase, but other approaches are also possible (mixnet approach might outperform butterfly network for large $m$), this is largely TBD.