Keywords

1 Introduction

Securely merging two sorted lists into a single, globally sorted list with the same asymptotic complexity as in the insecure setting has been a long-standing open problem. It is a fundamental tool in many machine learning and data-processing applications [6, 42, 57], Oblivious RAM [31, 45], and Private Set Intersection (PSI) [36]. A series of works [1, 13, 32, 33] have shown that securely sorting a list can be done with the same asymptotic complexity as insecure sorting. On the other hand, for merging, a gap remains. In the past, it has been solved with complicated techniques that either run in super-linear time or communication, or make unnatural assumptions.

In the insecure setting, and in the three-party ORAM setting, where there are three servers and a trusted client, merging two sorted lists of length n can be done in O(n) time, [10], whereas in the secure setting, the best existing 2-party secure merge algorithm requires \(O(n \log \log n)\) communication [26].

Our main result is to close this gap. More explicitly, we show

Theorem 1 (Main Theorem)

There exists a 2-party protocol for merging two locally sorted lists in linear-time, space and communication that provides security against semi-honest adversaries. The protocol only requires black-box use of an Additively-Homomorphic cryptosystem and a generic secure computation protocol for comparison and equality-testing on secret shares.

Secure 2-party merge protocols arise naturally, since the two participants can each sort their list locally before the protocol begins. Three-party protocols for secure merge are less natural, since there are still only two lists being merged, but these lists are secret-shared amongst the three computation parties. If the two lists being merged were initially held in the clear by two parties, then it’s unnatural to require a third party to aid in the secure merge procedure. On the other hand, if the two lists were initially secret-shared among two parties (e.g. as the output of a previous 3-party computation) it becomes less natural to assume that they are pre-sorted (since they cannot have been sorted locally).

One application of two-party merge protocols is in Private Set Intersection (PSI). There are many PSI protocols, but most output the intersection in the clear (e.g. [11, 12, 16, 20,21,22, 24, 28, 35, 37,38,39,40,41, 47, 48, 51,52,53]). In many applications, however, PSI is only a first step in a larger computation, and in these settings the PSI must return secret shares of the intersection, rather than the list itself – but these secret-shared PSI protocols (e.g. [17, 49, 50]) tend to be less efficient than protocols that reveal the intersection in the clear. One of the earliest methods for secret-shared PSI is the sort-compare paradigm [36], where the participants sort their joint list, then compare adjacent elements in a linear pass, deleting singletons. The problem with this approach is that the initial sorting step takes \(O(n \log n)\) communication. Using our novel linear-time secure merge protocol, the sort-compare paradigm gives a simple, efficient linear-communication secret-shared PSI protocol.

Our protocol is inspired by the 3-server ORAM merge protocol of [10], where the two sorted lists are treated as linked lists, then each linked list is shuffled with a collection of “dummy” elements using a linear-time three-party secure shuffle [43]. Thereafter, the trusted client can traverse the shuffled linked lists, comparing one element at a time, as in the standard insecure merge protocol.

There are several obstacles that need to be overcome in order to eliminate the trusted client and one of the servers from the [10] merge protocol. We can use a linear-time 2-party secure shuffle [26] to replace the 3-party shuffle, but updating the pointers in the shuffled lists is challenging without a trusted client.

To overcome this obstacle, we develop a technique for converting values encrypted under the key of one participant into additive secret shares of the same underlying plaintext (See Sect. 5.2). This conversion process is extremely efficient, and only relies on the cryptosystem being additively homomorphic. Moreover, the trusted client in [10] can easily switch from the real to dummy list obliviously once the real list is exhausted; however, this is non-trivial in our 2-party setup since obviously neither party should learn when a real list has been exhausted. We combat this issue by creating a unique, partially circular linked list (Sect. 5.1 and Fig. 1) such that the protocol can seamlessly switch from the real to dummy list.

