Oblivious sort by key

We describe here briefly the construction of Hamada et al. The only difference with it is that we suggest using Laud's efficient oblivious random permutation protocol instead of the one used in the original paper.

The sort here is, actually, a stable radix sort.

Sort by revealed key

This is a subprotocol, which picks an array of (key, value) pairs $([K_i],[V_i])$ and sorts it by key, but leaks keys in process.

It works as follows:

1. Do oblivious random permutation.
2. Reveal keys and sort the array by them.

Stable sort by $r$-bit register

Consider a short key of size $r$ bits. We will now sort an array of size $m$ by this key.

1. For each $i$, form an indicator vector $\bar P_i$ of size $2^r$, where $[P_{ij}] := [K_i = j]$.
2. Form also a vector $\bar S_i$, such that $[S_{ij}] = [K_i < j] = \underset{s>j}{\overset{2^r}\sum} P_{is}$.
3. For each $i$ from $1$ to $m$, calculate the running sum $[\bar Q_i] = \underset{k=0}{\overset{i-1}\sum} [\bar P_k]$. This counts the amount of different values of the key up to the point $i$.
4. Calculate the reveal key $[R_i] = \underset{k=0}{\overset{2^r - 1}{\sum}}([Q_{ik} P_{ik}] + [Q_{mk} S_{ik}])$. This calculates the amount of key values less than the current key value, plus the amount of the key values equal to the current key value before this element - which is exactly the position where the element should land in a sorted array.
5. Engage in the revealing sort subprotocol, using $R_i$ as keys.

Stable sort by key

The stable sort by key works by splitting key into $r$-sized registers, and then engaging in a stable sort by registers.

Complexity

Steps of one instance of stable sort by $r$-bit register involve:

1. 6 online rounds for equality test.
2. 0 rounds
3. 0 rounds
4. 1 round for multiplication
5. n rounds for oblivious permutation and 1 round to open $R_i$

Therefore, it takes $8+n$ rounds. The size of $r$-bit registers is, therefore, a tradeoff between (exponential) blowup in offline computation and amount of invocations of the stable sort by register.