Lookup

In this part, we describe how to produce a witness to the lookup argument described here.

We have a pair of arrays, A and S of the same length m, in our case S can be assumed to be public and already sorted, and A is a shared array, which is known to be a subset of S (with repetitions). The witness consists of a new pair of arrays, _A, _S, satisfing the following condition: either _A[i] == _S[i], or _A[i] == _A[i-1]. The second condition can not hold for i == 0.

The arrays also are constrained by requirement that A is a permutation of _A, and S is a permutation of _S.

The non-MPC algorithm does the following:

1. Sort A, this will be _A. Call an index i "initial" if either i == 0, or _A[i] != _A[i-1].
2. For each initial element, find the corresponding j such that _A[i] = S[j], and set _S[i] = S[j].
3. Fill in the rest of values.

Searching for elements in MPC is not very efficient, so we use a slightly different strategy:

1. Consider a disjoint union $T = A \sqcup S$ (we will add an additional parameter to remember from which array an element came from, so T[i].value represents the actual value, and T[i].ext is either 0 or 1). Sort in place by value.
2. Introduce a new bit flag: T[i].paired, which is set as (T[i].ext == 1 & T[i-1].ext == 0) | (T[i].ext == 0 & T[i+1].ext == 1).
3. Sort in place by ext > 1-paired, strip off additional introduced fields.
4. Create a new array of tuples pairs[i] = (T[i], T[m+i]).
5. Sort this array by the first element of the tuple in place, set (_A[i], _S[i]) = pairs[i].

Why this works:

First, we sort by value, so obtain the batches of the same value coming from A, intercepted by increasing values coming from S. The field paired is set to 1 exactly for one element from A and corresponding element from S (also, in this phase we could check whether lookup is incorrect if we wanted, which amounts to a situation where the neighboring elements with ext == 0 have different values).

Now, we order by ext, splitting the arrays back and there move the elements of paired == 1 kind to the left of their respective halves. Upon pairing, and sorting by the first element of the tuple, each paired element of A becomes first in a batch of the elements of equal value (because the sort was stable).