Using this novel linked list construction and ciphertext-to-secret-sharing tool, we give a two party secure merge protocol, where each participant treats their input as a linked list, then allows the other participant to shuffle this linked list (while updating the pointers). The parties then re-share these permuted linked lists, and compare elements one at a time (using a secure comparison protocol), while the exact sequence of data accesses from each list is independent of the underlying data. See Sect. 5 for the full construction.

The detailed security proofs and analysis are presented in the full version of the paper [25].

2 Previous Work

2.1 Secure Sorting

Merging two sorted lists can be seen as a special case of sorting, and thus any sorting protocol is also a merge protocol. When security is not required, a simple counting argument shows that any comparison-based sorting algorithm requires \(O(n \log n)\) comparisons, whereas two sorted lists can be merged using only O(n) comparisons. Although secure merge protocols are a building block for many secure multiparty computations, most applications focus on the more general (and more difficult) problem of secure sorting.

One route for building a secure sorting protocol is to securely implement a data-oblivious sorting network using a generic circuit-based secure multiparty computation (MPC) protocol (e.g. GMW [30], BGW [7] or Garbled Circuits [59, 60]). Asymptotically, the best sorting network is the AKS network [1], which requires \(O(n \log n)\) comparisons. Although the AKS network is asymptotically optimal, the hidden constants are extremely large [2], and so the AKS network has little practical value. In practice, Batcher’s bitonic sort [5] which requires \(O(n \log ^2 n)\) comparisons is much faster and is widely implemented in practice, including in the ABY [23], Obliv-C [61] and EMP [58] compilers. Batcher’s sorting network is defined recursively, and thus when using Batcher’s network to merge two pre-sorted input lists, all but the final level of the recursion can be omitted. Unfortunately, this does not improve the asymptotic complexity, but it does increase the concrete performance by about a factor of 2.

One problem with implementing traditional sorting algorithms (e.g. quicksort, mergesort, radix sort) using generic secure computation, is that the they are not data-oblivious – even if the comparisons are implemented securely, the data movement depends on the underlying values being sorted. The shuffle-then-sort paradigm [13, 32, 33], solves this problem by first obliviously shuffling the input lists, then securely executing a traditional sorting algorithm. The initial shuffle ensures that the data movement (which is not hidden by the secure computation) is independent of the underlying data. These techniques yield an asymptotically optimal (\(O(n\log n)\)) sorting algorithms, that are also efficient in practice.

The efficiency of the shuffle-then-sort paradigm rests on the efficiency of the secure shuffle protocol. In the 3-party setting there are linear-time secure shuffles (based on one-way functions) [43], and in the 2-party there are linear-time secure shuffles (based on additively homomorphic encryption) [29].

Applying the shuffle-then-sort paradigm to the problem of merging immediately yields \(O(n \log n)\)-communication oblivious merge protocols, but does not achieve the O(n)-time merging that is possible in the insecure setting. In fact, the \(\varOmega (n \log n)\) lower bound on comparison-based sorting means that this approach will never yield a linear-time secure merge algorithm – unless we can take advantage of the fact that the initial lists being merged are pre-sorted.

Alternative sorting schemes (e.g. Radix sort) avoid the \(\varOmega (n \log n)\) lower bounds on comparison-based sorting. Another example is [34] in the randomized setting which sorts integers in \(O(n\sqrt{\log \log n})\) expected running time. These sorting algorithms are efficient, but rely on the RAM model of computation, and their data-dependent access patterns cannot be efficiently implemented in the circuit model. One exception is [4], which uses non-comparison based techniques to beat the \(\varOmega (n\log n)\) lower bound, but still remains in the circuit model.

2.2 Secure Merging

Secure, multiparty merge protocols have been studied separately from secure sorting protocols, and just as in the insecure case, focusing on the problem of merging allows us to circumvent the \(\varOmega (n \log n)\) lower bound for sorting.

The first secure merge protocol with (asymptotically) less communication than a corresponding secure sort was given in the 3-server ORAM setting (which requires 3-servers and a trusted client), where there is an information-theoretic secure merge protocol with only O(n) communication [10]. In general, any k-server ORAM protocol, the client can be emulated using secure multiparty computation (MPC), thus the protocol of [10] also yields a 3-server secure merge protocol. Unfortunately, using MPC to securely emulate an ORAM client can dramatically hurt performance since the ORAM client may not be “MPC friendly”, e.g. the client may have a very large circuit complexity, which leads inefficiencies when emulating the ORAM client under MPC.

The key idea of [10] is to apply “shuffle-then-sort” [13, 32, 33] to the idea of merging. Essentially, the participants shuffle the two (sorted) linked-lists – updating the pointers to each element’s new, shuffled location. Then the participants apply a standard (non-oblivious) merge protocol to traverse these shuffled linked lists (without needing to hide the data movement). These techniques yield a linear-communication secure merge protocol, but the construction of [10] only works in the 3-party ORAM setting, i.e., when there are four parties, three servers and a trusted client.

The “shuffle-then-merge” paradigm is a bit more delicate than the “shuffle-then-sort” paradigm, since the input lists in a merge are pre-sorted, and the merge protocol must process them in this sorted order (even after the oblivious shuffle). To overcome this difficulty, the pre-sorted input lists can be turned into linked lists, and the oblivious shuffle can update each item’s pointer to point to the permuted position of its successor [10].

In the two-party setting, [26] gives a protocol based on additively homomorphic encryption that securely merges two lists using \(O(n \log \log n)\) communication. The key idea of [26] is that since the input lists are pre-sorted, we can divide the entire list into poly-logarithmic sized blocks, and focus on moving these blocks into (nearly) the correct positions. Once the large blocks are in place, the small number of remaining “strays” that are out of place, can be identified and moved efficiently. Although our solution is fundamentally different, like [26], we also rely on a linear-time 2-party shuffle.

Our protocol follows a shuffle-then-merge paradigm that is similar to [10], but in order to adapt this to the two-party setting, we create a new protocol for shuffling linked lists in the two-party setting (which can be seen as an extension of the two-party oblivious shuffle of [26, 29]).

3 Overview

3.1 Challenges

In the insecure setting, two parties can merge their locally sorted lists by simply comparing their smallest elements and advancing the list with the smaller element. This operation is linear in the length of the two lists. The core issue in translating this linear-time merge algorithm to a secure version is that advancing a list is not data-oblivious – it reveals which list contained the smaller element.

figure a

There are two key challenges when trying to adapt the non-oblivious naïve merge protocol (Protocol 1), into an oblivious variant.

  1. 1.

    Which list is being accessed: Whether the algorithm reaches Line 4 or Line 7 reveals which list is being accessed.

  2. 2.

    Which location is being accessed: When the algorithm reaches Line 4 (resp. Line 7), it reveals which element of A’s (resp. B’s) list is being accessed at iteration \(i_C\).

We also face an additional challenge: we have only two participants in the protocol unlike these prior works which had three, either two servers and a trusted client [44] or three servers and trusted client [10].

3.2 Intuition and Construction Overview

Oblivious Shuffle with Linked List: To address challenge 2, we rely on an oblivious permutation. In the multiparty setting, it is possible to perform efficient (linear-time), oblivious shuffles of secret-shared lists [43]. Similarly, in the two-party scenario, the participants can use additively homomorphic encryption to obliviously shuffle ciphertexts in linear time [26, 29]. These linear-time multiparty shuffles are a key building block of many secure multiparty sorting protocols [13, 32, 33], and secure merge algorithms [10, 26].

By viewing each participant’s sorted input as a linked list, then shuffling that list, the parties can decouple the locations being accessed from the iteration of the loop – for example, at Line 4 the protocol would read location \(\Pi _A(i_A)\) for some random permutation \(\Pi _A\), instead of directly reading \(i_A\).

There are some subtleties here, as the parties need to obliviously permute their linked lists, and then obliviously traverse them.

In order to allow the parties to traverse the permuted linked lists in the original (sorted) order, the parties must also update the pointers. Thus if \(\pi \) is a permutation of [n], and the original list is \((v[0],\ldots ,v[n-1])\), the parties will create two new arrays

$$\begin{aligned} w&= \left( v\left[ \pi ^{-1}(0) \right] ,\ldots ,v\left[ \pi ^{-1}(n-1) \right] \right)&\text{ Permuted } \text{ data }\\ t&= \left( \pi \left( \pi ^{-1}\left( 0 \right) +1 \right) ,\ldots ,\pi \left( \pi ^{-1}\left( n-1 \right) +1 \right) \right)&\text{ Permuted } \text{ tags } \end{aligned}$$

With \(t[\pi (n-1)] = \perp \). Thus if \(w\left[ i \right] = v\left[ j \right] \), then \(w\left[ t \left[ i \right] \right] = v\left[ j+1 \right] \).

This structure allows the parties to traverse the permuted list, w, by first revealing \(\pi \left( 0 \right) \) and then, selectively revealing elements of t, starting with \(t[\pi (0)]\), \(t[\pi (1)]\), \(\dots \)

Our goal is for each party to achieve a secret-shared, permutation of their own list permuted (as well as the updated pointers) by the other party. In our construction, the second party acts as a permuting party for the first and generates both the permuted list and the corresponding linked list to traverse it. To maintain privacy of the data and obliviousness of the memory accesses, the second party’s permutation, and the first party’s data must remain private.

Now, if the permuting party holds on to its share of the owner party’s list, it is not clear how to obliviously traverse the permutation since the permuting party knows the position of each accessed share, and thus each element.

When there are three participants this can be done information-theoretically, by having each participant generate a permutation and secret-share to the other two participants [10]. In the two party setting, we can use additively homomorphic encryption to (obliviously) permute a private list [26, 29], but we cannot use those constructions in a black-box manner, since they do not allow us to create the shared tags needed to traverse the permuted list.

Instead, we recombine the shares at the owner party but to maintain obliviousness, i.e. to hide the data itself so as to not leak the permutation, both parties somehow convert their shares into shares encrypted using the permuting party’s public key. The owner party can then use the additive homomorphism of the encryption scheme to add the encrypted shares and obtain an encryption of the element under the other (permuting) party’s public key. Therefore, it cannot decrypt to learn the underlying value (and thus, permutation).

Adding Dummies and Oblivious Pointer Advancement: To address challenge 1, we add “dummy” elements to each party’s list so that we are able to advance both lists every iteration of the loop. For simplicity, suppose both parties’ lists are of size n. Then, both parties can generate n dummy elements and maintain two separate pointers to keep track of the real and dummy elements respectively. These dummies are interspersed with the real elements to create a list of 2n elements. At every iteration, the party with the smaller element advances its real pointer, while the other party advances its dummy pointer. This ensures that an element is consumed from both lists every iteration of the merge.

Finally, we are left with two more operations: (1) comparing encrypted real values efficiently and (2) advancing lists obliviously. We achieve (1) using a trick to convert ciphertexts into secret shares which can be passed to any state-of-the-art 2-party comparison protocol [18, 55] to avoid executing an expensive decryption circuit jointly; and we accomplish (2) by a clever construction of the linked list. The detailed shuffle and merge protocol is shown in Sect. 5.

4 Preliminaries

4.1 Secret Sharing

Our protocol makes use of an additive secret sharing scheme, where a secret \(x \in \mathcal {G}\) is shared as (\(x - r\), r), for some random \(r \leftarrow \mathcal {G}\) where \(\mathcal {G}\) is the finite group that parameterizes the Group Homomorphic Encryption scheme. In the two-party setting all linear secret-sharing schemes are essentially equivalent [19], so we can focus on this scheme without loss of generality.

As is standard, we use the notation \(\llbracket x \rrbracket \) to denote a secret sharing of the plaintext x. Using the linearity of the secret sharing scheme, the participants can compute \(\llbracket x+y \rrbracket \) from \(\llbracket x \rrbracket \) and \(\llbracket y \rrbracket \) with no communication.

For more complex calculations on shares, we rely on secure multiparty computation (MPC), described below.

4.2 Secure Computation

Our protocol makes use of a few simple primitives for processing on secret shares, comparisons, multiplexing and equality tests. These basic primitives are implemented in essentially every secure computation framework, including ABY [23], EMP [58], SCALE-MAMBA [3] and MPyC [54].

We assume that there is an underlying ordering on the elements of \(\mathcal {G}\) – this is a necessary assumption since the parties want to sort their elements.

Our construction is compatible with both arithmetic and boolean secure computation protocols, although comparisons and equality tests are likely to be more efficient in boolean-circuit-based secure computation protocols.

figure b

4.3 Additively Homomorphic Encryption

Our construction makes use of a semantically secure, additively homomorphic cryptosystem, \((\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec},\mathsf {Add})\). Our system is compatible with classical additively homomorphic schemes like Paillier [46], or lattice-based schemes that natively work over \(\mathbb {Z}/2\mathbb {Z}\), e.g. BFV [9, 27] or CGGI [14, 15], both of which are widely supported by current FHE implementations [56]. Note that the security we require for the \(\mathsf {Add}(\cdot ,\cdot ,\cdot )\) is much weaker than full circuit privacy [8], since in our application the summations being computed are known to both parties, and only the summands are private.

In order for our final merge protocol to achieve linear communication, the underlying additively homomorphic cryptosystem must have constant ciphertext expansion.

figure c

4.4 Notation

As there are only two parties, and each party has a unique public key (for the additively homomorphic cryptosystem), when we say “key i” we mean the public key of party i, \(pk_i\).

We denote each party as \(P_i\) where \(i\in \left\{ 0,1 \right\} \). As all our protocols are two-party protocols (and most are completely symmetric), we take all subscripts modulo 2, thus if \(P_i\) is one party, \(P_{i+1}\) is the other party.

Several protocols below must be run twice, one time for each party, so we give such protocols an index with respect to which we write the steps within the protocol. For example, \(\mathsf {Protocol}_i\) will be called twice, for \(i\in \left\{ 0,1 \right\} \) and we use index i within the protocol to identify the parties. Similarly, we use the same index to define the ideal functionality.

We introduce some more notation in Table 1.

Table 1. More notation
Full size table

5 Construction and Protocol Definitions

In this section we describe our construction. First, we present a two-party algorithm for creating and shuffling linked lists. Second, we present a technique for converting encryptions (encrypted by one party) into secret shares. Third, we show how to combine these tools into our main construction which is a linear-communication secure merge protocol.

We assume that party i has a key pair \((pk_i,sk_i)\) for an additively homomorphic cryptosystem \((\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec},\mathsf {Add})\).

5.1 Obliviously Shuffling Input Lists

In this section, we describe our novel two-party protocol for padding and shuffling private linked lists. \(\mathsf {ShuffleLL}_i\) (Protocol 2). The goal of the \(\mathsf {ShuffleLL}_i\) protocol is for party i to achieve a random permutation of its input list with dummies encrypted under party \((i+1)\)’s public key. The protocol takes a parameter, m, defining how many “dummy” elements are created. Although \(\mathsf {ShuffleLL}_i\) takes m as a parameter, in our final merge protocol, \(P_1\) should set m equal to the length of its input list. The \(\mathsf {ShuffleLL}_i\) protocol realizes the ideal functionality, \(\mathcal {F}^{i}_{\text {shuffle}}\) below.

figure d

In the second last step, we output a 2-tuple which are secret shares of the head pointers (positions) of the dummy and real list respectively. In the last step, we output the secret share of the position of a special end-of-list dummy element. This special element is used to obliviously switch between the real and dummy list. It is explained in detail in Sect. 5.1 and 5.3.

Below, we describe the shuffle for party \(P_0\) but in the final protocol they also swap positions and rerun. Assume that \(P_0\) holds a sorted list v of length n, and \(P_1\) generates a random permutation \(\pi \) over \(\left[ m+n \right] \). Then, the protocol proceeds as follows,

  1. 1.

    Encrypt sorted list: To hide its real elements (input list), \(P_0\) encrypts each element using its public key \(pk_0\) and sends the list of ciphertexts (in sorted order of the underlying value) to \(P_1\).

  2. 2.

    Generate shares: Given a value \(v'\), party 1 can create an additive sharing of \(v'\) as \((v'-r,r)\) for some random value \(r \in \mathcal {G}\). In our setting, however, \(P_1\) does not have the plaintext value, \(v'\), but instead has an encryption \(\langle \!\langle {v'}\rangle \!\rangle _{0}\).

    Using the additively homomorphism, given a ciphertext \(\langle \!\langle {v'}\rangle \!\rangle _{0}\), party 1 creates the encrypted pair \((\langle \!\langle {v'-r}\rangle \!\rangle _{0},\langle \!\langle {r}\rangle \!\rangle _{1})\). See Line 2.

  3. 3.

    Concatenate encrypted dummies: Party \(P_1\) creates a special dummy known as the end-of-list element, and \(m-1\) random dummy elements. The end-of-list element marks the end of both the real and dummy list but also points to the first element of the dummy list. Therefore, the end-of-list element along with the dummy elements form a cycle. The end-of-list element stores the largest real value in sorted order instead of a random number as its value. \(P_1\) easily constructs the end-of-list element encrypted under \(pk_0\) by just duplicating \(\langle \!\langle {v\left[ n-1 \right] }\rangle \!\rangle _{0}\). Instead of a linked list terminating by pointing to \(\perp \), we will have it point to the this end-of-list element. The purpose of the special element becomes apparent when either party’s real list is exhausted and we must obliviously switch to traversing the dummy list while we access the remaining real elements from the other party (See Sect. 5.3).

  4. 4.

    Permute ciphertexts and create linked list: Party \(P_1\) permutes the pair of shares using \(\pi \) by assigning the \(k^{\text {th}}\) element of the permuted list to the \(\pi ^{-1}\left( k \right) ^{\text {th}}\) element of the concatenated list as shown in Line 5. To traverse the permuted list in sorted order, \(P_1\) also generates a linked list such that the \(i^{\text {th}}\) element is the position of the next element in sorted order (see Line 6). We also point the last dummy element to the end-of-list element. Therefore, the real (resp. dummy) list reaches the end-of-list element after n (resp. m) steps. See Fig. 1 below which illustrates this construction.

    To hide the linked list from party \(P_0\) (and thus, the underlying permutation), \(P_1\) encrypts each element of the linked list using its public key, \(pk_1\). Finally, it secret shares the position of the first dummy and the first real element as a 2-tuple head pointer, and the end-of-list element.

  5. 5.

    Recombine shares: \(P_1\) sends both the shuffled ciphertext pairs and the encrypted linked list to \(P_0\). Party \(P_0\) first decrypts the ciphertexts which were encrypted under its own public key, \(pk_0\) and then re-encrypts them using \(pk_1\), \(P_1\)’s public key. Using the additive property of the encryption scheme, \(P_0\) adds the newly obtained ciphertexts to their corresponding ciphertexts in the pair. Due to the homomorphic property, \(P_0\) obtains an encryption of the sum of the underlying value which is in fact, the original set of real/dummy elements as the pairs were constructed precisely from those values.

Fig. 1.
figure 1

Construction of the linked list. d[1] and v[0] (as pair of encrypted shares) are the at the head of the dummy and real pointer respectively. Both the last real element, \(v[n-1]\) and last dummy element, \(d[m-1]\) point to the end-of-list element.

Full size image

Therefore, at the end of Protocol 2, \(P_0\) obtains a permutation (oblivious to itself) of its original list with dummies encrypted under \(P_1\)’s public key, along with an encrypted linked list to traverse it. Note that the end-of-list element is treated as a dummy element but stores a real value which is crucial in proceeding obliviously when either party exhausts its real list. We further elaborate on this in Sect. 5.3.

We prove \(\mathsf {ShuffleLL}_i\) securely computes the ideal functionality \(\mathcal {F}^{i}_{\text {shuffle}}\) in [25].

figure e

5.2 Converting Ciphertexts to Secret Shares

In this section, we give an efficient 2-party protocol for converting ciphertexts from an additively homomorphic cryptosystem into secret shares of the same underlying value. A similar idea was used implicitly for creating “blinded permutations” [29].

In principle, a general-purpose MPC protocol can always be used to convert ciphertexts to secret shares by evaluating the decryption circuit for the encryption scheme within the MPC, but, in general, this is extremely inefficient. \(\mathsf {EncToSS}_i\) (Protocol 3) gives an extremely efficient two-party protocol for achieving the same result when the underlying cryptosystem is additively homomorphic. \(\mathsf {EncToSS}_i\) realizes the ideal functionality, \(\mathcal {F}^{i}_{\text {decrypt}}\) defined below.

figure f

In our setting, party i holds a ciphertext \(c = \langle \!\langle {v}\rangle \!\rangle _{i+1}\) of a private value, v, encrypted under party \((i+1)\)’s key. At the end of the protocol, the parties hold additive secret shares of the underlying value v, and neither party learns anything about v.

We prove that \(\mathsf {EncToSS}_i\) securely computes \(\mathcal {F}^{i}_{\text {decrypt}}\) in [25].

figure g

5.3 Securely Merging Obliviously Shuffled Lists

We are finally ready to securely merge the two parties’ lists. Our \(\mathsf {Merge}\) protocol realizes the ideal functionality, \(\mathcal {F}_{\text {merge}}\) defined below.

figure h

Suppose party \(P_i\) holds list \(v_i\) of size \(n_i\). The protocol proceeds as described below.

  1. 1.

    Obliviously shuffle padded list with linked list: First, both parties call \(\mathsf {ShuffleLL}_i\) (for \(i\in \left\{ 0,1 \right\} \) (as described in Protocol 2) to obtain an encrypted, permuted version of their input list padded with dummies (including the end-of-list element). \(\mathsf {ShuffleLL}_i\) also outputs an encrypted linked list that party i later uses to traverse their list without leaking the accessed positions to party \(i+1\) (who knows the permutation).

  2. 2.

    Access elements from shuffled list: The parties maintain a secret-shared bit for each party, \(\llbracket b_i \rrbracket \), and \(b_i = 1\) at iterations where \(P_i\) needs to access a real element, and \(b_i=0\) at iterations where \(P_i\) needs to access a dummy element. In the first step, both parties access their first real element, in all subsequent steps since only one party advances its real list.Footnote 1 The bit, \(b_i\), allows the parties to select and update the appropriate values obliviously using the \(\mathsf {mux}\) operation (e.g. Protocol 5 line 9).

    At every step in the protocol, the parties also maintain a secret sharing of the last observed real value in \(P_i\)’s list, \(cur_i\). In any iteration where a dummy element must be consumed from party i’s list, we use \(b_i\) to obliviously select \(cur_i\) over the dummy value, effectively discarding it in place of the actual real value to be compared. See Line 14 of Protocol 5.

  3. 3.

    Compare real values: Using \(b_i\), we obtain the real values at the head of each real list. To find the smaller element, we use a generic comparison protocol (Sect. 4.2) which returns a (secret-shared) bit equal to 1 if party 0’s real value was smaller than party 1’s. Therefore, we set \(b_0\) to the result of the comparison protocol (line 15) and \(b_1 \leftarrow 1 - b_0\) (line 16) allowing us to appropriately update the head pointer for the next step.

  4. 4.

    Update head pointer: Now, we advance one party’s real list and the other party’s dummy list as follows. First, we find the next position from the encrypted linked list using \(\mathsf {EncToSS}_i\). Then, we update the appropriate entry of the head pointer using bit, \(b_i\) (line 1). If \(b_i = 1\), then this means that \(P_i\)’s real value was smaller and we must advance the real (resp. dummy) pointer to obtain the next real (resp. dummy) value from \(P_i\)’s (resp. \(P_{i+1}\)’s) list. Protocol 4 details how the head pointer is advanced. We prove in [25] that that every memory location in the shuffled list is accessed exactly once, which makes the overall access pattern independent of the underlying data.

  5. 5.

    Switching from an exhausted list: When either party exhausts their real list, we must somehow notify the protocol and secret-share the remaining values of the other real list.

    We keep track of when a real list is exhausted by checking when the real pointer reaches the end-of-list element. We do so securely using a generic equality testing MPC protocol as described in Sect. 4.2. We maintain another secret-shared bit, fin initialized to 0, which acts like a boolean flag and is inverted as soon as either real pointer reaches its corresponding end-of-list element. See line 10 of Protocol 5.

    Without loss of generality, suppose that party 0 exhausted its real list first. This implies that \(b_0 = 1\) (and \(b_1 = 0\)) from the previous iteration, and the real pointer has been advanced to store the position of the end-of-list element. Recall that the underlying value of the end-of-list element is exactly the same as the largest real value, i.e., the most recent element that party 0 accessed in the previous iteration. So on Line 14, \(val_0\) will equal the end-of-list element i.e., the largest real value of party 0, and \(val_1\) will equal \(cur_1\), the most recent real value from party 1 that has not been advanced and secret-shared yet. Therefore, essentially, we will perform the same comparison as the previous iteration and conclude that \(val_0\) is smaller. However, \(val_0\) is a duplicate of the most recent real value that was secret-shared in the previous iteration. This is where we use the fin bit to “reverse” the bits so that we instead select \(val_1\) as the next real value, and advance the real pointer of party 1 (and dummy pointer of party 0) as required since we’re only left with real values from party 1’s list. As \(val_0\) is smaller than every remaining real value in party 1’s list, every comparison hereafter will always return \(b_0 = 1\) which we always invert hereafter using fin. We prove fin remains 1 once set in [25], thus proving the correctness of the algorithm. In summary, performing these dummy comparisons allows the protocol to remain oblivious by still accessing elements from the permuted list, and using the fin bit allows the protocol to correctly compute the merge.

    Lastly, notice that if party 1 exhausts it real list first, then by construction, party 0’s dummy pointer will reach the end-of-list element as we consume one dummy for each real element after the first one and thus, cycle back from the last dummy element to the end-of-list element. And since party 1 just exhausted its real list, we know \(b_0 = 0\) and \(b_1 = 1\). So, \(pos_0\) is equal to the position of the dummy pointer, i.e., the position of the end-of-list element. Therefore, in either case (whether party 0 or 1 exhausts a real list), \(pos_0\) will always equal the position of the end-of-list element and it is sufficient to only test \(pos_0\) for setting fin (line 10).

figure i

In the end, both parties obtain element-wise secret shares of the merge of their two sorted lists such that the resulting list is also in sorted order. We prove \(\mathsf {Merge}\) securely computes \(\mathcal {F}_{\text {merge}}\) in [25].

Our algorithm runs in time linear in the length of the two lists requires only linear communication between the two parties assuming the underlying encryption scheme produces ciphertexts with constant factor expansion. The concrete costs are outlined in [25].

figure j

6 Conclusion

In this paper, we presented the first linear-communication 2-party secure merge protocol. The protocol is asymptotically optimal, and efficient enough for practical applications. To achieve this protocol, we introduced a 2-party method to obliviously traverse a permuted list using a novel linked list construction and an extremely efficient technique to convert ciphertexts to secret shares.

Our secure merge protocol makes only black-box use of an additively homomorphic cryptosystem, and a secure computation protocol supporting comparisons, equality tests, and multiplexing on secret shared values.